Binary Tree Sort

This is a discussion on Binary Tree Sort within the C++ Programming forums, part of the General Programming Boards category; Ok basically i have this: Code: struct Node { int value; Node *left; Node *right; }; void Insert(Node *BTree, int ...

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    14

    Binary Tree Sort

    Ok basically i have this:

    Code:
    struct Node
    {
        int value;
        Node *left;
        Node *right;
    };
    
    void Insert(Node *BTree, int temp)
    {
         if (BTree->value == NULL)
             BTree->value = temp;
         else if (temp < BTree->value)
             Insert(BTree->left, temp);
         else
             Insert(BTree->right, temp);
    }
    could some1 help me a little with basic binary trees... sorting, deleting. Ive looked some up and they havnt helped. (Edit was for a tab then enter... I hate that tab moves straight to post =\ )
    Last edited by BakAttack; 02-05-2003 at 02:38 AM.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    This is either a case in point of how undependable the internet really is or it is a devious way of getting us to do your work. Either way I'd recommend looking up sorting on a search engine. You will find all the help you need (with source).

    [edit]
    just so people don't think I'm crazy, the post was fixed after my remarks were made.
    [/edit]
    Last edited by master5001; 02-05-2003 at 02:41 AM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Deleting isn't too hard either. If the deleted node has no children, just delete it. If it has one child, then splice it out (make the parent point to the deleted nodes child). If it has two children, then you need to find the succesor (the next highest number compared to the deleted node), splice the succesor out of its location since it can only have at most one child, then replace the deleted node with its value.

  4. #4
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>could some1 help me a little with basic binary trees... sorting, deleting.
    Sorting is a piece of cake, a binary search tree is sorted by default :-)

    Deleting is harder, you have to consider three different situations. The first is deleting a link with no children, easy. The second is deleting a link with one child, just replace that link with the child. The hardest is when a link has two children, set the left child's right child to be the right child and replace the link with the left child:
    Code:
    Start:
    a
     \
      d
     / \
    b   e
    
    Set b->left to e
    a
     \
      d
     / \
    b   ~
     \
      e
    
    Set d to b
    a
     \
      b
     / \
    ~   e
    *Cela*

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Don't you have to find the succesor or the predeccesor, not just the left child when the deleted node has two children? Otherwise if the left child already has a right child then things get messed up.

  6. #6
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>Don't you have to find the succesor or the predeccesor, not just the left child when the deleted node has two children?
    Yep, you're right, but it gets a lot more confusing when you throw all that in :-)
    Code:
    void delete_node(Node *tree, int item)
    {
      Node **save, *walk;
    
      save = &tree;
      walk = tree;
    
      /* Find the link */
      while (1)
      {
        if (walk == 0)
        {
          return;
        }
        else if (item == walk->value)
        {
          break;
        }
        else if (item > walk->value)
        {
          save = &walk->right;
          walk = walk->right;
        }
        else
        {
          save = &walk->left;
          walk = walk->left;
        }
      }
    
      /* Kill it */
      if (walk->right == 0)
      {
        *save = walk->left;
      }
      else
      {
        Node *next_right = walk->right;
    
        if (next_right->left == 0)
        {
          next_right->left = walk->left;
          *save = next_right;
        }
        else
        {
          Node *next_left = next_right->left;
    
          while (next_left->left != 0)
          {
            next_right = next_left;
            next_left = next_right->left;
          }
    
          next_right->left = next_left->right;
          next_left->left = walk->left;
          next_left->right = walk->right;
    
          *save = walk;
        }
      }
    
      delete walk;
    }
    *Cela*

  7. #7
    Registered User
    Join Date
    Dec 2002
    Posts
    29
    When you delete a node with two children you have two good options:

    1. replace the node with the smallest node in it's right subtree

    2. replace the node with the largest node in it's left subtree

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 11:43 AM
  2. Delete all from a Binary Tree
    By Silvio in forum C Programming
    Replies: 5
    Last Post: 04-25-2009, 07:23 AM
  3. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 08:08 AM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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