Create cormen_binary_tree.cpp

BST
Create a Binary Search Tree, which supports the following operations.
• insert(tree, element) – adds the node specified by element (which contains
the data) into the BST specified by tree.
• search(tree, key) – searches for the data specified by key in the BST specified
by tree.
• findMin(tree) – retrieves the smallest data in the BST specified by tree.
• findMax(tree) – retrieves the largest data in the BST specified by tree.
• predecessor(tree, element) – retrieves the inorder-predecessor of the
node specified by element in the BST specified by tree.
• successor(tree, element) – retrieves the inorder-successor of the node
specified by element in the BST specified by tree.
• delete(tree, element) – removes the node specified by element from the
BST specified by tree.
Input - Output Format
The input consists of multiple lines, each one containing either one or two integers.
The first integer in the line can be 0, 1, 2, 3, 4, 5, 6, or 7 and each one has its own
meaning:
• The integer 0 means stop the program.
• The integer 1 means, create a node which contains the next integer from
the input as the data part, and then, insert this node into the BST. In this
case, the next integer (>= 0) is given on the same line as the 1, separated
by a space.
•The integer 2 means, search for the key specified by the next integer from
the input, in the BST. In this case, the next integer (>= 0) is given on the
same line as the 2, separated by a space. If the search is successful,
output “FOUND”. Otherwise, output “NOT FOUND”.
The integer 3 means find and output the minimum number in the BST.
Print “NIL” if the BST is empty.
The integer 4 means find and output the maximum number in the BST.
Print “NIL” if the BST is empty.
The integer 5 means find and output the inorder-predecessor of the data
specified by the next integer from the input. In this case, the next integer
(>= 0) is given on the same line as the 5, separated by a space. Output
“NIL”, if the data exists in the tree, but there is no inorder-predecessor for
the data. Output “NOT FOUND”, if the data is not present in the tree.
The integer 6 means find and output the inorder-successor of the data
specified by the next integer from the input. In this case, the next integer
(>= 0) is given on the same line as the 6, separated by a space. Output
“NIL”, if the data exists in the tree, but there is no inorder-successor for
the data. Output “NOT FOUND”, if the data is not present in the tree.
The integer 7 means delete the data specified by the next integer in the
input from the BST, if present. In this case, the next integer (>= 0) is given
on the same line as the 7, separated by a space. (Here, the data to be
deleted is guaranteed to be present in the BST).



sample input:
1 25
1 13
1 50
1 45
1 55
1 18
5 13
6 13
5 18
6 18
5 25
6 25
5 45
6 45
5 50
6 50
5 55
6 55
7 55
7 13
7 25
3
4
5 18
6 18
5 45
6 45
5 50
6 50
7 45
7 50
7 18
3
4
1 90
3
4
0