Trees

Linked lists, stacks and queues are linear data structures (i.e., sequences). A tree is a nonlinear, two-dimensional data structure with special properties. Tree nodes contain two or more links. This section discusses binary trees (Fig. 17.15)trees whose nodes each contain two links (one or both of which may be null). The root node is the first node in a tree. Each link in the root node refers to a child. The left child is the first node in the left subtree (also known as the root node of the left subtree), and the right child is the first node in the right subtree (also known as the root node of the right subtree). The children of a specific node are called siblings. A node with no children is called a leaf node. Computer scientists normally draw trees from the root node downexactly the opposite of the way most trees grow in nature.

Figure 17.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 17.16 illustrates a binary search tree with 12 integer values. Note that the shape of the binary search tree that corresponds to a set of data can vary, depending on the order in which the values are inserted into the tree.

Figure 17.16. Binary search tree containing 12 values.

The application of Fig. 17.17 and Fig. 17.18 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) three waysusing recursive inorder, preorder and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Class tree is declared in package com.deitel.jhtp6.ch17 for reuse purposes.

Figure 17.17. treeNode and tree class declarations for a binary search tree.

(This item is displayed on pages 840 - 842 in the print version)

 1 // Fig. 17.17: Tree.java
 2 // Definition of class TreeNode and class Tree.
 3 package com.deitel.jhtp6.ch17;
 4
 5 // class TreeNode definition
 6 class TreeNode
 7 {
 8 // package access members
 9 TreeNode leftNode; // left node
10 int data; // node value
11 TreeNode rightNode; // right node
12 
13 // constructor initializes data and makes this a leaf node
14 public TreeNode( int nodeData )
15 {
16 data = nodeData;
17 leftNode = rightNode = null; // node has no children
18 } // end TreeNode no-argument constructor
19 
20 // locate insertion point and insert new node; ignore duplicate values
21 public void insert( int insertValue )
22 {
23 // insert in left subtree
24 if ( insertValue < data )
25 {
26 // insert new TreeNode
27 if ( leftNode == null )
28 leftNode = new TreeNode( insertValue );
29 else // continue traversing left subtree
30 leftNode.insert( insertValue );
31 } // end if
32 else if ( insertValue > data ) // insert in right subtree
33 {
34 // insert new TreeNode
35 if ( rightNode == null )
36 rightNode = new TreeNode( insertValue );
37 else // continue traversing right subtree
38 rightNode.insert( insertValue );
39 } // end else if
40 } // end method insert
41 } // end class TreeNode
42 
43 // class Tree definition
44 public class Tree
45 {
46 private TreeNode root;
47 
48 // constructor initializes an empty Tree of integers
49 public Tree()
50 {
51 root = null;
52 } // end Tree no-argument constructor
53 
54 // insert a new node in the binary search tree
55 public void insertNode( int insertValue )
56 {
57 if ( root == null )
58 root = new TreeNode( insertValue ); // create the root node here
59 else
60 root.insert( insertValue ); // call the insert method
61 } // end method insertNode
62 
63 // begin preorder traversal
64 public void preorderTraversal()
65 {
66 preorderHelper( root );
67 } // end method preorderTraversal
68 
69 // recursive method to perform preorder traversal
70 private void preorderHelper( TreeNode node )
71 {
72 if ( node == null )
73 return;
74 
75 System.out.printf( "%d ", node.data ); // output node data
76 preorderHelper( node.leftNode ); // traverse left subtree 
77 preorderHelper( node.rightNode ); // traverse right subtree
78 } // end method preorderHelper
79 
80 // begin inorder traversal
81 public void inorderTraversal()
82 {
83 inorderHelper( root );
84 } // end method inorderTraversal
85 
86 // recursive method to perform inorder traversal
87 private void inorderHelper( TreeNode node )
88 {
89 if ( node == null )
90 return;
91 
92 inorderHelper( node.leftNode ); // traverse left subtree
93 System.out.printf( "%d ", node.data ); // output node data
94 inorderHelper( node.rightNode ); // traverse right subtree
95 } // end method inorderHelper
96 
97 // begin postorder traversal
98 public void postorderTraversal()
99 {
100 postorderHelper( root );
101 } // end method postorderTraversal
102 
103 // recursive method to perform postorder traversal
104 private void postorderHelper( TreeNode node )
105 {
106 if ( node == null )
107 return;
108 
109 postorderHelper( node.leftNode ); // traverse left subtree 
110 postorderHelper( node.rightNode ); // traverse right subtree
111 System.out.printf( "%d ", node.data ); // output node data
112 } // end method postorderHelper
113 } // end class Tree

Figure 17.18. Binary tree test program.

