Description
Definition of Binary Search Trees
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
B. Implementation of the BST Data Structure
There are two approaches to BST implementation: array and linked list, you only need to implement the linked list.
1.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 constructor, insert(), remove(), search() and createLeaf()member functions of List_ BST classes.
Note:
1. This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
2. For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
HINT1:
You don't have to take care of the height changing in insert() and remove(), the function height2() will take care of it.
HINT2:
There are three possible cases to remove a node from BST, after removing it will still maintain a BST:
1.Node to be deleted is leaf: Simply remove from the tree.
2.Node to be deleted has only one child: Copy the child to the node and delete the child
3.Node to be deleted has two children: Find node A with max key value in the left tree of the deleted node or minimim key value in the right tree of the deleted node, copy A to the deleted node. Then, replace A by it's child. In this test, please choose node A by finding minimum key value in the right tree.
For example, we remove the node with key = 4, node A's key = 5
the BST will become
Input
There are five kinds of commands:
- “I A”: insert a node with int value A(A>0) into the BST
- “R A”:remove a node with int value A(A>0) into the BST, value A must appear in the tree.
- “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.
You can still get two ACs without doing remove() function.
Output
The output shows the result 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.