Thread: Need help with Binary Tree!!!

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    18

    Angry Need help with Binary Tree!!!

    Ok the commands are:
    a or A followed by a number to add to the tree (ex: a123)(finished)
    d or D followed by number to delete 1st node from tree that matches(ex: d123)(not finished)
    s or S followed by number to delete all nodes in tree that matches(ex: s123)(not finished)
    p or P to print tree
    e or E to exit

    So far I have the print and add function working. The tree is preloaded with an array with a value greater than insert left, less or equal insert right.

    If I print the initial list it works. If I hit print again I get some funky numbers. It looks as if the numbers are being duplicated in the print. Whats wrong. Can't figure out what is happening. Thanks.





    Code:
    #include <stdio.h>
    #define SIZE 15
    #define ARRAYSIZE 80
    #define PRINT 15
    
    
    
    
    //*************STRUCTS*****************
    struct treeNode
    {
         int data;
         struct treeNode *rChild;
         struct treeNode *lChild;
    };
    
    //**************************************//
    
    //***********FUNCTION PROTOTYPES********//
    struct treeNode *makeTreeNode(int number);
    void readArrayIntoTree(int *treeArray, struct treeNode **rootPtr);
    void insertInTree(struct treeNode **rootPtr, int number);
    void printTraversal(struct treeNode *rootPtr);
    void preOrderTraversal(struct treeNode *rootPtr);
    void inOrderTraversal(struct treeNode *rootPtr);
    void postOrderTraversal(struct treeNode *rootPtr);
    //******END OF FUNCTION PROTOTYPES******//
    
    
    //************************MAIN************************//
    int main()
    {
         
         struct treeNode *rootPtr = '\0';
         
         int number;
         int index = 1;               
         int treeArray[15] ={60,75,40,32,55,80,70,74,68,69,85,90,84,65,28};
         
         char ch; 
         char selection;     
         char inputArray[256];
         char numberArray[256];
    
         printf("-->[E] or [e] will exit the program<--\n\n"); 
         
         do
         {    
              
              readArrayIntoTree(treeArray, &rootPtr);
              
              printf("Enter a command---> ");
              gets(inputArray);
         
              selection = inputArray[0];
         
              while(inputArray[index] != '\0' && index < ARRAYSIZE)
              {
                   ch = inputArray[index];
                   numberArray[index-1] = ch;
                   index++;
              }
              numberArray[index-1];     
              number = atoi(numberArray);  
    
              switch(selection)
              {
                   case 'a':
                        insertInTree(&rootPtr, number);
                        break;
                   case 'A':
                        insertInTree(&rootPtr, number);                    
                        break;
                   case 'd':
                        break;
                   case 'D':
                        break;
                   case 's':
                        break;
                   case 'S':
                        break;
                   case 'p':
                        printTraversal(rootPtr);               
                        break;
                   case 'P':
                        printTraversal(rootPtr);                    
                        break;
                   case 'e':
                        break;
                   case 'E':
                        break;
                   default:
                        printf("\n\n*****You have entered an invalid command [a/A, d/D, s/S, p/P, e/E]*****\n\n\n");
              }
              
         }while(selection != 'e' && selection != 'E');  
            
       
         printf("\n\n\n");
         system("PAUSE");
         
         return 0;
         
    }
    //************END OF MAIN**************//
    
    
    //**********MAIN PROTOTYPED FUNCTIONS**//
    struct treeNode *makeTreeNode(int number)
    {
         struct treeNode *newTreePtr = '\0'; 
       
         newTreePtr = (struct treeNode*)malloc(sizeof(struct treeNode));
         newTreePtr->lChild = '\0';
         newTreePtr->rChild = '\0';
         newTreePtr->data = number;
         
         return newTreePtr;
    }
    
    void readArrayIntoTree(int *treeArray, struct treeNode **rootPtr)
    {    
              
         int index;    
         
         for(index=0;index<SIZE;index++)
         {
              insertInTree(rootPtr, (*(treeArray + index)));
         }     
              
    }
    
    void insertInTree(struct treeNode **rootPtr, int number)
    {
         
         struct treeNode *newTreePtr = '\0';
         struct treeNode *currTreePtr = '\0';
         struct treeNode *insertLocationPtr = '\0';
    
         newTreePtr = makeTreeNode(number);
        
         if(*(rootPtr) == '\0')
         {
              *rootPtr = newTreePtr;    
         }
        
         else
         {
              currTreePtr = *rootPtr;
                  
              while(currTreePtr != '\0')
              {
                   insertLocationPtr = currTreePtr;
             
                   if(newTreePtr->data > currTreePtr->data)
                   {
                        currTreePtr = currTreePtr->lChild;
                   }
                   else
                   {
                        currTreePtr = currTreePtr->rChild;
                   }
              }
                   
              if(newTreePtr->data > insertLocationPtr->data)
              {
                   insertLocationPtr->lChild = newTreePtr;
              }
                   
              else
              {
                   insertLocationPtr->rChild = newTreePtr;
              }
         }       
    }
    
    
    
    void preOrderTraversal(struct treeNode *rootPtr)
    { 
         static int post_counter = 1;
         
         if(rootPtr != '\0')
         {    
              printf("%-3i",rootPtr->data);
              post_counter++;
              
              if(post_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 post_counter = 1;
              }                    
              preOrderTraversal(rootPtr->lChild);
              preOrderTraversal(rootPtr->rChild);     
         } 
    }
    
    void inOrderTraversal(struct treeNode *rootPtr)
    { 
         static int post_counter = 1;
    
         if(rootPtr != '\0')
         {    
              inOrderTraversal(rootPtr->lChild);
              printf("%-3i",rootPtr->data);          
              post_counter++;
              
              if(post_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 post_counter = 1;
              }         
              inOrderTraversal(rootPtr->rChild);      
         } 
    }
    
    void postOrderTraversal(struct treeNode *rootPtr)
    { 
         static int post_counter = 1;
    
         if(rootPtr != '\0')
         {    
              postOrderTraversal(rootPtr->lChild);
              postOrderTraversal(rootPtr->rChild);
              printf("%-3i",rootPtr->data);
              post_counter++;
              
              if(post_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 post_counter = 1;
              }          
         } 
    }
    
    void printTraversal(struct treeNode *rootPtr)
    {
         
         if(rootPtr == '\0')
         {
              printf("*****No nodes to print*****");
         }
         else
         {
              printf("\n\t\tThe preorder traversal is:\n\n");
              printf("\t\t\t");
              preOrderTraversal(rootPtr);
              printf("\n\n");
         
              printf("\t\tThe inorder traversal is:\n\n");
              printf("\t\t\t");     
              inOrderTraversal(rootPtr);
              printf("\n\n");
         
              printf("\t\tThe postorder traversal is:\n\n");
              printf("\t\t\t");     
              postOrderTraversal(rootPtr);
              printf("\n\n");
         }
         
    }
    
    //**********END OF MAIN FUNCTIONS**********//

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > struct treeNode *rootPtr = '\0';
    Pointers are conventionally initialised by saying
    struct treeNode *rootPtr = NULL;

    > gets(inputArray);
    NEVER use gets(), it is a totally unsafe function.
    http://faq.cprogramming.com/cgi-bin/...&id=1043284351

    > numberArray[index-1];
    This does nothing, though I suspect you meant to append a \0, with
    numberArray[index-1] = '\0';

    It is also unnecessary, since you could have done
    Code:
              selection = inputArray[0];
              number = atoi(&inputArray[1]);
    > switch(selection)
    You could have done
    switch( toupper(selection) )
    and remove half your case statements.

    You could also have done
    case 'a':
    case 'A':
    insertInTree(&rootPtr, number);
    break;

    > Whats wrong. Can't figure out what is happening. Thanks.
    My guess is these not being 1 on the 2nd call to print
    static int post_counter = 1;

    You should pass the 'depth' (if that's what it is) as a parameter, because this local variable is initialised only once during the life of the program.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    18
    Thanks! I took your advice which made it a lot better. As far as resetting the static int I made the function return a pointer to a static int, returned the address to the int and reset it to 1 when I exited the function call in printTraversal function. I changed gets() to fgets(inputArray,256,stdin) I hope that is right, it seems to work. Need to work on a single delete function and multi delete function and then I am done. Any suggestions on a delete function? Not sure how to search through the tree. What things to I need to keep track of? Also the teacher wants the immediate predecessor as the replacement. Thanks again!



    Code:
     
    
    
    #include <stdio.h>
    #define SIZE 15
    #define ARRAYSIZE 80
    #define PRINT 10
    
    
    
    
    //*************STRUCTS*****************
    struct treeNode
    {
         int data;
         struct treeNode *rChild;
         struct treeNode *lChild;
    };
    
    //**************************************//
    
    //***********FUNCTION PROTOTYPES********//
    struct treeNode *makeTreeNode(int number);
    void readArrayIntoTree(int *treeArray, struct treeNode **rootPtr);
    void insertInTree(struct treeNode **rootPtr, int number);
    void printTraversal(struct treeNode *rootPtr);
    static int *preOrderTraversal(struct treeNode *rootPtr);
    static int *inOrderTraversal(struct treeNode *rootPtr);
    static int *postOrderTraversal(struct treeNode *rootPtr);
    //void deleteFirstNode(struct treeNode **rootPtr, int number);
    //******END OF FUNCTION PROTOTYPES******//
    
    /*    //working on function
    void deleteFirstNode(struct treeNode **rootPtr, int number)
    {
         struct treeNode *deleteNodePtr = '\0';
         struct treeNode *parentPtr = '\0';
         
         deleteNodePtr = *rootPtr;
         parentPtr = *rootPtr;
    
         
         while(deleteNodePtr != '\0' && deleteNodePtr->data != number)
         {
              parentPtr->data = deleteNodePtr->data;
              
              if(number <= deleteNodePtr->data)
              {
                   deleteNodePtr = deleteNodePtr->lChild;
              }
              else
              {
                   deleteNodePtr = deleteNodePtr->rChild;
              }
         }
         if(deleteNodePtr == '\0')
         {
              printf("\n*****Node value does not exist in the tree*****\n\n");
              
              
         }
    
    }
    
    */
    
    
    
    //************************MAIN************************//
    int main()
    {
    
         struct treeNode *rootPtr = '\0';
         
    
         int number;
         int index = 1;               
         int treeArray[15] ={60,75,40,32,55,80,70,74,68,69,85,90,84,65,28};
         
         char ch; 
         char selection;     
         char inputArray[256];
         char numberArray[256];
    
         printf("-->[E] or [e] will exit the program<--\n\n"); 
         readArrayIntoTree(treeArray, &rootPtr);     
         
         do
         {          
              
              printf("Enter a command---> ");
              fgets(inputArray,256,stdin);
         
              selection = inputArray[0];
              number = atoi(&inputArray[1]); 
    
    
              switch(toupper(selection))
              {
                   case 'A':
                        insertInTree(&rootPtr, number);                    
                        break;
                   case 'D':
                        deleteFirstNode(&rootPtr, number);
                        break;
                   case 'S':
                        break;
                   case 'P':
                        printTraversal(rootPtr);                    
                        break;
                   case 'E':
                        printf("\n\n\n");                   
                        break;
                   default:
                        printf("\n\n*****You have entered an invalid command [a/A, d/D, s/S, p/P, e/E]*****\n\n\n");
              }
              
         }while(selection != 'e' && selection != 'E');  
           
    
         system("PAUSE");
         
         return 0;
         
    }
    //************END OF MAIN**************//
    
    
    //**********MAIN PROTOTYPED FUNCTIONS**//
    struct treeNode *makeTreeNode(int number)
    {
         struct treeNode *newTreePtr = '\0'; 
       
         newTreePtr = (struct treeNode*)malloc(sizeof(struct treeNode));
         newTreePtr->lChild = '\0';
         newTreePtr->rChild = '\0';
         newTreePtr->data = number;
         
         return newTreePtr;
    }
    
    void readArrayIntoTree(int *treeArray, struct treeNode **rootPtr)
    {    
              
         int index;    
         
         for(index=0;index<SIZE;index++)
         {
              insertInTree(rootPtr, (*(treeArray + index)));
         }     
              
    }
    
    void insertInTree(struct treeNode **rootPtr, int number)
    {
         
         struct treeNode *newTreePtr = '\0';
         struct treeNode *currTreePtr = '\0';
         struct treeNode *insertLocationPtr = '\0';
    
         newTreePtr = makeTreeNode(number);
        
         if(*(rootPtr) == '\0')
         {
              *rootPtr = newTreePtr;    
         }
        
         else
         {
              currTreePtr = *rootPtr;
                  
              while(currTreePtr != '\0')
              {
                   insertLocationPtr = currTreePtr;
             
                   if(newTreePtr->data > currTreePtr->data)
                   {
                        currTreePtr = currTreePtr->lChild;
                   }
                   else
                   {
                        currTreePtr = currTreePtr->rChild;
                   }
              }
                   
              if(newTreePtr->data > insertLocationPtr->data)
              {
                   insertLocationPtr->lChild = newTreePtr;
              }
                   
              else
              {
                   insertLocationPtr->rChild = newTreePtr;
              }
         }       
    }
    
    
    
    static int *preOrderTraversal(struct treeNode *rootPtr)
    {
         
         static int pre_counter = 1;
         
         if(rootPtr != '\0')
         {    
              printf("%-5i",rootPtr->data);
              pre_counter++;
              
              if(pre_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 pre_counter = 1;
              }                    
              preOrderTraversal(rootPtr->lChild);
              preOrderTraversal(rootPtr->rChild);
         }     
         return &pre_counter;
    
    }
    
    static int *inOrderTraversal(struct treeNode *rootPtr)
    { 
      
         static int in_counter = 1;
          
         if(rootPtr != '\0')
         {    
              inOrderTraversal(rootPtr->lChild);
              printf("%-5i",rootPtr->data);          
              in_counter++;
              
              if(in_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 in_counter = 1;
              }         
              inOrderTraversal(rootPtr->rChild);      
         }
         return &in_counter; 
    }
    
    
    static int *postOrderTraversal(struct treeNode *rootPtr)
    { 
    
         static int post_counter = 1;
         
         if(rootPtr != '\0')
         {    
              postOrderTraversal(rootPtr->lChild);
              postOrderTraversal(rootPtr->rChild);
              printf("%-5i",rootPtr->data);
              post_counter++;       
              
              if(post_counter > PRINT)
              {
                 printf("\n\t\t\t");
                 post_counter = 1;
    
              }          
         }
         return &post_counter; 
    }
    
    void printTraversal(struct treeNode *rootPtr)
    {
         
         int *reset;
         
         if(rootPtr == '\0')
         {
              printf("*****No nodes to print*****");
         }
         else
         {
    
              printf("\n\t\tThe preorder traversal is:\n\n");
              printf("\t\t\t");
              reset = preOrderTraversal(rootPtr);
              *reset = 1;
              printf("\n\n");
              
              printf("\t\tThe inorder traversal is:\n\n");
              printf("\t\t\t");
              reset = inOrderTraversal(rootPtr);
              *reset = 1;
              printf("\n\n");
         
              printf("\t\tThe postorder traversal is:\n\n");
              printf("\t\t\t");
              reset = postOrderTraversal(rootPtr);
              *reset = 1;
              printf("\n\n");
         }
         
    }
    
    //**********END OF MAIN FUNCTIONS**********//
    Last edited by pityocamptes; 04-14-2006 at 05:11 PM.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    18
    Here is my delete node function. It works but I was wondering if there is any way to clean it up, seems a little long


    Code:
     
    int deleteFirstNode(struct treeNode **rootPtr, int number)
    {
         struct treeNode *deleteNodeParentPtr = '\0';
         struct treeNode *deleteNodePtr = '\0';
         struct treeNode *replacementNodePtr = '\0';
         struct treeNode *replacementParentNodePtr = '\0';
         int flag = 0;
         
         
              
         if(*rootPtr == '\0')
         {
              printf("\n*****The list is empty, no nodes left to delete*****\n\n");
         }
         else
         {
              deleteNodeParentPtr = *rootPtr;
              deleteNodePtr = deleteNodeParentPtr;
                
                   //search function           
              while(deleteNodePtr != '\0' && deleteNodePtr->data != number)
              {
                   deleteNodeParentPtr = deleteNodePtr;
                            
                   if(number > deleteNodePtr->data)
                   {
                        deleteNodePtr = deleteNodePtr->lChild;
                   }
                   else
                   {
                        deleteNodePtr = deleteNodePtr->rChild;
                   }
                   
              }          
                   //node not found in tree
              if(deleteNodePtr == '\0')
              {
                   flag = 1; //value does not exist
    
              }
                             //node has no children
              else if(deleteNodePtr->lChild == '\0' && deleteNodePtr->rChild == '\0')
              {
                   if(deleteNodePtr == *rootPtr)
                   {
                        *rootPtr = '\0';
                   }
                   else
                   {
                        if(deleteNodeParentPtr->rChild == deleteNodePtr)
                        {
                             deleteNodeParentPtr->rChild = '\0';
                            
                        }                    
                        else
                        {
                             deleteNodeParentPtr->lChild = '\0';
                                               
                        }
                   }                    
              }
                   //delete node has one right child or the node is the root with no right child
              else if(deleteNodePtr->rChild == '\0')
              {
                   if(deleteNodeParentPtr->rChild == deleteNodePtr)
                   {
                        deleteNodeParentPtr->rChild = deleteNodePtr->lChild;
                          
                   }
                   else
                   {
                        deleteNodeParentPtr->lChild = deleteNodePtr->lChild;
               
                   }
                   
                   if(deleteNodePtr->rChild == '\0' && deleteNodePtr == *rootPtr)
                   {
                        replacementNodePtr = deleteNodePtr->lChild;
                        replacementParentNodePtr = '\0';
                   
                             //node has two children
                        while(replacementNodePtr->rChild != '\0')
                        {
                             replacementParentNodePtr = replacementNodePtr;
                             replacementNodePtr = replacementNodePtr->rChild;
                        }
                        deleteNodePtr->data = replacementNodePtr->data;
                   
                        if(replacementParentNodePtr == '\0')
                        {
                             deleteNodePtr->lChild = replacementNodePtr->lChild;
                        }                    
                   
                        else 
                        {
                             replacementParentNodePtr->rChild = replacementNodePtr->rChild;
    
                        }                
                   }                   
              }
                   //delete node has one left child or the node is the root with no left child
              else if(deleteNodePtr->lChild == '\0')
              {
                   if(deleteNodeParentPtr->rChild == deleteNodePtr)
                   {
                        deleteNodeParentPtr->rChild = deleteNodePtr->rChild;
                       
                   }
                   else
                   {
                        deleteNodeParentPtr->lChild = deleteNodePtr->rChild;
                           
                   }
                   
                   if(deleteNodePtr->lChild == '\0' && deleteNodePtr == *rootPtr)
                   {
                        replacementNodePtr = deleteNodePtr->rChild;
                        replacementParentNodePtr = '\0';
                   
                             //node has two children
                        while(replacementNodePtr->lChild != '\0')
                        {
                             replacementParentNodePtr = replacementNodePtr;
                             replacementNodePtr = replacementNodePtr->lChild;
                        }
                        deleteNodePtr->data = replacementNodePtr->data;
                   
                        if(replacementParentNodePtr == '\0')
                        {
                             deleteNodePtr->rChild = replacementNodePtr->rChild;
                        }                    
                   
                        else 
                        {
                             replacementParentNodePtr->lChild = replacementNodePtr->rChild;
    
                        }                
                   }
              }
              
              else
              {         //delete node has two children - replacement node needs to be found
                   replacementNodePtr = deleteNodePtr->rChild;
                   replacementParentNodePtr = '\0';
                   
                             //node has two children
                   while(replacementNodePtr->lChild != '\0')
                   {
                        replacementParentNodePtr = replacementNodePtr;
                        replacementNodePtr = replacementNodePtr->lChild;
                   }
                   deleteNodePtr->data = replacementNodePtr->data;
                   
                   if(replacementParentNodePtr == '\0')
                   {
                        deleteNodePtr->rChild = replacementNodePtr->rChild;
                   }                    
                   
                   else 
                   {
                        replacementParentNodePtr->lChild = replacementNodePtr->rChild;
    
                   }
                   free(replacementNodePtr);                              
              }
         }
         
         return(flag);
    }
    Last edited by pityocamptes; 04-17-2006 at 11:34 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM