You've got several good questions, all at the heart of a binary tree. If we can help you to understand the answers, you'll have gone far in understanding binary trees.

The first step is to understand exactly what a binary tree is. It is simply a storage mechanism whereby the contents are stored in a sorted order. Where the values are stored in memory is meaningless, as data is located by address, not position within a list or array.

The rules of a binary tree are simple. For any node in the tree, all nodes that are accessed from the left child of the node have a value less than the current node. Similarly, all nodes that are accessed from the right child of the node are larger than the node.

One possible binary tree (albeit a lousy one) is actually just a linked list. It you were to construct a binary tree so that all nodes had a value for the left child of NULL, the construct

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Is a "tree" where all of the right children point to the next higher valued node.

But that's a lousy tree. A much better one is balanced, where the middle value serves as the root node and all of the branches of the tree have the same number of nodes on each side. That tree would look like this:

4

/ \

2 6

/ \ / \

1 3 5 7

Note that the basic rule applies. All nodes to the left of 4 are smaller than 4. All nodes left of 2 are smaller than 2. All nodes to the right of 4 are larger than 4, etc.

Traversing the tree is very easy, but recursive. You absolutely must understand recursion to manage the tree.

To traverse a tree, you recursively follow the left child of a node, then the right node. Since this is recursive, you don't go left then right, you go left of current, left of next, left of next, until no more left children remain. THEN you traverse the right children. Note that after the recursion gets to a right child it may be necessary to traverse ITS left children.

The code is easy. :)

InOrder (node *P)

{

if (*P == NULL)

return;

if (P->Left)

InOrder (P->Left);

print ("Current node value is %d\n", P->Value);

if (P->Right)

InOrder (P->Right);

}

To print the list in reverse order, you simply move the *print* statement to after the check for the right child. :)

And of course, you don't have to print anything. If you're looking for a node, you'd return a flag to indicate that the node was found.

Deleting a node is a bit trickier. You MUST know the parent node. In the tree above, to delete the node with a value of 2, you'd make either of the child nodes of 2 the left child of of it's parent (4). The other child of 2 would then have to be linked to the bottom of the chain that was linked to (4).

That would leave you with a tree that looked like this:

4

/ \

3 6

/ / \

1 5 7

or:

4

/ \

1 6

\ / \

3 5 7

The trees look different, but they are equivalent.

Now. I'm sure that there are a ton more questions, so fire away.

Kent