Thread: Binary Tree, couple questions

  1. #1
    Registered User
    Join Date
    Dec 2002
    Posts
    56

    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
    Last edited by scoobasean; 03-11-2005 at 02:09 AM.

  2. #2
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    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.
    straight off the heap

  3. #3
    Registered User
    Join Date
    Dec 2002
    Posts
    56
    Quote Originally Posted by dinjas
    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);
      }
    }
    I didn't think about printing it out that way, thanks

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

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    Quote 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);
      }
    }
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  3. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM