Tree Search using C/C++.

In the binary tree used to store a file, all the left descendants of a node with key have keys that are less than key, and all the right descendants have keys that are greater than or equal to key. The inorder traversal of such a binary tree yields the file in ascending key order.

Such a tree may also be used as a binary search tree. Using binary tree notation, the algorithm for searching for the key key in such a tree is as follows ( here we assume that each node contains four fields: k, which holds the record’s key value, r, which holds the record itself, and left and right, which are pointers to the subtrees).

The efficiency of the search process can be improved by using a sentinel, as in sequential searching. A sentinel node, with a separate external pointer pointing to it, remains allocated with the tree. All left or right tree pointers that do not point to another tree node now point to this sentinel node instead of equaling null. When a search is performed, the argument key is first inserted into the sentinel node, thus guaranteeing that it will be located in the tree. This enables the header of the search loop to be written while(key != key(p)) without the risk of an infinite loop. After leaving the loop, if p equals the external sentinel pointer, the search is unsuccessful; otherwise, p points to the desired node.


Source Code


SHARE Tree Search using C/C++.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *