Typically, a binary search tree is implimented as a collection of 0 or more classes or structures called nodes. Each node stores a single value from the set of values stored in the tree. Each node also stores two pointers to other nodes that are "farther down the tree". One or both of these node pointers may be NULL, indicating that they do not refer to a node. One of the pointers refer to a node that has a larger value than the current node and the other pointer refers to a node that has a smaller value than the current node.
For a binary tree that stores ints a node might be declared as a structure like
Node
{
int Value;
Node *NextPtr; // -> node with higher value.
Node *PrevPtr; // -> node with lower value.
};
The nodes in a binary tree are organized in a manner that is similar to a family tree. At the top is the "root node" This is the node that is the key to obtaining access to all the other nodes in the tree. The root node points to 0, 1, or 2 other nodes. The node that is refered to by the "NextPtr", if there is one, will contain a larger value than the root node. The node that is refered to by the "PrevPtr" will contain a smaller value than the root node. Then these node will each have 0, 1, or 2 child nodes below them and so on.
If we draw the tree, so that the node that has the lesser value is shown below and to the left and the node with the higer value is shown below and to the right. Then an example binary tree might look like
5
/ \
2 7
/ \ / \
1 3 6 9
As you can see, for any node, the pointer that leads down and to the left leads to a lower value and the pointe that leads down and to the right leads to a higher value. Note that the 4 lowest nodes have no children nodes. This means that there pointers are set to NULL. Note that the reason this is called a "binary tree" is that at each node the tree "splits" into two branches (up to two branches).
In order to find a value in the tree, you start with the root node (you start with the root node for everything.) Then you follow this procedure for ever node you encounter in the search (starting with the root node beign the first node you encouter.) If the node stores the value you want, then you've found the value. If not, if the value to be found is larger than the value in the node, look to see if there is a "next node" specified by the "nextPtr". If so go to that node. If not, the search is done and failed to find the value. If the value to be found is lowe than the value in the node, then look to see if there is "previous node" specified by the "PrevPtr", If so, go to that node. If not, the search is done and failed to find a value.
Questions?
0
Featured Post
Here at Experts Exchange, we strive to give members the best experience. Help us improve the site by taking this survey today! (Bonus: Be entered to win a great tech prize for participating!)
continues.