Advanced Structured Programming and Algorithms
A Binary Search Tree (BST) for a set of input can have many different forms, and the structure of the tree you get depends on the sequence of data from the input array.
The tree is built by calling the treeInsert method on each of the item you encounter in the array. For example, if your input array is
A = {10, 8,2,5}
Then, you would call treeInsert(T,10), treeInsert(T, 8), treeInsert(T, 2), and treeInsert(T, 5). This should place all the elements in the proper position in the BST.
NOTE: You MUST use the pseudocodes given in the class to develop your program (i.e., No Googling and copying codes from a ready-made BST program. They might do it in some different ways).
1. Create a class called Node. This class should have the followings:
- A data member to hold a key that is an int value
- It has data members that point to parent, left, and right nodes
- A constructor that takes the key value
2. Create a binary search tree class. This class should have the followings:
- A data member that points to the root node of the tree
- A constructor that takes an int[] array as argument and build the BST from the array (each node is an object created from class Node in problem 1)
- An iterativeSearch method that can be used to search for a node with the given key value
- A insert method to insert a node into the tree
- A successor method that finds the successor for a given node
- A minimum method that finds the minimum value in any of the subtrees, given a node x (not just from the root and not just the minimum of the entire input array)
- An inorderTreeWalk method that can be used to display the results from the in-order tree walk, starting from any given node
3. Add the main method inside of the binary search tree class to test your codes. Your tests should do the followings:
- Use the input array A = {15, 6, 18, 3, 7, 17, 20, 2, 4, 12, 8}
- Build the binary search tree for this input
- Do the inorderTreeWalk to display the results (this should show the sorted list)
- Use the minimum method to find the minimum, starting from the node with key = 18
- Find the successor to the root node, and display the result on the screen
- Find the successor to node with key = 12, and display the result on the screen The output from running the program should display on the screen as follows:
Inorder tree walk: 2 3 4 6 7 8 12 15 17 18 20
Minimum from node.key = 18 is [the result] Successor to the root node is [the result] Successor to the node.key = 12 is [the result]