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 =\ )

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]

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.

>>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

---

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.

>>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;
}

---

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