Thread: Binary Tree, couple questions

Code:

/*
    File: btree.c
    Date: 3/10/05
    Info: Binary tree implementation.
    
    Sean
*/


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

/* verbose output */
#define DEBUG

/* structures */
struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct btree {
    struct node *root;
    struct node *cur;
    struct node *prev;
};

/* prototypes */
int btree_initialize(int data, struct btree *tree);
int btree_insert(int data, struct btree *tree);
struct node * btree_find(int data, struct btree *tree);
struct node * btree_find_node(int data, struct node *cur);
void btree_delete(struct btree *tree);
void btree_delete_all(struct node *cur);
void btree_print(struct btree *tree);
void btree_print_all(struct node *cur);



int main(void)
{
    struct btree tree;
    
    btree_initialize(10, &tree); /* initialize root node to 10 */
    
    /* insert nodes */    
    btree_insert(5,&tree);
    btree_insert(6,&tree);
    btree_insert(14,&tree);
    btree_insert(14,&tree);
    
    /*
        Current tree should look something like this:

                        10
                     /      \
                    5       14
                   / \     /  \
                  N   6    N   N
      
    */
    
    /* check the tree for certain values */
    printf("%s\n",btree_find(4, &tree) ? "Item found!" : "Item not found.");
    printf("%s\n",btree_find(87, &tree) ? "Item found!" : "Item not found.");
    
    btree_print(&tree); /* print the tree */
    
    btree_delete(&tree); /* delete the tree */
    
    getchar();
    
    return 0;
}


/*
    First function that should be called on the binary tree. Basically
    defines the root node and sets its value to 'data'. The function
    returns -1 if initialization fails and 0 if it is successful.
*/
int btree_initialize(int data, struct btree *tree)
{
    struct node *tmp = NULL;
    
    tmp = malloc(sizeof(struct node));
    if (!tmp) {
        #ifdef DEBUG
            puts("btree_initialize: unable to allocate memory");
        #endif
        
        return -1;
    }

    tmp->data = data;
    tmp->left = NULL;
    tmp->right = NULL;
    
    tree->root = tmp;
    tree->cur = tree->root;
    
    #ifdef DEBUG
        puts("btree_initialize: root node initialized");
    #endif
    
    return 0;
}


/*
    This function searches the entire binary for the value 'data'.
    A pointer to the node containing 'data' is returned if it is
    found. Otherwise, NULL is returned.
*/
struct node * btree_find(int data, struct btree *tree)
{
    struct node *ret = NULL;
    
    /* just make sure tree->cur points to root for search */
    tree->cur = tree->root;

    #ifdef DEBUG
        printf("btree_find: trying to find %d\n",data);
    #endif
    
    /* function that does the actual search */
    ret = btree_find_node(data, tree->cur);
    
    #ifdef DEBUG
        if (ret) {
            printf("btree_find: found %d\n",data);
        } else {
            printf("btree_find: did not find %d\n",data);
        }
    #endif
    
    return ret;
}


/*
    This function searches the tree recursively for 'data'. It 
    traverses to the left until it reaches a leaf, then it traverses
    right. All functions will return once 'data' is found. Otherwise,
    execution continues until the tree has been fully searched.
*/
struct node * btree_find_node(int data, struct node *cur)
{
    struct node *ret = NULL;
    
    if (cur) { /* node is not NULL */
        if (cur->data == data) {
            return cur;
        }
        else { /* continue searching */
            #ifdef DEBUG
                puts("btree_find_node: searching left");
            #endif
            ret = btree_find_node(data,cur->left);
            if (ret != NULL) { /* node has been found */
                return ret;
            }
            
            #ifdef DEBUG
                puts("btree_find_node: searching right");
            #endif
            ret = btree_find_node(data,cur->right);
            if (ret != NULL) { /* node has been found */
                return ret;
            }
            
            return NULL;
        }
    }
    else {
        return NULL;
    }
}


