Java Reference
In-Depth Information
B
A
D
C
Fig. 21.15
|
Binary tree graphical representation.
In our example, we create a special binary tree called a
binary search tree
. A binary
search tree (with no duplicate node values) has the characteristic that the values in any left
subtree are less than the value in that subtree's parent node, and the values in any right
subtree are greater than the value in that subtree's parent node. Figure 21.16 illustrates a
binary search tree with 12 integer values. The shape of the binary search tree that corre-
sponds to a set of data can vary, depending on the order in which the values are inserted
into the tree.
47
25
77
11
43
65
93
7 7 1 4 8
Fig. 21.16
|
Binary search tree containing 12 values.
Figures 21.17 and 21.18 create a generic binary search tree class and use it to manip-
ulate a tree of integers. The application in Fig. 21.18
traverses
the tree (i.e., walks through
all its nodes) three ways—using recursive
inorder
,
preorder
and
postorder traversals
(trees
are almost always processed recursively). The program generates 10 random numbers and
inserts each into the tree. Class
Tree<T>
is declared in package
com.deitel.datastruc-
tures
for reuse.
1
// Fig. 21.17: Tree.java
2
// TreeNode and Tree class declarations for a binary search tree.
3
package
com.deitel.datastructures;
4
Fig. 21.17
|
TreeNode
and
Tree
class declarations for a binary search tree. (Part 1 of 4.)
