Trees - Data Structures and Abstractions with Java - page 568

Tree Terminology
23.5

Each of the previous figures is an example of a tree. A tree is a set of nodes connected by edges
that indicate the relationships among the nodes. The nodes are arranged in levels that indicate the
nodes' hierarchy. At the top level is a single node called the root . Figure 23-5 shows a tree that,
except for the names of the nodes, is identical to the tree in Figure 23-4. In Figure 23-4, the root of
the tree is the folder myStuff ; in Figure 23-5, the root is node A .

FIGURE 23-5

A tree equivalent to the tree in Figure 23-4

Root

Level 1

A

Edge

Siblings:
children of node A

Level 2

B C E

D

Subtree of
node B

F G I J K L M

H Level 3

N O Leaves

P Q R S T

Level 4

The nodes at each successive level of a tree are the children of the nodes at the previous level.
A node that has children is the parent of those children. In Figure 23-5, node A is the parent of
nodes B , C , D , and E . Since these children have the same parent, they are called siblings . They also
are the descendants of node A , and node A is their ancestor . Furthermore, node P is a descendant of
A , and A is an ancestor of P . Notice that node P has no children. Such a node is called a leaf . A node
that is not a leaf—that is, one that has children—is called either an interior node or a nonleaf . Such
a node is also a parent.

Note: Trees
While the roots of most plants are firmly in the ground, the root of an ADT tree is at the tree's
top; it is the origin of a hierarchical organization. Each node can have children. A node with
children is a parent; a node without children is a leaf. The root is the only node that has no
parent; all other nodes have one parent each.

Question 1 Consider the tree in Figure 23-5.
a. Which nodes are the leaves?

b. Which nodes are the siblings of node K ?

c. Which nodes are the children of node B ?

d. Which nodes are the descendants of node B ?

e. Which nodes are the ancestors of node N ?

f. Which nodes are parents?

23.6

In general, each node in a tree can have an arbitrary number of children. We sometimes call such a tree a
general tree . If each node has no more than n children, the tree is called an n -ary tree . Realize that not
every general tree is an n -ary tree. If each node has at most two children, the tree is called a binary tree .
The tree in Figure 23-2 is a binary tree, but the trees in the other previous figures are general trees.