Binary tree

This is a discussion on Binary tree within the C Programming forums, part of the General Programming Boards category; Hello everyone, again trying to help a friend who wrote this code to make a binary tree. It should then ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    24

    Binary tree

    Hello everyone, again trying to help a friend who wrote this code to make a binary tree. It should then show the biggest and smallest number in the tree then delete them and show the last content. Unfortunately this code gives a segmentation error - if anyone could find the problem I would be really grateful. *C only, no C++ please*

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct treeNode
    {
       int data;
       struct treeNode *leftNodePtr;
       struct treeNode *rightNodePtr;
    }TreeNode;
    
    typedef TreeNode *TreeNodePtr;
    
    void addNode(TreeNodePtr *treePtr, int value);
    void writeInceasingOrder(TreeNodePtr treePtr);
    TreeNodePtr findSmallest(TreeNodePtr treePtr);
    TreeNodePtr deleteSmallest(TreeNodePtr treePtr);
    
    int main(void)
    {
       int integer;
       TreeNodePtr rootPtr = NULL;
    
       printf("Please enter the integer to add tree");
       printf("('-1' to conclude): ");
       scanf("%d",&integer);
       while(integer != -1)
       {
          addNode(&rootPtr, integer);
          printf("add new integer to tree");
          printf("('-1' to conclude): ");
          scanf("%d",&integer);
       }
    
       writeInceasingOrder(rootPtr);
       printf("\ndeleted: %d", (deleteSmallest(rootPtr)->data));
       writeInceasingOrder(rootPtr);
    
       return 0;
    }
    
    void addNode(TreeNodePtr *treePtr, int value)
    {
       if(*treePtr == NULL)
       {
          *treePtr = (TreeNodePtr)malloc(sizeof(TreeNode));
    
          if(*treePtr != NULL)
          {
    	 (*treePtr)->data = value;
    	 (*treePtr)->leftNodePtr = NULL;
    	 (*treePtr)->rightNodePtr = NULL;
          }
          else
          {
    	 printf("not enough memory");
          }
       }
       else
       {
          if(value < (*treePtr)->data)
          {
    	 addNode(&((*treePtr)->leftNodePtr), value);
          }
          else
          {
    	 if(value > (*treePtr)->data)
    	 {
    	    addNode(&((*treePtr)->rightNodePtr), value);
    	 }
    	 else
    	 {
    	    printf("this number was added earlier");
    	 }
          }
       }
    }
    
    void writeInceasingOrder(TreeNodePtr treePtr)
    {
       if(treePtr != NULL)
       {
          writeInceasingOrder(treePtr->leftNodePtr);
          printf("%3d", treePtr->data);
          writeInceasingOrder(treePtr->rightNodePtr);
       }
    }
    
    TreeNodePtr deleteSmallest(TreeNodePtr treePtr)
    {
       TreeNodePtr tempPtr;
       if(treePtr->leftNodePtr != NULL && treePtr->rightNodePtr)
       {
          tempPtr = findSmallest(treePtr->rightNodePtr);
          treePtr->data = tempPtr->data;
          treePtr->rightNodePtr = deleteSmallest(treePtr->rightNodePtr);
          return treePtr;
       }
    }
    
    TreeNodePtr findSmallest(TreeNodePtr treePtr)
    {
       if(treePtr == NULL)
       {
          return NULL;
       }
       else
       {
          if(treePtr->leftNodePtr == NULL)
          {
    	 return treePtr;
          }
          else
          {
    	 return findSmallest(treePtr->leftNodePtr);
          }
       }
    }

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    The deleteSmallest function doesn't check if treePtr is NULL before dereferencing it.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    24
    Thanks, hopefully changing that will fix it.

  4. #4
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    The problem lies in the deleteSmallest function. It doesn't look really good.

    So, let's say you want a function who returns the node with the smallest value of a tree and remove that node from that tree (without freeing the memory associated with it). One way to achieve this would be
    1. Find the node with the smallest value of the whole tree. Store the adress of that node somewhere.
    2. Remove the node from the tree. Since the "smallest node" doesn't have a left child, all you need to do is "parent(smallestNode)->left = smallestNode->right" (in the case smallestNode == root, you'll have a problem of removing the node from the tree since you won't be able to update the root for the new root (root->right). You'll have to change your function prototype if you wan't to resolve this issue).


    Note that if you want to use this solution, you'll have to implement a "parent" function, who returns a pointer to the parent of a node.

    Also, you could also find a recursive solution. But again, i would highly recommend changing your function prototype before, maybe for something like this
    Code:
    TreeNodePtr deleteSmallest(TreeNodePtr treePtr, TreeNodePtr *smallestNode);
    // Should return the root of the tree after removing the smallest node from it.
    
    // Example on how to call the function:
    TreeNodePtr smallestNode;
    // ...
    rootPtr = deleteSmallest(rootPtr, &smallestNode);
    or

    Code:
    TreeNodePtr deleteSmallest(TreeNodePtr *treePtr);
    // Should return the smallest node of the tree
    
    // Example on how to call the function:
    TreeNodePtr smallestNode;
    // ...
    smallestNode = deleteSmallest(&rootPtr);
    If you choose the 2nd solution, you should also choose a non-recursive solution, it will be more straightforward to implement. And if you would like to see some code, i guess i could throw you some.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10: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, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21