Java Reference
In-Depth Information
Traversals
24.12
Traversing a binary tree recursively. The previous chapter described four orders in which we
could traverse all the nodes in a binary tree: inorder, preorder, postorder, and level order. An inorder
traversal, for example, visits all nodes in the root's left subtree, then visits the root, and finally visits
all nodes in the root's right subtree. Since an inorder traversal visits the nodes in the subtrees by
using an inorder traversal, its description is recursive.
We could add a recursive method to the class BinaryTree to perform an inorder traversal. Such
a method, however, must do something specific to or with the data in each node that it visits. For
simplicity, we will display the data, even though a class that implements an ADT generally should
not perform input or output.
For the method to process the subtrees recursively, it needs the root of a subtree as a parameter.
To hide this detail from the client, we make the recursive method private and call it from a public
method that has no parameters. Thus, we have the following result:
public void inorderTraverse()
{
inorderTraverse(root);
} // end inorderTraverse
private void inorderTraverse(BinaryNodeInterface<T> node)
{
if (node != null )
{
inorderTraverse(node.getLeftChild());
System.out.println(node.getData());
inorderTraverse(node.getRightChild());
} // end if
} // end inorderTraverse
We could implement similar methods for preorder and postorder traversals.
Question 3 Trace the method inorderTraverse with the binary tree in Figure 24-4. What
data is displayed?
Question 4 Implement a recursive method preorderTraverse that displays the data in a
binary tree in preorder.
Note: Generally, the methods in a class that implements an ADT should not perform input
and output. We are doing so here to simplify the discussion that follows. However, instead of
actually displaying the data in the tree, a method like inorderTraverse could return a string
composed of the data. The client that uses the tree could display this string by using a state-
ment such as
System.out.println(myTree.inorderTraverse());
 
 
Search WWH ::




Custom Search