Saturday, March 26, 2011

Binary-tree test

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>

/* 
 Helper function that allocates a new node with the given data and NULL left and right pointers. 
*/ 


typedef struct node {
 int data;
 struct node *left;
 struct node *right;
} NodeT;


NodeT* NewNode(int data);
void BTreeLog(const char *fmt, ...);

typedef int (*BTreeCompFunc)(NodeT* node, void *data);

NodeT* BTreeNewNode(int data) 
{ 
 NodeT* node = (NodeT*)malloc(sizeof(NodeT));    // "new" is like "malloc" 
 node->data = data; 
 node->left = NULL; 
 node->right = NULL;
 BTreeLog("BTreeNewNode: new node=0x%X, data=%d\n", node, data);
    return(node); 
} 
     

void BTreeLog(const char *fmt, ...)
{
#ifdef __ENABLE_LOG__  
 char buf[256];
 va_list ap;
 int n;
 
 va_start(ap, fmt);
 n = vsnprintf(buf, sizeof(buf), fmt, ap);
 printf("%s", buf);
 va_end(ap);
#endif 
}


int BTreeCompare(NodeT* node, void *data)
{
 if (*((int*)data) < node->data)
  return -1;
 if (*((int*)data) > node->data)
  return 1;
 return 0;
}  
/* 
  Give a binary search tree and a number, BTreeInserts a new node 
  with the given number in the correct place in the tree. 
  Returns the new root pointer which the caller should 
  then use (the standard trick to avoid using reference 
  parameters). 
*/ 

NodeT* BTreeInsert(NodeT* node, int data, BTreeCompFunc comp)
{ 
 // 1. If the tree is empty, return a new, single node 
 if (NULL == node) 
 { 
  BTreeLog("New Entry: %d\n", data);
  return BTreeNewNode(data); 
    } 
 else { 
  // 2. Otherwise, recur down the tree 
     if (comp(node, &data) == -1) {
   /*BTreeLog("BTreeInsert: left; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->left = BTreeInsert(node->left, data, comp); 
  } 
  else {
   /* 
   BTreeLog("BTreeInsert: right; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->right = BTreeInsert(node->right, data, comp);
  } 
 }
 return(node); // return the (unchanged) node pointer 
}


void BTreeDeleteAll(NodeT* pNode)
{
 if (pNode)
 {
  if (pNode->left)
  {
   BTreeDeleteAll(pNode->left);
  } 
  if (pNode->right)
  {
   BTreeDeleteAll(pNode->right);
  } 
  BTreeLog("BTreeDeleteAll: pNode=0x%X, data=%d\n", pNode, pNode->data);
  free(pNode);
  //pNode->left = NULL;
  //pNode->right = NULL;
 }
}

NodeT *BTreeSearch(NodeT* pNode, int data, BTreeCompFunc comp)
{
 int cmp; 
 if (pNode) {
  cmp = comp(pNode, &data); 
  if (cmp == 0)
   return pNode;
  else 
  if (cmp == -1)
  {
   /* data < pnode->data */
   pNode = BTreeSearch(pNode->left, data, comp); 
  }
  else {
   pNode = BTreeSearch(pNode->right, data, comp);
  } 
 }
 //BTreeLog("Comp...\n");
 return pNode;
}


int main(int argc, char *argv[])
{
 NodeT* root = NULL;
 NodeT* node;
 unsigned int n,i;
 int data1, data2;
 unsigned int count;

 srand(time(NULL));
 BTreeLog("BTree demo\n");
 n = rand() % 100;
 root = BTreeInsert(root, n, BTreeCompare);
 data2 = 4750;
 n = 10000000;
 for (i=0, count=0; i<n; i++)
 {
  data1 = rand()%n;
  /* insert unique entry */
  if (BTreeSearch(root, data1, BTreeCompare) == NULL) {
   BTreeInsert(root, data1, BTreeCompare);
   count++;
  } 
 }
 BTreeInsert(root, data2, BTreeCompare);
 printf("Just inserted %d entries into Binary-tree\n", count+1);
 node = BTreeSearch(root, data2, BTreeCompare);
 printf("\n\n\n\n");
 if (node) {
  printf("!!!!!!!!!!!!!!!!!!!!!!!!Found node=0x%X for data=%d\n", node, data2);
 }
 printf("\n\n\n\n");
 BTreeDeleteAll(root);
}

No comments:

Post a Comment