/*
    Inserts a node containing 'data'. If 'data' already exists in the tree,
    no new node will be added and 1 will be returned. Otherwise, 'data' will
    be added to the left or right depending on how it compares to the value
    of the current node. On successful insertion, 0 is returned.
*/
int btree_insert(int data, struct btree *tree)
{   
    if (tree->cur) { /* node is not NULL */
        if (data < tree->cur->data) { /* insert to the left */
            tree->prev = tree->cur;
            tree->cur = tree->cur->left;
            #ifdef DEBUG
                puts("btree_insert: traversing left");
            #endif
            return btree_insert(data, tree);
        }
        else if (data > tree->cur->data) { /* insert to the right */
            tree->prev = tree->cur;
            tree->cur = tree->cur->right;
            #ifdef DEBUG
                puts("btree_insert: traversing right");
            #endif
            return btree_insert(data, tree);
        }
        else { /* data already in tree, don't insert */
            #ifdef DEBUG
                puts("btree_insert: data already in tree");
            #endif
            tree->cur = tree->root;
            return 1;
        }
    }
    else { /* node is NULL, so we add */
        struct node *tmp = NULL;
        
        tmp = malloc(sizeof(struct node));
        if (!tmp) {
            #ifdef DEBUG
                puts("btree_insert: unable to allocate memory");
            #endif
            return -1;
        }
        
        tmp->data = data;
        tmp->left = NULL;
        tmp->right = NULL;
        
        tree->cur = tmp;
        
        /* add new node to correct side of parent node */
        if (data < tree->prev->data) {
            tree->prev->left = tree->cur;
        }
        else {
            tree->prev->right = tree->cur;
        }
        
        tree->cur = tree->root; /* reset tree->cur for next insert */
        
        #ifdef DEBUG
            printf("btree_insert: node added with value %d",data);
        #endif
        
        return 0;
    }
}


/*
    Prints out the entire binary tree, one node per line. First, all of the nodes
    to the left are covered, then all of the nodes to the right of the current
    node.
*/
void btree_print(struct btree *tree)
{
    btree_print_all(tree->root);
}


/*
    Prints the entire list.
*/
void btree_print_all(struct node *cur)
{
    if (cur) { /* node is not NULL */
        btree_print_all(cur->left);
        btree_print_all(cur->right);
        
        printf("%d ",cur->data);
    }
}

/*
    Deletes the entire binary tree, freeing all allocated memory.
*/
void btree_delete(struct btree *tree)
{
    /* delete the entire tree */
    btree_delete_all(tree->root);
    
    tree->root = NULL;
    tree->cur = NULL;
    tree->prev = NULL;
}


/*
    This function deletes the entire binary tree by traversing each path and 
    deleting each leaf.
*/
void btree_delete_all(struct node *cur)
{
    if (cur) { /* current node isn't NULL */
        btree_delete_all(cur->left);
        btree_delete_all(cur->right);
        
        /* once both of these have returned, we know */
        /* that we have reached a leaf.              */
        free(cur);
    }
}

At the bottom of my code, I delete the entire tree. I was wondering if I'm doing this currently. Should I be passing a double pointer to btree_delete_all()? I tried searching the tree immediately after deleting the list, and the tree appeared to have been deleted. I just wanna double check

Also, is there a better way of printing out the tree? As it is, the function will just go down to to the furthest node and prints from the bottom up (kinda).

Any other suggestions/tips?

Thanks

This is a good place to use recursive functions. To print the contents in order, you might want to do something like:

Code:

void printbst(struct node* rootPtr)
{
  if(rootPtr != NULL)
  {
    printbst(rootPtr->leftPtr);
    printf(" %d\n", rootPtr->data);
    printbst(rootPtr->rightPtr);
  }
}

the free function is really similar, but instead of a print statement in the middle, use a free() call at the bottom.

Code:

void freenodes(struct node* rootPtr)
{
  if(rootPtr != NULL)
  {
    freenodes(rootPtr->leftPtr);
    freenodes(rootPtr->rightPtr);
    free(rootPtr);
  }
}

Should do the trick.

Originally Posted by scoobasean

I didn't think about printing it out that way, thanks

And I think my delete code is pretty much the same as yours

Three common ways to print out binary trees are as follows:

Preorder Traversal:

Code:

void PrintPreorder(struct node* root)
{
  if(root)
  {
    printf(" %d\n", root->data);
    PrintPreorder(root->left);
    PrintPreorder(root->right);
  }
}

In-order Traversal

Code:

void PrintInorder(struct node* root)
{
  if(root)
  {
    PrintInorder(root->left);
    printf(" %d\n", root->data);
    PrintInorder(root->right);
  }
}

Postorder Traversal

Code:

void PrintPostorder(struct node* root)
{
  if(root)
  {
    PrintPostorder(root->left);
    PrintPostorder(root->right);
    printf(" %d\n", root->data);
  }
}