#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);
}
