1.1 --- a/src/bst.c	Wed Sep 26 13:11:09 2012 -0500
     1.2 +++ b/src/bst.c	Wed Sep 26 18:59:22 2012 -0500
     1.3 @@ -4,10 +4,16 @@
     1.4  #include "bst.h"
     1.5  
     1.6  // Private functions.
     1.7 -void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data));
     1.8 +void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));
     1.9 +void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));
    1.10 +void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data));
    1.11 +
    1.12 +void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n));
    1.13 +
    1.14  void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
    1.15  void * bst_node_minimum(struct bst_node * node);
    1.16  void * bst_node_maximum(struct bst_node * node);
    1.17 +void bst_node_free(struct bst_node * node);
    1.18  
    1.19  ////////////////////////////////////////////////////////////////////////////////
    1.20  struct bst *
    1.21 @@ -37,13 +43,21 @@
    1.22     if (0 < bst->size)
    1.23        {
    1.24        // Walk the tree and delete the nodes.
    1.25 -      // This will cause memory leaks, so hopefully the user has already
    1.26 +      // This may cause memory leaks, so hopefully the user has already
    1.27        // emptied the tree.
    1.28 +      bst_node_walk_postorder(bst->root, bst_node_free);
    1.29        }
    1.30     free(bst);
    1.31     }
    1.32  
    1.33  ////////////////////////////////////////////////////////////////////////////////
    1.34 +void
    1.35 +bst_node_free(struct bst_node * node)
    1.36 +   {
    1.37 +   free(node);
    1.38 +   }
    1.39 +
    1.40 +////////////////////////////////////////////////////////////////////////////////
    1.41  void *
    1.42  bst_insert(struct bst * bst, void * data)
    1.43     {
    1.44 @@ -79,6 +93,7 @@
    1.45     else
    1.46        p->right = new;
    1.47  
    1.48 +   bst->size++;
    1.49     return new->data;
    1.50     }
    1.51  
    1.52 @@ -89,17 +104,68 @@
    1.53     if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
    1.54        return;
    1.55  
    1.56 -   bst_node_walk_inorder(bst->root, op);
    1.57 +   bst_data_walk_inorder(bst->root, op);
    1.58     }
    1.59  
    1.60  ////////////////////////////////////////////////////////////////////////////////
    1.61 -void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data))
    1.62 +void bst_walk_postorder(struct bst * bst, void (*op)(void * data))
    1.63 +   {
    1.64 +   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
    1.65 +      return;
    1.66 +
    1.67 +   bst_data_walk_postorder(bst->root, op);
    1.68 +   }
    1.69 +
    1.70 +////////////////////////////////////////////////////////////////////////////////
    1.71 +void bst_walk_preorder(struct bst * bst, void (*op)(void * data))
    1.72 +   {
    1.73 +   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
    1.74 +      return;
    1.75 +
    1.76 +   bst_data_walk_preorder(bst->root, op);
    1.77 +   }
    1.78 +
    1.79 +////////////////////////////////////////////////////////////////////////////////
    1.80 +void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data))
    1.81     {
    1.82     if (NULL != node)
    1.83        {
    1.84 -      bst_node_walk_inorder(node->left, op);
    1.85 +      bst_data_walk_inorder(node->left, op);
    1.86        op(node->data);
    1.87 -      bst_node_walk_inorder(node->right, op);
    1.88 +      bst_data_walk_inorder(node->right, op);
    1.89 +      }
    1.90 +   }
    1.91 +
    1.92 +////////////////////////////////////////////////////////////////////////////////
    1.93 +void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data))
    1.94 +   {
    1.95 +   if (NULL != node)
    1.96 +      {
    1.97 +      bst_data_walk_postorder(node->left, op);
    1.98 +      bst_data_walk_postorder(node->right, op);
    1.99 +      op(node->data);
   1.100 +      }
   1.101 +   }
   1.102 +
   1.103 +////////////////////////////////////////////////////////////////////////////////
   1.104 +void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data))
   1.105 +   {
   1.106 +   if (NULL != node)
   1.107 +      {
   1.108 +      op(node->data);
   1.109 +      bst_data_walk_preorder(node->left, op);
   1.110 +      bst_data_walk_preorder(node->right, op);
   1.111 +      }
   1.112 +   }
   1.113 +
   1.114 +////////////////////////////////////////////////////////////////////////////////
   1.115 +void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n))
   1.116 +   {
   1.117 +   if (NULL != node)
   1.118 +      {
   1.119 +      bst_node_walk_postorder(node->left, op);
   1.120 +      bst_node_walk_postorder(node->right, op);
   1.121 +      op(node);
   1.122        }
   1.123     }
   1.124  
   1.125 @@ -188,3 +254,109 @@
   1.126        return NULL;
   1.127     return node->data;
   1.128     }
   1.129 +
   1.130 +////////////////////////////////////////////////////////////////////////////////
   1.131 +struct bst_iterator * bst_begin(struct bst * bst)
   1.132 +   {
   1.133 +   if ( (NULL == bst) || (NULL == bst->root) )
   1.134 +      return NULL;
   1.135 +
   1.136 +   struct bst_node * min = bst->root;
   1.137 +   while (min->left)
   1.138 +      min = min->left;
   1.139 +
   1.140 +   struct bst_iterator * it = malloc(sizeof(struct bst_iterator));
   1.141 +   if (NULL == it)
   1.142 +      return NULL;
   1.143 +
   1.144 +   it->bst = bst;
   1.145 +   it->curr = min;
   1.146 +   return it;
   1.147 +   }
   1.148 +
   1.149 +////////////////////////////////////////////////////////////////////////////////
   1.150 +struct bst_iterator * bst_end(struct bst * bst)
   1.151 +   {
   1.152 +   if ( (NULL == bst) || (NULL == bst->root) )
   1.153 +      return NULL;
   1.154 +
   1.155 +   struct bst_node * max = bst->root;
   1.156 +   while (max->right)
   1.157 +      max = max->right;
   1.158 +
   1.159 +   struct bst_iterator * it = malloc(sizeof(struct bst_iterator));
   1.160 +   if (NULL == it)
   1.161 +      return NULL;
   1.162 +
   1.163 +   it->bst = bst;
   1.164 +   it->curr = max;
   1.165 +   return it;
   1.166 +   }
   1.167 +
   1.168 +////////////////////////////////////////////////////////////////////////////////
   1.169 +struct bst_iterator * bst_next(struct bst_iterator * it)
   1.170 +   {
   1.171 +   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
   1.172 +      return NULL;
   1.173 +
   1.174 +   if (NULL == it->curr->right)
   1.175 +      {
   1.176 +      struct bst_node * p = it->curr;
   1.177 +      it->curr = it->curr->parent;
   1.178 +      while ( (NULL != it->curr) && (p == it->curr->right) )
   1.179 +	 {
   1.180 +	 p = it->curr;
   1.181 +	 it->curr = it->curr->parent;
   1.182 +	 }
   1.183 +
   1.184 +      if (it->curr == NULL)
   1.185 +	 return NULL;
   1.186 +      }
   1.187 +   else
   1.188 +      {
   1.189 +      struct bst_node * min = it->curr->right;
   1.190 +      while (min->left)
   1.191 +	 min = min->left;
   1.192 +      it->curr = min;
   1.193 +      }
   1.194 +   return it;
   1.195 +   }
   1.196 +
   1.197 +////////////////////////////////////////////////////////////////////////////////
   1.198 +struct bst_iterator * bst_prev(struct bst_iterator * it)
   1.199 +   {
   1.200 +   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
   1.201 +      return NULL;
   1.202 +
   1.203 +   if (NULL == it->curr->left)
   1.204 +      {
   1.205 +      struct bst_node * p = it->curr;
   1.206 +      it->curr = it->curr->parent;
   1.207 +      while ( (NULL != it->curr) && (p == it->curr->left) )
   1.208 +	 {
   1.209 +	 p = it->curr;
   1.210 +	 it->curr = it->curr->parent;
   1.211 +	 }
   1.212 +
   1.213 +      if (it->curr == NULL)
   1.214 +	 return NULL;
   1.215 +      }
   1.216 +   else
   1.217 +      {
   1.218 +      struct bst_node * max = it->curr->left;
   1.219 +      while (max->right)
   1.220 +	 max = max->right;
   1.221 +      it->curr = max;
   1.222 +      }
   1.223 +   return it;
   1.224 +   }
   1.225 +
   1.226 +////////////////////////////////////////////////////////////////////////////////
   1.227 +void * bst_value(struct bst_iterator * it)
   1.228 +   {
   1.229 +   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
   1.230 +      return NULL;
   1.231 +
   1.232 +   return it->curr->data;
   1.233 +   }
   1.234 +

     2.1 --- a/src/bst.h	Wed Sep 26 13:11:09 2012 -0500
     2.2 +++ b/src/bst.h	Wed Sep 26 18:59:22 2012 -0500
     2.3 @@ -20,6 +20,12 @@
     2.4     bool (*eq)(void * a, void * b);
     2.5     };
     2.6  
     2.7 +struct bst_iterator
     2.8 +   {
     2.9 +   struct bst * bst;
    2.10 +   struct bst_node * curr;
    2.11 +   };
    2.12 +
    2.13  struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
    2.14  void bst_delete(struct bst * bst);
    2.15  
    2.16 @@ -32,5 +38,14 @@
    2.17  void * bst_maximum(struct bst * bst);
    2.18  
    2.19  void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
    2.20 +void bst_walk_preorder(struct bst * bst, void (*op)(void * data));
    2.21 +void bst_walk_postorder(struct bst * bst, void (*op)(void * data));
    2.22 +
    2.23 +
    2.24 +struct bst_iterator * bst_begin(struct bst * bst);
    2.25 +struct bst_iterator * bst_end(struct bst * bst);
    2.26 +struct bst_iterator * bst_next(struct bst_iterator * it);
    2.27 +struct bst_iterator * bst_prev(struct bst_iterator * it);
    2.28 +void * bst_value(struct bst_iterator * it);
    2.29  
    2.30  #endif

     3.1 --- a/src/bst_test.c	Wed Sep 26 13:11:09 2012 -0500
     3.2 +++ b/src/bst_test.c	Wed Sep 26 18:59:22 2012 -0500
     3.3 @@ -22,6 +22,11 @@
     3.4     printf("%d\n", *((int *) d) );
     3.5     }
     3.6  
     3.7 +void free_data(void * d)
     3.8 +   {
     3.9 +   free(d);
    3.10 +   }
    3.11 +
    3.12  int main(int argc, char ** argv)
    3.13     {
    3.14     struct bst * bst = bst_new(le, eq);
    3.15 @@ -31,6 +36,8 @@
    3.16        exit(EXIT_FAILURE);
    3.17        }
    3.18  
    3.19 +   ////////////////////////////////////////
    3.20 +   printf ("======================\nGenerating\n");
    3.21     //srand(time());
    3.22     int * ip;
    3.23     for (int i = 0 ; i < MAX_NUMS ; ++i)
    3.24 @@ -43,16 +50,20 @@
    3.25  	 }
    3.26  
    3.27        *ip = rand();
    3.28 -
    3.29 +      printf("%d\n", *ip);
    3.30        if (NULL == bst_insert(bst, ip))
    3.31  	 {
    3.32  	 perror("bst_insert");
    3.33  	 exit(EXIT_FAILURE);
    3.34  	 }
    3.35        }
    3.36 +   printf ("======================\n");
    3.37  
    3.38 +
    3.39 +   ////////////////////////////////////////
    3.40     bst_walk_inorder(bst, print);
    3.41  
    3.42 +   ////////////////////////////////////////
    3.43     int i = 1;
    3.44     int * p = (int *) bst_search(bst, &i);
    3.45     if (NULL == p)
    3.46 @@ -87,5 +98,36 @@
    3.47     else
    3.48        printf("%d MAXIMUM\n", *max);
    3.49  
    3.50 +   ////////////////////////////////////////
    3.51 +   printf("\n\nWalking inorder with iterators\n");
    3.52 +   struct bst_iterator * it = bst_begin(bst);
    3.53 +   if (NULL == it)
    3.54 +      {
    3.55 +      perror("bst_begin");
    3.56 +      exit(EXIT_FAILURE);
    3.57 +      }
    3.58 +   do
    3.59 +      printf("%d\n", *((int *) bst_value(it)));
    3.60 +   while (bst_next(it));
    3.61 +   free(it);
    3.62 +
    3.63 +
    3.64 +   ////////////////////////////////////////
    3.65 +   printf("\n\nWalking reverse inorder with iterators\n");
    3.66 +   it = bst_end(bst);
    3.67 +   if (NULL == it)
    3.68 +      {
    3.69 +      perror("bst_end");
    3.70 +      exit(EXIT_FAILURE);
    3.71 +      }
    3.72 +   do
    3.73 +      printf("%d\n", *((int *) bst_value(it)));
    3.74 +   while (bst_prev(it));
    3.75 +   free(it);
    3.76 +
    3.77 +
    3.78 +   bst_walk_inorder(bst, free_data);
    3.79 +   bst_delete(bst);
    3.80 +
    3.81     exit(EXIT_SUCCESS);
    3.82     }