Java Reference
In-Depth Information
A tree is a classic data structure with many important applications.
Key
Point
A
tree
provides a hierarchical organization in which data are stored in the nodes. This chapter
introduces binary search trees. You will learn how to construct a binary search tree, how to
search an element, insert an element, delete an element, and traverse elements in a binary
search tree. You will also learn how to define and implement a custom data structure for a
binary search tree.
A binary search tree can be implemented using a linked structure.
Key
Point
Recall that lists, stacks, and queues are linear structures that consist of a sequence of
elements. A
binary tree
is a hierarchical structure. It either is empty or consists of an
element, called the
root
, and two distinct binary trees, called the
left subtree
and
right
subtree
, either or both of which may be empty. Examples of binary trees are shown in
Figure 25.1.
binary tree
root
left subtree
right subtree
60
G
55
100
F
R
45
57
67
107
A
M
T
(a)
(b)
F
IGURE
25.1
Each node in a binary tree has zero, one, or two subtrees.
The
length
of a path is the number of the edges in the path. The
depth
of a node is
the length of the path from the root to the node. The set of all nodes at a given depth
is sometimes called a
level
of the tree.
Siblings
are nodes that share the same parent
node. The root of a left (right) subtree of a node is called a
left (right) child
of the node.
A node without children is called a
leaf
. The height of a nonempty tree is the length
of the path from the root node to its furthest leaf. The
height
of a tree that contains a
single node is
0
. Conventionally, the height of an empty tree is
—1
. Consider the tree in
Figure 25.1a. The length of the path from node 60 to 45 is
2
. The depth of node 60 is
0
, the depth of node 55 is
1
, and the depth of node 45 is
2
. The height of the tree is
2
.
Nodes 45 and 57 are siblings. Nodes 45, 57, 67, and 107 are at the same level.
A special type of binary tree called a
binary search tree
(BST) is often useful. A BST (with
no duplicate elements) has the property that for every node in the tree, the value of any node in
its left subtree is less than the value of the node, and the value of any node in its right subtree
is greater than the value of the node. The binary trees in Figure 25.1 are all BSTs.
length
depth
level
sibling
leaf
height
binary search tree
Pedagogical Note
For an interactive GUI demo to see how a BST works, go to
www.cs.armstrong.edu/liang/
animation/web/BST.html
,
as shown in Figure 25.2.
BST animation on Companion
Website
Search WWH ::
Custom Search