One way to deal with the “problem” of null pointers in binary trees is to use that space for some other purpose. One example is the threaded binary tree. Extending the node implementation of Figure 5.7, the threaded binary tree stores with each node two additional bit fields that indicate if the child pointers lc and rc are regular pointers to child nodes or threads. 

If lc is not a pointer to a non-empty child (i.e., if it would be null in a regular binary tree), then it instead stores a pointer to the inorder predecessor of that node. The inorder predecessor is the node that would be printed immediately before the current node in an inorder traversal. If rc is not a pointer to a child, then it instead stores a pointer to the node’s inorder successor. The inorder successor is the node that would be printed immediately after the current node in an inorder traversal. The main advantage of threaded binary trees is that operations such as inorder traversal can be implemented without using recursion or a stack.

Reimplement the BST as a threaded binary tree, and include a non-recursive version of the preorder traversal. 

Transcribed Image Text:

/** Binary tree node implementation: Pointers to children */ BinNode { // Key for this node // Element for this node // Pointer to left child private BSTNode left; private BSTNode right; // Pointer to right child class BSTNode implements private K key; private E element; /** Constructors */ public BSTNode () {left = right = null; } public BSTNode (K k, E val) { left right = null; key = k; element = val; } public BSTNode (K k, E val, BSTNode 1, BSTNode r) { left = 1; right = r; key =k; element = val; } /** Return and set the key value */ public K key () { return key; } public void setKey (K k) { key = k; } /** Return and set the element value */ public E element () { return element; } public void setElement (Ev) { element = v; } /** Return and set the left child */ public BSTNode left () { return left; } public void setLeft (BSTNode p) { left = p; } /** Return and set the right child */ public BSTNode right () { return right; } public void setRight (BSTNode p) { right = p; } /** Return true if this is a leaf node */ public boolean isLeaf () { return (left == null) && (right == null); } } Figure 5.7 A binary tree node class implementation.