Description
Binary Search Tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
We only implement the insertion, and reverse-level traversal methods of BST. Completing two existed classes Node and BinarySearchTree.
Node
Public Variables:
- data(int) int data stored in a node.
- left(Node*) pointer points to the left child node.
- right(Node*) pointer points to the right child node.
- parent(Node*) pointer points to the parent node.
Constructors:
- Node(int d) – Should initalize the data (data) store in a node to d, and initialize left, right and parent pointer to nullptr.
BinarySearchTree:
Public Variables:
- root(Node*) should point to the root element of the BST.
note: the root element is the first element inserted in the BST.
Constructors:
- The default constructor – Should initialize root to nullptr.
Public Methods:
- void Insert(int i) – Should create a Node(i), and insert it into the BST. Shown as below figure.
- void ReverseLevelOrderTraversal(Node* r) – Traverse each level of the tree and print all the node’s data stored in BST from left to right in reverse-level order.
note: No need to separate each of two data. Print ”/* empty */” if the BST is empty (root == nullptr).
For Example:
The reverse-level-order traversal is: 1->4->7->2->5->3.
hint: Queue or Vector is helpful for this implementation.
Also, to_string(int), and reverse(string.begin(), string.end()) may help.
/* You Don’t Need to Implement the Below Method */
- void InOrderTraversal() – Print all the node’s data stored in BST in order (LNR). If the list is empty print ”/* empty */”.
note: if insertion is implmented correctly, it will automatically print the data in ascending order. Also, you may use this function to check and debug.
Input
There are three kinds of input command.
insert i – Call Insert(i).
reverselevel – Call ReverseLevelOrderTraversal(root).
/* The Below Command Would Not in the Test Case Only for Debugging */
print – Call InOrderTraversal(root).
Output
No need to handle output. Check main.cpp for more details.