Java Reference
In-Depth Information
Note:
Can a tree be empty?
We allow any of our trees to be empty. Some people allow empty binary trees but require that
general trees contain at least one node. While the reasons for doing so are quite valid, we will
avoid confusion here by not making this subtle distinction between binary and general trees.
Any node and its descendants form a
subtree
of the original tree. A
subtree of a node
is a tree
rooted at a child of that node. For example, one subtree of node
B
in Figure 23-5 is the tree rooted
at
F
. A
subtree of a tree
is a subtree of the tree's root.
Question 2
This topic has a hierarchical organization that you can represent by using a
tree. Sketch a portion of this tree and indicate whether it is a general tree or a binary tree.
23.7
The
height
of a tree is the number of levels in the tree. We number the levels in a tree beginning
with the root at level 1. The tree in Figure 23-5 has four levels, and so its height is 4. The height of
a one-node tree is 1, and the height of an empty tree is 0.
We can express the height of a nonempty tree recursively by considering its subtrees:
Height of tree
T
=
1
+
height of the tallest subtree of
T
The root of the tree in Figure 23-5 has four subtrees of heights 3, 2, 3, and 2. Since the tallest of
these subtrees has height 3, the tree has height 4.
We can reach any node in a tree by following a
path
that begins at the root and goes from node
to node along the edges that join them. The path between the root and any other node is unique. The
length of a path
is the number of edges that compose it. For example, in Figure 23-5, the path that
passes through the nodes
A
,
B
,
F
, and
N
has length 3. No other path from the root to a leaf is longer
than this particular path. This tree has height 4, which is 1 more than the length of this longest path.
In general, the height of a tree is 1 more than the length of the longest of the paths between its root
and its leaves. Alternatively, the height of a tree is the number of nodes along the longest path
between the root and a leaf.
Note:
The path between a tree's root and any other node is unique.
Note:
The
height of a tree
is the number of levels in the tree. The height also equals the
number of nodes along the longest path between the root and a leaf.
Note:
Alternate definitions of height and level
Some people define both the height of a tree and its levels to be 1 less than those we will use
in this topic. For example, a one-node tree would have height 0 instead of 1. Also, the root of
a tree would be at level 0 instead of 1.
Question 3
What are the heights of the trees in Figures 23-1, 23-2, and 23-4?
