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).
 
Search WWH ::




Custom Search