diff tree3/tree.c tree4/tree.c
3,4c3,4
<  *  (store arbitrary 'things' using void*)
<  * 
---
>  *  (version 4: separating the 'tree' struct from the 'treenode' struct)
>  *
6d5
<  * Xia Zhou, July 2016
15c14
< /**************** types ****************/
---
> /**************** local types ****************/
17,19c16,23
<   int key;		      // search key for this item
<   void *data;		      // pointer to data for this item
<   struct treenode *left, *right; // children
---
>   int key;		           // search key for this item
>   void *data;		           // pointer to data for this item
>   struct treenode *left, *right;   // children
> } treenode_t;
> 
> /**************** global types ****************/
> typedef struct tree {
>   struct treenode *root;
22c26,35
< /**************** functions ****************/
---
> /**************** global functions ****************/
> /* that is, visible outside this file */
> /* see tree.h for comments about exported functions */
> 
> /**************** local functions ****************/
> /* not visible outside this file */
> static treenode_t *tree_insert_helper(treenode_t *node, 
> 				      const int key, void *data);
> static treenode_t *treenode_new(const int key, void *data);
> static void *tree_find_helper(treenode_t *node, const int key);
25,27d37
< /* Create a new tree for the given key and data;
<  * return NULL if error.
<  */
29c39
< tree_new(const int key, void *data)
---
> tree_new(void)
31,34c41,44
<   tree_t *node = malloc(sizeof(tree_t));
< 
<   if (node == NULL) {
<     return NULL;
---
>   tree_t *tree = malloc(sizeof(tree_t));
>   
>   if (tree == NULL) {
>     return NULL; // error allocating tree
36,40c46,48
<     node->key = key;
<     node->data = data;
<     node->left = NULL;
<     node->right = NULL;
<     return node;
---
>     // initialize contents of tree structure
>     tree->root = NULL;
>     return tree;
45,50c53,64
< /* Insert into the given tree, or NULL to start a new tree;
<  * wherein the item is described by a key and some data,
<  * and the tree is provided as a pointer to its root;
<  * providing a NULL root creates a new tree and returns it.
<  * If the key is already in the tree, its datum is update with new data.
<  * (The result is that old data pointer is lost.)
---
> void
> tree_insert(tree_t *tree, const int key, void *data)
> {
>   if (tree != NULL) {
>     tree->root = tree_insert_helper(tree->root, key, data);
>   }
> }
>     
> 
> /**************** tree_insert_helper() ****************/
> /* Recursively find the place to insert the new node;
>  * if 'node' is NULL it returns pointer to new node.
52,53c66,67
< tree_t *
< tree_insert(tree_t *node, const int key, void *data)
---
> static treenode_t *  // not visible outside this file
> tree_insert_helper(treenode_t *node, const int key, void *data)
57c71
<     return tree_new(key, data);
---
>     return treenode_new(key, data);
66c80
<       node->left = tree_insert(node->left, key, data);
---
>       node->left = tree_insert_helper(node->left, key, data);
68c82
<       node->right = tree_insert(node->right, key, data);
---
>       node->right = tree_insert_helper(node->right, key, data);
73a88,105
> /**************** treenode_new ****************/
> /* Allocate and initialize a treenode */
> static treenode_t * // not visible outside this file
> treenode_new(const int key, void *data)
> {
>   treenode_t *node = malloc(sizeof(treenode_t));
> 
>   if (node == NULL) {
>     return NULL;
>   } else {
>     node->key = key;
>     node->data = data;
>     node->left = NULL;
>     node->right = NULL;
>     return node;
>   }
> }
> 
75,77d106
< /* Return the data associated with the given key;
<  * return NULL if key is not in tree.
<  */
79c108,122
< tree_find(tree_t *node, const int key)
---
> tree_find(tree_t *tree, const int key)
> {
>   if (tree == NULL) {
>     return NULL;
>   } else {
>     return tree_find_helper(tree->root, key);
>   }
> }
> 
> /**************** tree_find_helper() ****************/
> /* Recursive function to find a node holding this key, 
>  * return data for the found node, or NULL if not found.
>  */
> static void * // not visible outside this file
> tree_find_helper(treenode_t *node, const int key)
87c130
<       return tree_find(node->left, key);
---
>       return tree_find_helper(node->left, key);
89c132
<       return tree_find(node->right, key);
---
>       return tree_find_helper(node->right, key);
diff tree3/tree.h tree4/tree.h
3,4c3,4
<  *  (store arbitrary 'things' using void*)
<  * 
---
>  *  (version 4: separate tree from treenode)
>  *
12c12
< typedef struct treenode tree_t;  // opaque to users of the module
---
> typedef struct tree tree_t;  // opaque to users of the module
16c16
< /* create a new tree for the given key and data;
---
> /* Create a new (empty) tree;
19c19
< tree_t *tree_new(const int key, void *data);
---
> tree_t *tree_new(void);
21,25c21,22
< /* insert into the given tree, or NULL to start a new tree;
<  * wherein the item is described by a key and some data,
<  * and the tree is provided as a pointer to its root;
<  * providing a NULL root creates a new tree and returns it.
<  * the key should not be tree_t_KEY_NOT_FOUND.
---
> /* Insert item into the given tree; NULL tree is ignored.
>  * The item is described by a key and some data.
27c24
< tree_t *tree_insert(tree_t *root, const int key, void *data);
---
> void tree_insert(tree_t *tree, const int key, void *data);
29,30c26,27
< /* return the data associated with the given key;
<  * return tree_t_KEY_NOT_FOUND if key is not in tree.
---
> /* Return the data associated with the given key;
>  * return NULL if tree is NULL or if key is not found.
32c29
< void *tree_find(tree_t *root, const int key);
---
> void *tree_find(tree_t *tree, const int key);
diff tree3/treetest.c tree4/treetest.c
12,18d11
< /* Use a global variable to hold the root of tree;
<  * it does not need to be global, in this simple example,
<  * but here it serves an example of a global variable.
<  * We normally try hard to avoid using globals.
<  */
< tree_t *root;
< 
20a14
>   tree_t *tree;		      // the tree
22a17,18
>   tree = tree_new();
> 
24,32c20,29
<   root = tree_insert(root, 3, datastring);
<   root = tree_insert(root, 4, datastring);
<   root = tree_insert(root, 1, datastring);
<   root = tree_insert(root, 5, datastring);
<   root = tree_insert(root, 6, datastring);
<   root = tree_insert(root, 2, datastring);
<   root = tree_insert(root, 8, datastring);
<   root = tree_insert(root, 7, datastring);
<   root = tree_insert(root, 0, datastring);
---
>   tree_insert(tree, 3, datastring);
>   tree_insert(tree, 4, datastring);
>   tree_insert(tree, 1, datastring);
>   tree_insert(tree, 5, datastring);
>   tree_insert(tree, 6, datastring);
>   tree_insert(tree, 2, datastring);
>   tree_insert(tree, 8, datastring);
>   tree_insert(tree, 7, datastring);
>   tree_insert(tree, 0, datastring);
>   tree_insert(NULL, 0, datastring); // should be ignored
34,35c31,32
<   printf("find %d returns %s\n", 4, tree_find(root, 4));
<   printf("find %d returns %s\n", 5, tree_find(root, 5));
---
>   printf("find %d returns %s\n", 4, tree_find(tree, 4));
>   printf("find %d returns %s\n", 5, tree_find(tree, 5));
38,39c35,37
<   root = tree_insert(root, 5, "new string");
<   printf("find %d returns %s\n", 5, tree_find(root, 5));
---
>   tree_insert(tree, 5, "new string");
>   printf("find %d returns %s\n", 5, tree_find(tree, 5));
>   printf("find null returns %s\n", tree_find(NULL, 5));