A pre-order traversal of a tree visits the root element first, then recursively visits all elements in the left subtree, followed by all elements in the right subtree. An in-order traversal is similar, but we visit all elements in the left subtree first, followed by the root element, followed by all elements in the right subtree. In class we implemented the methods printPreOrder and printInOrder to print out the elements using these two types of traversals. A post-order traversal is similar, but all left subtree elements are visited first, followed by all right subtree elements, and the root element is visited last. Finish the implementation of the printPostOrder method. For example, calling this method on the tree below would print the elements in the order: 1 0 3 2 5 6 4 9 8 7.
A level-order traversal goes through the tree level by level, printing or visiting all elements on one level before going on to the next level below that. We can implement a level-order traversal using a queue to hold the elements remaining to be printed. Here is a sketch of the algorithm:
create a new empty queue
add the root node to the queue
while the queue is not empty:
remove the next node from the queue
print the element stored in the node
add the node's children (if any) to the queue
For example, the elements in the above tree would be printed as: 7 4 8 2 6 9 0 3 5 1.
In our code, each node in the tree is represented by a BinarySearchTree object, so we need to use a queue of type Queue<BinarySearchTree> to hold the nodes. In Java, a Queue is actually an interface, not a class, but we can use a LinkedList<BinarySearchTree> object to represent the queue, which implements the Queue interface methods add and remove. Here is the beginning of the printLevelOrder method. Complete its definition and test it on a few different random trees to make sure it works:
public void printLevelOrder() {
Queue<BinarySearchTree> queue = new LinkedList<BinarySearchTree>();
queue.add(this);
while (!queue.isEmpty()) {
. . .
}
}
Implement and test the following methods of the BinarySearchTree class:
int largest() should return the largest element in the tree.
boolean isLeaf() should return true if the tree is a leaf, that is, if its left and right subtrees are both null.
int countNodes() should return the total number of nodes in the tree.
int countLeaves() should return the total number of leaf nodes in the tree.
int countInteriorNodes() should return the total number of interior nodes in the tree.
int height() should return the height of the tree, that is, the length of the longest path from the root to a leaf.
Implement the method findElement, which takes a String consisting of some combination of the uppercase letters R and L (for Right and Left) that specifies a pathway through the tree starting at the root, and retrieves the corresponding element. If no such element exists, the method returns null. For example, findElement("LLR") called on the above tree would return 3, findElement("") would return 7, and findElement("RLRR") would return null. Hint: think recursively!
