Java Reference
In-Depth Information
Note:
Algorithms for the operations on a general tree are more complex than those for a
binary tree due to the flexible number of children per node in a general tree. For this reason,
general trees are often represented by binary trees. The next section discusses how to trans-
form a general tree into an equivalent binary tree.
Instead of the implementation just suggested, we can use a binary tree to represent any general tree.
For example, let's represent the general tree in Figure 24-9a as a binary tree. As an intermediate step,
we connect the nodes with new edges, as follows. We give the root
A
one of its original children—
B
in this case—as a left child. We then draw an edge from
B
to its sibling
C
and from
C
to another sib-
ling
D
, as Figure 24-9b shows. Likewise, we give each parent in the general tree one of its original
children as a left child in the binary tree, and link these children by edges.
If we consider each node in Figure 24-9b that is to the right of its sibling as the right child of
that sibling, we will have a binary tree that has an unorthodox form. We can move the nodes in the
drawing without disconnecting them to get the familiar look of a binary tree, as Figure 24-9c shows.
24.21
Traversals.
Let's examine the various traversals of the general tree in Figure 24-9a and compare
them with traversals of the equivalent binary tree pictured in Figure 24-9c. The general tree has the
following traversals:
Preorder:
A B E F C G H I D J
Postorder:
E F B G H I C J D A
Level order:
A B C D E F G H I J
The traversals of the binary tree are as follows:
Preorder:
A B E F C G H I D J
Postorder:
F E I H G J D C B A
Level order:
A B E C F G D H J I
Inorder:
E F B G H I C J D A
The preorder traversals of the two trees are the same. The postorder traversal of the general
tree is the same as the inorder traversal of the binary tree. We must invent a new kind of traversal of
the binary tree to get the same results as a level-order traversal of the general tree. We leave that
task to you as an exercise.
Question 7
What binary tree can represent the general tree in Figure 23-1 of the previous chapter?
