Custom Generic Data Structures - Java: How to Program Early Objects - page 898

Let's walk through the binary tree program. Method main of class TreeTest
(Fig. 21.18) begins by instantiating an empty Tree<T> object and assigning its reference
to variable tree (line 10). Lines 16-21 randomly generate 10 integers, each of which is
inserted into the binary tree by calling method insertNode (line 20). The program then
performs preorder, inorder and postorder traversals (these will be explained shortly) of
tree (lines 24, 27 and 30, respectively).
Overview of Class Tree
Class Tree (Fig. 21.17, lines 45-114) requires its type argument to implement interface
Comparable , so that each value inserted in the tree can be compared with the existing values
to find the insertion point. The class has private field root (line 47)—a TreeNode refer-
ence to the root node of the tree. Tree 's constructor (lines 50-53) initializes root to null
to indicate that the tree is empty . The class contains method insertNode (lines 56-62) to
insert a new node in the tree and methods preorderTraversal (lines 65-68), inorder-
Traversal (lines 82-85) and postorderTraversal (lines 99-102) to begin traversals of
the tree. Each of these methods calls a recursive utility method to perform the traversal op-
erations on the internal representation of the tree.
Tree Method insertNode
Class Tree 's method insertNode (lines 56-62) first determines whether the tree is empty.
If so, line 59 allocates a new TreeNode , initializes the node with the value being inserted
in the tree and assigns the new node to reference root . If the tree is not empty, line 61 calls
TreeNode method insert (lines 21-41). This method uses recursion to determine the lo-
cation for the new node in the tree and inserts the node at that location. A node can be
inserted only as a leaf node in a binary search tree.
TreeNode Method insert
TreeNode method insert compares the value to insert with the data value in the root
node. If the insert value is less than the root node data (line 24), the program determines
whether the left subtree is empty (line 27). If so, line 28 allocates a new TreeNode , initial-
izes it with the value being inserted and assigns the new node to reference leftNode . Oth-
erwise, line 30 recursively calls insert for the left subtree to insert the value into the left
subtree. If the insert value is greater than the root node data (line 33), the program deter-
mines whether the right subtree is empty (line 36). If so, line 37 allocates a new TreeNode ,
initializes it with the value being inserted and assigns the new node to reference right-
Node . Otherwise, line 39 recursively calls insert for the right subtree to insert the value in
the right subtree. If the insertValue is already in the tree, it's simply ignored.
Tree Methods inorderTraversal , preorderTraversal and postorderTraversal
Methods inorderTraversal , preorderTraversal and postorderTraversal call Tree
helper methods inorderHelper (lines 88-96), preorderHelper (lines 71-79) and post-
orderHelper (lines 105-113), respectively, to traverse the tree and print the node values.
The helper methods in class Tree enable you to start a traversal without having to pass the
root node to the method. Reference root is an implementation detail that a programmer
should not be able to access. Methods inorderTraversal , preorderTraversal and
postorderTraversal simply take the private root reference and pass it to the appropriate
helper method to initiate a traversal of the tree. The base case for each helper method de-
termines whether the reference it receives is null and, if so, returns immediately.