The null links in a binary tree can be used to facilitate non-recursive traversal of the tree. For example, if we set each null right link ( except for the right link of the rightmost node) to point to its successor under inorder traversal, we have a right threaded binary tree. We can now do a non recursive inorder traversal of the tree in the following way:
Start from the root and go to the leftmost node by tracing the left links. Visit the node and go to its successor via its right link. If the right link is a thread link, it gives the successor; otherwise, move as far left as possible to locate the successor. Terminatewhen a null right link is reached.
This project is to modify the BinaryTree class to accommodate right-threaded binary trees. You need to add a flag variable to each node to indicate if a right link is a thread, write a method to turn an ordinary binaray tree into a right-threaded binary tree and write another mothod to demonstrate non-recursive inorder traversal.
Note that in a right-threaded binary tree, a node that has no right child and is itself the root of a left subtree should have its right link point to its parent. On the other hand, a node that has no right child and is itself the root of a right subtree should have its right link point to the parent of its highest ancestor. The parent of the root is set to null.
You will be given a test data file that contains several sequences of numbers. The numbers in each sequence are on the same line and separated by a space. You program should reach each sequence, build an ordinary binary search tree using simple insertion, right-threaded the tree and show each thread (i.e. if there is a thread from node 17 to node 41, then produce an output saying something like 17 -> 41), and print the numbers using non-recursive inorder traversal. Specifically, the main method must look like:
BinaryTree T; While( not end of input ) { Build an ordinary binary search tree T; right-threaded T and show each thread; print numbers in T via non-recursive inorder traversal; }
The method for right-threading takes a pointer to a non-empty node N and a pointer to its parent P (or the parent of its highest ancestor as defined above). It starts with N being the root node of an ordinary binary search tree and P being null. If the current node has left child, use this left node and the current node to make a recursive call. If the current node has a right child, use this right node and P to make a recursive call. Otherwise, set its right pointer to P. Please provide two different implementations of the two methods you write.