Programming Assignment #3
Threaded Binary Search Trees (Threaded-BST)
Recall in our model of Binary Search Trees (BSTs), the leaf nodes all
have null pointers. This seems like a waste of space. It has been
suggested that these null pointers can be used to reference something
useful. In a threaded binary search tree, the right
null pointers of a node are used to point to the node's inorder
successor and the left null pointers of nodes are employed to point to
the node's inorder predecessor. One advantage threaded threaded BST is
that one can do an inorder
traversal of the tree without using recursion.
We define a class as follows:
public String data;
public Node left;
public Node right;
public boolean isRightThread;
public boolean isLeftThread;
We need the boolean variables to distinguish a thread
from a non-thread link.
What to do:
There are three different versions of this program you may choose from:
There are two versions of this program:
No threads and all output is done recursively. This will be worth 30 out of 50 points. This will be worth 80% of full value.
You employ right handed threads only. Outputting ID, first name or last
name data in ascending order MAY NOT employ recursion, but output in
reverse order MAY employ recursion. This is worth 50 out of 50 points.
You employ left and right handed threads. No recursion is used at all. This is worth 100% of the points.
Repeat assignment 2, but replace the three linked lists with three
threaded binary search trees. You should still be able to output the
data in ascending and descending order. YOU MAY NOT EMPLOY RECURSION
PLEASE make sure your program contains the following header
information. PLEASE MAKE SURE YOUR HEADER CONTAINS WHICH VERSION OF
THIS PROGRAM YOU ARE DOING.
Program Number x