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
|
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.