Description
In this problem, you are asked to implement a linked list based binary search tree. In addition, you are also asked to implement a linked list based stack, so that the program can use a stack to print its corresponding binary search tree in the depth-first manner.
A. Implementation of the BST Data Structure using a 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.
For example,
The linked list will be
B. The relationship between a BST and its corresponding Stack
For printing the tree in the depth-first manner, the ListBST::printDFS needs to push and pop the tree nodes to/from a stack.
Example:
initially,
after push(root),
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. You are asked to implement
- void ListBST::insert(const int &key)
- bool ListBST::search(const int &key) const
- void Stack::push(ListNode *p)
- ListNode *Stack::pop()
3. ListNode is a ListBST’s node and Element is a Stack’s node whose data is a pointer to ListNode.
4. 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.
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.
- “D”: show the current content of the BST by DFS.
- “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 of each command.
When the BST is empty, you don’t need to print anything except a new line character.