Java Reference
In-Depth Information
We leave it to you as an exercise to prove that the height of a complete tree having
n
nodes is
log
2
(
n
+
1) rounded up.
Note:
The height of a binary tree with
n
nodes that is either complete or full is log
2
(
n
+
1)
rounded up.
Programming Tip:
To compute log
2
x
in Java, first observe that log
a
x
=
log
b
x
/
log
b
a
. In Java,
Math.log(x)
returns the natural logarithm of
x
. So
Math.log(x) / Math.log(2.0)
computes the
base 2 logarithm of
x
.
Question 4
Show that the relationship between a tree's height and its number of nodes is true
for the binary trees in Parts
a
and
b
of Figure 23-6.
Question 5
How many nodes are in a full binary tree of height 6?
Question 6
What is the height of a complete tree that contains 14 nodes?
23.10
Until now, we treated the contents of the nodes in a tree simply as labels for identification. Because
the tree is an ADT, however, its nodes contain data that we process. We now consider the nodes in
this way.
Traversing the items in a data collection is a common operation that we have seen in previous
chapters. In those cases, data was arranged linearly, so the sequence of the items in the traversal
was clear. Such is not the case for a tree.
In defining a traversal, or iteration, of a tree, we must
visit
, or process, each data item exactly
once. However, the order in which we visit items is not unique. We can choose an order suitable to
our application. Because traversals of a binary tree are somewhat easier to understand than travers-
als of a general tree, we begin there. To simplify our discussion, we will use the phrase “visit a
node” to mean “process the data within a node.”
VideoNote
The ADT Tree
Note:
“Visiting a node” means “processing the data within a node.” It is an action that we
perform during a traversal of a tree. A traversal can pass through a node without visiting it at
that moment.
We know that the subtrees of the root of a binary tree are themselves binary trees. Using this recur-
sive nature of a binary tree in the definition of its traversal is natural. To visit all the nodes in a
binary tree, we must
Visit the root
Visit all the nodes in the root's left subtree
Visit all the nodes in the root's right subtree
