Description
A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.
Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined.
For example, if a node with key 6 needs to be inserted into the following BST
the BST will become
Implementation of the BST Data Structure
There are two approaches to BST implementation: array and linked list.
1. Array:
An approach to storing a BST is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1, respectively. Using this technique, the tree below
would be stored as follows
2. Linked list:
We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.
REQUIREMENTS:
Implement the destructor, insert(), search(), and height() member functions of both the Array_ BST and List_ BST classes.
Input
There are four kinds of commands:
- “I A”: insert a node with int value A(A>0) into the BST
- “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
- “P”: show the current content of the BST in Level-order.
- “H”: print the BST’s height.
Each command is followed by a new line character.
Input terminated by EOF.
Output
The output shows the result (in both Array and LinkedList method) of each command.
When the BST is empty, you don’t need to print anything except a new line character.
But there's already a new line character in the main function, so you don't have to do anything.