(This item is displayed on page 843 in the print version)

 1 // Fig. 17.18: TreeTest.java
 2 // This program tests class Tree.
 3 import java.util.Random;
 4 import com.deitel.jhtp6.ch17.Tree;
 5
 6 public class TreeTest
 7 {
 8 public static void main( String args[] )
 9 {
10 Tree tree = new Tree();
11 int value;
12 Random randomNumber = new Random();
13
14 System.out.println( "Inserting the following values: " );
15
16 // insert 10 random integers from 0-99 in tree
17 for ( int i = 1; i <= 10; i++ )
18 {
19 value = randomNumber.nextInt( 100 );
20 System.out.print( value + " " );
21 tree.insertNode( value );
22 } // end for
23
24 System.out.println ( "

Preorder traversal" );
25 tree.preorderTraversal(); // perform preorder traversal of tree
26
27 System.out.println ( "

Inorder traversal" );
28 tree.inorderTraversal(); // perform inorder traversal of tree
29
30 System.out.println ( "

Postorder traversal" );
31 tree.postorderTraversal(); // perform postorder traversal of tree
32 System.out.println();
33 } // end main
34 } // end class TreeTest

 

Inserting the following values:
92 73 77 16 30 30 94 89 26 80

Preorder traversal
92 73 16 30 26 77 89 80 94

Inorder traversal
16 26 30 73 77 80 89 92 94

Postorder traversal
26 30 16 80 89 77 73 94 92

 

Let us walk through the binary tree program. Method main of class TReeTest (Fig. 17.18) begins by instantiating an empty TRee object and assigning its reference to variable tree (line 10). Lines 1722 randomly generate 10 integers, each of which is inserted into the binary tree through a call to method insertNode (line 21). The program then performs preorder, inorder and postorder traversals (these will be explained shortly) of tree (lines 25, 28 and 31, respectively).

Class tree (Fig. 17.17, lines 44113) has private field root (line 46)a TReeNode reference to the root node of the tree. tree's constructor (lines 4952) initializes root to null to indicate that the tree is empty. The class contains method insertNode (lines 5561) to insert a new node in the tree and methods preorderTraversal (lines 6467), inorderTraversa l (lines 8184) and postorderTraversal (lines 98101) to begin traversals of the tree. Each of these methods calls a recursive utility method to perform the traversal operations on the internal representation of the tree. (Recursion is discussed in Chapter 15.)

Class TRee's method insertNode (lines 5561) first determines whether the tree is empty. If so, line 58 allocates a new TReeNode, initializes the node with the integer being inserted in the tree and assigns the new node to reference root. If the tree is not empty, line 60 calls TReeNode method insert (lines 2141). This method uses recursion to determine the location 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 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 if the left subtree is empty (line 27). If so, line 28 allocates a new treeNode, initializes it with the integer being inserted and assigns the new node to reference leftNode. Otherwise, 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 32), the program determines if the right subtree is empty (line 35). If so, line 36 allocates a new treeNode, initializes it with the integer being inserted and assigns the new node to reference rightNode. Otherwise, line 38 recursively calls insert for the right subtree to insert the value in the right subtree. If the insertValue is already in the tree, it is simply ignored.

Methods inorderTraversal, preorderTraversal and postorderTraversal call tree helper methods inorderHelper (lines 8795), preorderHelper (lines 7078) and postorderHelper (lines 104112), respectively, to traverse the tree and print the node values. The helper methods in class tree enable the programmer 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 determines whether the reference it receives is null and, if so, returns immediately.

Method inorderHelper (lines 8795) defines the steps for an inorder traversal:

1.	Traverse the left subtree with a call to inorderHelper (line 92).
2.	Process the value in the node (line 93).
3.	Traverse the right subtree with a call to inorderHelper (line 94).

The inorder traversal does not process the value in a node until the values in that node's left subtree are processed. The inorder traversal of the tree in Fig. 17.19 is

 6 13 17 27 33 42 48

Figure 17.19. Binary search tree with seven values.

Note that 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 is called the binary tree sort.

Method preorderHelper (lines 7078) defines the steps for a preorder traversal:

1.	Process the value in the node (line 75)
2.	Traverse the left subtree with a call to preorderHelper (line 76).
3.	Traverse the right subtree with a call to preorderHelper (line 77).

The preorder traversal processes the value in each node as the node is visited. After processing the value in a given node, the preorder traversal processes the values in the left subtree, then the values in the right subtree. The preorder traversal of the tree in Fig. 17.19 is

 27 13 6 17 42 33 48

Method postorderHelper (lines 104112) defines the steps for a postorder traversal:

1.	Traverse the left subtree with a call to postorderHelper (line 109).
2.	Traverse the right subtree with a call to postorderHelper (line 110).
3.	Process the value in the node (line 111).

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. 17.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 follows 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 containing the same value. At this point, the insertion operation can decide to discard the duplicate value (as we do in this example).

Searching a binary tree for a value that matches a key value is fast, especially for tightly packed (or balanced) trees. In a tightly packed tree, each level contains about twice as many elements as the previous level. Figure 17.19 is a tightly packed binary tree. A tightly packed binary search tree with n elements has log2n levels. Thus, at most log2n comparisons are required either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000.

The chapter exercises present algorithms for several other binary tree operations, such as deleting an item from a binary tree, printing a binary tree in a two-dimensional tree format and performing a level-order traversal of a binary tree. The level-order traversal visits the nodes of the tree row by row, starting at the root node level. On each level of the tree, a level-order traversal visits the nodes from left to right. Other binary tree exercises include allowing a binary search tree to contain duplicate values, inserting string values in a binary tree and determining how many levels are contained in a binary tree. Chapter 19 continues our discussion of data structures by presenting the data structures in the Java API.