Added a find function.

Tom


git-svn-id: http://svn.cactuscode.org/flesh/trunk@858 17b73243-c579-4c4c-a9d2-2d5706c11dac

2 files changed, 44 insertions, 1 deletions

diff --git a/src/util/BinaryTree.c b/src/util/BinaryTree.c
index 3ca9d87f..e57ab153 100644
--- a/src/util/BinaryTree.c
+++ b/src/util/BinaryTree.c
@@ -67,7 +67,7 @@ t_tree *TreeStoreData(t_tree *root, t_tree *subtree, void *data, int (*compare)(
     }
     else if(order > 0) 
     {
-      root = TreeStoreData(subtree, subtree->right, data, compare);
+      subtree = TreeStoreData(subtree, subtree->right, data, compare);
     }
     else if(order==0)
     {
@@ -198,6 +198,32 @@ void TreePrintNodes(t_tree *root, int depth, void (*print_node)(void *, int))
   }
 }
 
+
+t_tree *TreeFindNode(t_tree *root, void *data, int (*compare)(const void *, const void *))
+{
+  int order;
+
+  t_tree *node;
+
+  /* Go down left or right branch. */
+  if((order = compare(data, root->data)) < 0)
+  {
+    node = TreeFindNode(root->left, data, compare);
+  }
+  else if(order > 0) 
+  {
+    node = TreeFindNode(root->right, data, compare);
+  }
+  else if(order==0)
+  {
+    /* Found it. */
+    node = root;
+  }
+
+  return node;
+}  
+
+
 /* Stuff to test the routines. */
 
 /*#define TEST_BinaryTree*/
@@ -230,6 +256,7 @@ int main(void)
   t_infodata infodata;
   char instring[500];
   char *newstring;
+  t_tree *node;
 
   infodata.i=0;
 
@@ -254,6 +281,19 @@ int main(void)
 
   TreePrintNodes(root, 0, (void (*)(void *, int))print_node);
 
+  printf("String to find ? ");
+  scanf("%s", instring);
+
+  node = TreeFindNode(root, instring, (int (*)(const void *, const void *))strcmp);
+
+  if(node)
+  {
+    printf("Found a node, node->data is %s\n", node->data);
+  }
+  else
+  {
+    printf("Unable to find node with %s\n", instring);
+  }
 
   return 0;
 }
diff --git a/src/util/BinaryTree.h b/src/util/BinaryTree.h
index 8be9a956..f4dce162 100644
--- a/src/util/BinaryTree.h
+++ b/src/util/BinaryTree.h
@@ -14,6 +14,7 @@ typedef struct T_TREE
 {
   struct T_TREE *left;
   struct T_TREE *right;
+  struct T_TREE *next;
 
   void *data;
 } t_tree;
@@ -32,6 +33,8 @@ int TreeTraversePostorder(t_tree *root, int (*process)(void *, void *), void *in
 
 void TreePrintNodes(t_tree *root, int depth, void (*print_node)(void *, int));
 
+t_tree *TreeFindNode(t_tree *root, void *data, int (*compare)(const void *, const void *));
+
 #ifdef _cplusplus
 	   }
 #endif