Trees - Data Structures and Abstractions with Java - page 578

BinaryTreeInterface<String> bTree = new BinaryTree<String>();
bTree.setTree("B", dTree, eTree); // subtree rooted at B
BinaryTreeInterface<String> cTree = new BinaryTree<String>();
cTree.setTree("C", emptyTree, hTree); // subtree rooted at C
BinaryTreeInterface<String> aTree = new BinaryTree<String>();
aTree.setTree("A", bTree, cTree); // desired tree rooted at A
// display root, height, number of nodes
System.out.println("Root of tree contains " + aTree.getRootData());
System.out.println("Height of tree is " + aTree.getHeight());
System.out.println("Tree has " + aTree.getNumberOfNodes() + " nodes");
// display nodes in preorder
System.out.println("A preorder traversal visits nodes in this order:");
Iterator<String> preorder = aTree.getPreorderIterator();
while (preorder.hasNext())
System.out.print(preorder.next() + " ");
System.out.println();

FIGURE 23-13

A binary tree whose nodes contain one-letter strings

A

B

C

D E H

F G

Examples of Binary Trees

We now look at some examples that use trees to organize data, leaving details of the implementa-
tions for the next chapter. Our first example includes a demonstration of some of the traversals
introduced earlier in this chapter.

Expression Trees
23.20

We can use a binary tree to represent an algebraic expression whose operators are binary. Recall
from Segment 5.5 in Chapter 5 that a binary operator has two operands. For example, we can repre-
sent the expression a / b as the binary tree in Figure 23-14a. The root of the tree contains the opera-

tor / and the root's children contain the operands for the operator. Notice that the order of the children
matches the order of the operands. Such a binary tree is called an expression tree. Figure 23-14
also contains other examples of expression trees. Notice that any parentheses in an expression do
not appear in its tree. The tree in fact captures the order of the expression's operations without the
need for parentheses.

VideoNote

Using the ADT tree