Java Reference
In-Depth Information
Using these ideas, we write inOrderTraversal as an instance method in the BinaryTree class and
inOrderSuccessor as a static method called by it.
public void inOrderTraversal() {
if (root == null) return;
//find first node in in-order
TreeNode node = root;
while (node.left != null) node = node.left;
while (node != null) {
node.data.visit(); //from the NodeData class
node = inOrderSuccessor(node);
}
} //end inOrderTraversal
private static TreeNode inOrderSuccessor(TreeNode node) {
if (node.right != null) {
node = node.right;
while (node.left != null) node = node.left;
return node;
}
//node has no right subtree; search for the lowest ancestor of the
//node for which the node is in the ancestor's left subtree
//return null if there is no successor (node is the last in in-order)
TreeNode parent = node.parent;
while (parent != null && parent.right == node) {
node = parent;
parent = node.parent;
}
return parent;
} //end inOrderSuccessor
As an exercise, write similar functions to perform pre-order and post-order traversals. We will write a program to
test inOrderTraversal in the next section.
8.8.1 Building a Binary Search Tree with Parent Pointers
We can modify the findOrInsert function from the BinaryTree class to build a search tree with parent pointers. This
can be done with the following:
public TreeNode findOrInsert(NodeData d) {
//Searches the tree for d; if found, returns a pointer to the node.
//If not found, d is added and a pointer to the new node returned.
//The parent field of d is set to point to its parent.
TreeNode curr, node;
int cmp;
if (root == null) {
node = new TreeNode(d);
node.parent = null;
return root = node;
}
curr = root;
 
Search WWH ::




Custom Search