Java Reference
In-Depth Information
Method
inorderHelper
(lines 88-96) defines the steps for an inorder traversal:
1.
Traverse the left subtree with a call to
inorderHelper
(line 93).
2.
Process the value in the node (line 94).
3.
Traverse the right subtree with a call to
inorderHelper
(line 95).
The inorder traversal does not process the value in a node until the values in that node's left sub-
tree are processed.
The inorder traversal of the tree in Fig. 21.19 is
6 13 17 27 33 42 48
27
13
42
6
17
33
48
Fig. 21.19
|
Binary search tree with seven values.
The inorder traversal of a binary search tree prints the node values in
ascending order
.
The process of creating a binary search tree actually sorts the data; thus, it's called the
binary tree sort
.
Method
preorderHelper
(lines 71-79) defines the steps for a preorder traversal:
1.
Process the value in the node (line 76).
2.
Traverse the left subtree with a call to
preorderHelper
(line 77).
3.
Traverse the right subtree with a call to
preorderHelper
(line 78).
The preorder traversal processes the value in each node as the node is visited.
After processing
the value in a particular node, it processes the values in the left subtree, then processes the
values in the right subtree. The preorder traversal of the tree in Fig. 21.19 is
27 13 6 17 42 33 48
Method
postorderHelper
(lines 105-113) defines the steps for a postorder traversal:
1.
Traverse the left subtree with a call to
postorderHelper
(line 110).
2.
Traverse the right subtree with a call to
postorderHelper
(line 111).
3.
Process the value in the node (line 112).
The postorder traversal processes the value in each node after the values of all that node's children
are processed.
The
postorderTraversal
of the tree in Fig. 21.19 is
6 17 13 33 48 42 27
The binary search tree facilitates
duplicate elimination
.
While building a tree, the
insertion operation recognizes attempts to insert a duplicate value, because a duplicate fol-
lows the same “go left” or “go right” decisions on each comparison as the original value
did. Thus, the insertion operation eventually compares the duplicate with a node con-
taining the same value. At this point, the insertion operation can decide to
discard
the
duplicate value (as we do in this example).