Trees
Linked lists, stacks and queues are linear data structures (i.e., sequences). A tree is a non-linear, two-dimensional data structure with special properties. Tree nodes contain two or more links.
Basic Terminology
This section discusses binary trees (Fig. 25.18)trees whose nodes all contain two links (none, 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, and the right child is the first node in the right subtree. The children of a specific node are called siblings. A node with no children is called a leafnode. Computer scientists normally draw trees from the root node downexactly the opposite of the way most trees grow in nature.
Figure 25.18. Binary tree graphical representation.
|
Binary Search Trees
In our binary tree 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 the subtree's parent node, and the values in any right subtree are greater than the value in the subtree's parent node. Figure 25.19 illustrates a binary search tree with 9 integer values. Note that the shape of the binary search tree that corresponds to a set of data can depend on the order in which the values are inserted into the tree.
Figure 25.19. Binary search tree containing 9 values.
25.7.1. Binary Search Tree of Integer Values
The application of Figs. 25.20 and 25.21 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) in three waysusing recursive inorder, preorder and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Figure 25.20 defines class tree in namespace BinaryTreeLibrary for reuse purposes. Figure 25.21 defines class treeTest to demonstrate class TRee's functionality. Method Main of class TReeTest instantiates an empty TRee object, then randomly generates 10 integers and inserts each value in the binary tree by calling TRee method InsertNode. The program then performs preorder, inorder and postorder traversals of the tree. We will discuss these traversals shortly.
Figure 25.20. TReeNode and tree classes for a binary search tree.
(This item is displayed on pages 1347 - 1350 in the print version)
|
1 // Fig. 25.20: BinaryTreeLibrary.cs 2 // Declaration of class TreeNode and class Tree. 3 using System; 4 5 namespace BinaryTreeLibrary 6 { 7 // class TreeNode declaration 8 class TreeNode 9 { 10 private TreeNode leftNode; // link to left child 11 private int data; // data stored in node 12 private TreeNode rightNode; // link to right child 13 14 // initialize data and make this a leaf node 15 public TreeNode( int nodeData ) 16 { 17 data = nodeData; 18 leftNode = rightNode = null; // node has no children 19 } // end constructor 20 21 // LeftNode property 22 public TreeNode LeftNode 23 { 24 get 25 { 26 return leftNode; 27 } // end get 28 set 29 { 30 leftNode = value; 31 } // end set 32 } // end property LeftNode 33 34 // Data property 35 public int Data 36 { 37 get 38 { 39 return data; 40 } // end get 41 set 42 { 43 data = value; 44 } // end set 45 } // end property Data 46 47 // RightNode property 48 public TreeNode RightNode 49 { 50 get 51 { 52 return rightNode; 53 } // end get 54 set 55 { 56 rightNode = value; 57 } // end set 58 } // end property RightNode 59 60 // insert TreeNode into Tree that contains nodes; 61 // ignore duplicate values 62 public void Insert( int insertValue ) 63 { 64 if ( insertValue < data ) // insert in left subtree 65 { 66 // insert new TreeNode 67 if ( leftNode == null ) 68 leftNode = new TreeNode( insertValue ); 69 else // continue traversing left subtree 70 leftNode.Insert( insertValue ); 71 } // end if 72 else if ( insertValue > data ) // insert in right subtree 73 { 74 // insert new TreeNode 75 if ( rightNode == null ) 76 rightNode = new TreeNode( insertValue ); 77 else // continue traversing right subtree 78 rightNode.Insert( insertValue ); 79 } // end else if 80 } // end method Insert 81 } // end class TreeNode 82 83 // class Tree declaration 84 public class Tree 85 { 86 private TreeNode root; 87 88 // construct an empty Tree of integers 89 public Tree() 90 { 91 root = null; 92 } // end constructor 93 94 // Insert a new node in the binary search tree. 95 // If the root node is null, create the root node here. 96 // Otherwise, call the insert method of class TreeNode. 97 public void InsertNode( int insertValue ) 98 { 99 if ( root == null ) 100 root = new TreeNode( insertValue ); 101 else 102 root.Insert( insertValue ); 103 } // end method InsertNode 104 105 // begin preorder traversal 106 public void PreorderTraversal() 107 { 108 PreorderHelper( root ); 109 } // end method PreorderTraversal 110 111 // recursive method to perform preorder traversal 112 private void PreorderHelper( TreeNode node ) 113 { 114 if ( node == null ) 115 return; 116 117 // output node data 118 Console.Write( node.Data + " " ); 119 120 // traverse left subtree 121 PreorderHelper( node.LeftNode ); 122 123 // traverse right subtree 124 PreorderHelper( node.RightNode ); 125 } // end method PreorderHelper 126 127 // begin inorder traversal 128 public void InorderTraversal() 129 { 130 InorderHelper( root ); 131 } // end method InorderTraversal 132 133 // recursive method to perform inorder traversal 134 private void InorderHelper( TreeNode node ) 135 { 136 if ( node == null ) 137 return; 138 139 // traverse left subtree 140 InorderHelper( node.LeftNode ); 141 142 // output node data 143 Console.Write( node.Data + " " ); 144 145 // traverse right subtree 146 InorderHelper( node.RightNode ); 147 } // end method InorderHelper 148 149 // begin postorder traversal 150 public void PostorderTraversal() 151 { 152 PostorderHelper( root ); 153 } // end method PostorderTraversal 154 155 // recursive method to perform postorder traversal 156 private void PostorderHelper( TreeNode node ) 157 { 158 if ( node == null ) 159 return; 160 161 // traverse left subtree 162 PostorderHelper( node.LeftNode ); 163 164 // traverse right subtree 165 PostorderHelper( node.RightNode ); 166 167 // output node data 168 Console.Write( node.Data + " " ); 169 } // end method PostorderHelper 170 } // end class Tree 171 }// end namespace BinaryTreeLibrary |
Figure 25.21. Creating and traversing a binary tree.
(This item is displayed on pages 1350 - 1351 in the print version)
|
1 // Fig. 25.21: TreeTest.cs 2 // This program tests class Tree. 3 using System; 4 using BinaryTreeLibrary; 5 6 // class TreeTest declaration 7 public class TreeTest 8 { 9 // test class Tree 10 static void Main( string[] args ) 11 { 12 Tree tree = new Tree(); 13 int insertValue; 14 15 Console.WriteLine( "Inserting values: " ); 16 Random random = new Random(); 17 18 // insert 10 random integers from 0-99 in tree 19 for ( int i = 1; i <= 10; i++ ) 20 { 21 insertValue = random.Next( 100 ); 22 Console.Write( insertValue + " " ); 23 24 tree.InsertNode( insertValue ); 25 } // end for 26 27 // perform preorder traversal of tree 28 Console.WriteLine( " Preorder traversal" ); 29 tree.PreorderTraversal(); 30 31 // perform inorder traversal of tree 32 Console.WriteLine( " Inorder traversal" ); 33 tree.InorderTraversal(); 34 35 // perform postorder traversal of tree 36 Console.WriteLine( " Postorder traversal" ); 37 tree.PostorderTraversal(); 38 } // end method Main 39 } // end class TreeTest
|
Class treeNode (lines 881 of Fig. 25.20) is a self-referential class containing three private data membersleftNode and rightNode of type treeNode and data of type int. Initially, every treeNode is a leaf node, so the constructor (lines 1519) initializes references leftNode and rightNode to null. Properties LeftNode (lines 2232), Data (lines 3545) and RightNode (lines 4858) provide access to a ListNode's private data members. We discuss treeNode method Insert (lines 6280) shortly.
Class tree (lines 84170 of Fig. 25.20) manipulates objects of class treeNode. Class tree has as private data root (line 86)a reference to the root node of the tree. The class contains public method InsertNode (lines 97103) to insert a new node in the tree and public methods PreorderTraversal (lines 106109), InorderTraversal (lines 128131) and PostorderTraversal (lines 150153) to begin traversals of the tree. Each of these methods calls a separate recursive utility method to perform the traversal operations on the internal representation of the tree. The TRee constructor (lines 8992) initializes root to null to indicate that the tree initially is empty.
tree method InsertNode (lines 97103) first determines whether the tree is empty. If so, line 100 allocates a new treeNode, initializes the node with the integer being inserted in the tree and assigns the new node to root. If the tree is not empty, InsertNode calls TReeNode method Insert (lines 6280), which recursively determines 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, the program determines whether the left subtree is empty (line 67). If so, line 68 allocates a new treeNode, initializes it with the integer being inserted and assigns the new node to reference leftNode. Otherwise, line 70 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, the program determines whether the right subtree is empty (line 75). If so, line 76 allocates a new TReeNode, initializes it with the integer being inserted and assigns the new node to reference rightNode. Otherwise, line 78 recursively calls Insert for the right subtree to insert the value in the right subtree.
Methods InorderTraversal, PreorderTraversal and PostorderTraversal call helper methods InorderHelper (lines 134147), PreorderHelper (lines 112125) and PostorderHelper (lines 156169), respectively, to traverse the tree and print the node values. The purpose of the helper methods in class tree is to allow the programmer to start a traversal without needing to obtain a reference to the root node first, then call the recursive method with that reference. Methods InorderTraversal, PreorderTraversal and PostorderTraversal simply take private variable root and pass it to the appropriate helper method to initiate a traversal of the tree. For the following discussion, we use the binary search tree shown in Fig. 25.22.
Figure 25.22. Binary search tree.
(This item is displayed on page 1352 in the print version)
Inorder Traversal Algorithm
Method InorderHelper (lines 134147) defines the steps for an inorder traversal. Those steps are as follows:
|
1. |
If the argument is null, return immediately.
|
|
2. |
Traverse the left subtree with a call to InorderHelper (line 140).
|
|
3. |
Process the value in the node (line 143).
|
|
4. |
Traverse the right subtree with a call to InorderHelper (line 146).
|
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. 25.22 is
6 13 17 27 33 42 48
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 (when coupled with an inorder traversal)thus, this process is called the binary tree sort.
Preorder Traversal Algorithm
Method PreorderHelper (lines 112125) defines the steps for a preorder traversal. Those steps are as follows:
|
1. |
If the argument is null, return immediately.
|
|
2. |
Process the value in the node (line 118).
|
|
3. |
Traverse the left subtree with a call to PreorderHelper (line 121).
|
|
4. |
Traverse the right subtree with a call to PreorderHelper (line 124).
|
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. 25.22 is
27 13 6 17 42 33 48
Postorder Traversal Algorithm
Method PostorderHelper (lines 156169) defines the steps for a postorder traversal. Those steps are as follows:
|
1. |
If the argument is null, return immediately.
|
|
2. |
Traverse the left subtree with a call to PostorderHelper (line 162).
|
|
3. |
Traverse the right subtree with a call to PostorderHelper (line 165).
|
|
4. |
Process the value in the node (line 168).
|
The postorder traversal processes the value in each node after the values of all that node's children are processed. The postorder traversal of the tree in Fig. 25.22 is
6 17 13 33 48 42 27
Duplicate Elimination
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 might simply discard the duplicate value.
Searching a binary tree for a value that matches a key value is fast, especially for tightly packed binary trees. In a tightly packed binary tree, each level contains about twice as many elements as the previous level. Figure 25.22 is a tightly packed binary tree. A binary search tree with n elements has a minimum of 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.
Overview of the Binary Tree Exercises
The chapter exercises present algorithms for other binary tree operations, such as deleting an item from a binary tree and performing a level-order traversal of a binary tree. The level-order traversal of a binary tree 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.
25.7.2. Binary Search Tree of IComparable Objects
The binary tree example in Section 25.7.1 works nicely when all the data is of type int. Suppose that you want to manipulate a binary tree of double values. You could rewrite the TReeNode and TRee classes with different names and customize the classes to manipulate double values. Similarly, for each data type you could create customized versions of classes treeNode and TRee. This results in a proliferation of code, which can become difficult to manage and maintain.
Ideally, we would like to define the functionality of a binary tree once and reuse that functionality for many data types. Languages like Java™ and C# provide polymorphic capabilities that enable all objects to be manipulated in a uniform manner. Using such capabilities enables us to design a more flexible data structure. The new version of C#, C# 2.0, provides these capabilities with generics (Chapter 26).
In our next example, we take advantage of C#'s polymorphic capabilities by implementing TReeNode and tree classes that manipulate objects of any type that implements interface IComparable (namespace System). It is imperative that we be able to compare objects stored in a binary search, so we can determine the path to the insertion point of a new node. Classes that implement IComparable define method CompareTo, which compares the object that invokes the method with the object that the method receives as an argument. The method returns an int value less than zero if the calling object is less than the argument object, zero if the objects are equal and a positive value if the calling object is greater than the argument object. Also, both the calling and argument objects must be of the same data type; otherwise, the method throws an ArgumentException.
The program of Figs. 25.23 and 25.24 enhances the program from Section 25.7.1 to manipulate IComparable objects. One restriction on the new versions of classes treeNode and TRee in Fig. 25.23 is that each tree object can contain objects of only one data type (e.g., all strings or all doubles). If a program attempts to insert multiple data types in the same TRee object, ArgumentExceptions will occur. We modified only six lines of code in class TReeNode (lines 12, 16, 36, 63, 65 and 73) and one line of code in class tree (line 98) to enable processing of IComparable objects. With the exception of lines 65 and 73, all other changes simply replaced the type int with the type IComparable. Lines 65 and 73 previously used the < and > operators to compare the value being inserted with the value in a given node. These lines now compare IComparable objects via the interface's CompareTo method, then test the method's return value to determine whether it is less than zero (the calling object is less than the argument object) or greater than zero (the calling object is greater than the argument object), respectively. [Note: If this class were written using generics, the type of data, int or IComparable, could be replaced at compile time by any other type that implements the necessary operators and methods.]
Figure 25.23. treeNode and tree classes for manipulating IComparable objects.
|
1 // Fig. 25.23: BinaryTreeLibrary2.cs 2 // Declaration of class TreeNode and class Tree for IComparable 3 // objects. 4 using System; 5 6 namespace BinaryTreeLibrary2 7 { 8 // class TreeNode declaration 9 class TreeNode 10 { 11 private TreeNode leftNode; // link to left child 12 private IComparable data; // data stored in node 13 private TreeNode rightNode; // link to right subtree 14 15 // initialize data and make this a leaf node 16 public TreeNode( IComparable nodeData ) 17 { 18 data = nodeData; 19 leftNode = rightNode = null; // node has no children 20 } // end constructor 21 22 // LeftNode property 23 public TreeNode LeftNode 24 { 25 get 26 { 27 return leftNode; 28 } // end get 29 set 30 { 31 leftNode = value; 32 } // end set 33 } // end property LeftNode 34 35 // Data property 36 public IComparable Data 37 { 38 get 39 { 40 return data; 41 } // end get 42 set 43 { 44 data = value; 45 } // end set 46 } // end property Data 47 48 // RightNode property 49 public TreeNode RightNode 50 { 51 get 52 { 53 return rightNode; 54 } // end get 55 set 56 { 57 rightNode = value; 58 } // end set 59 } // end property Right Node 60 61 // insert TreeNode into Tree that contains nodes; 62 // ignore duplicate values 63 public void Insert( IComparable insertValue ) 64 { 65 if ( insertValue.CompareTo( data ) < 0 ) 66 { 67 // insert in left subtree 68 if ( leftNode == null ) 69 leftNode = new TreeNode( insertValue ); 70 else // continue traversing left subtree 71 leftNode.Insert( insertValue ); 72 } // end if 73 else if ( insertValue.CompareTo( data ) > 0 ) 74 { 75 // insert in right subtree 76 if ( rightNode == null ) 77 rightNode = new TreeNode( insertValue ); 78 else // continue traversing right subtree 79 rightNode.Insert( insertValue ); 80 } // end else if 81 } // end method Insert 82 } // end class TreeNode 83 84 // class Tree declaration 85 public class Tree 86 { 87 private TreeNode root; 88 89 // construct an empty Tree of integers 90 public Tree() 91 { 92 root = null; 93 } // end constructor 94 95 // Insert a new node in the binary search tree. 96 // If the root node is null, create the root node here. 97 // Otherwise, call the insert method of class TreeNode. 98 public void InsertNode( IComparable insertValue ) 99 { 100 if ( root == null ) 101 root = new TreeNode( insertValue ); 102 else 103 root.Insert( insertValue ); 104 } // end method InsertNode 105 106 // begin preorder traversal 107 public void PreorderTraversal() 108 { 109 PreorderHelper( root ); 110 } // end method PreorderTraversal 111 112 // recursive method to perform preorder traversal 113 private void PreorderHelper( TreeNode node ) 114 { 115 if ( node == null ) 116 return; 117 118 // output node data 119 Console.Write( node.Data + " " ); 120 121 // traverse left subtree 122 PreorderHelper( node.LeftNode ); 123 124 // traverse right subtree 125 PreorderHelper( node.RightNode ); 126 } // end method PreorderHelper 127 128 // begin inorder traversal 129 public void InorderTraversal() 130 { 131 InorderHelper( root ); 132 } // end method InorderTraversal 133 134 // recursive method to perform inorder traversal 135 private void InorderHelper( TreeNode node ) 136 { 137 if ( node == null ) 138 return; 139 140 // traverse left subtree 141 InorderHelper( node.LeftNode ); 142 143 // output node data 144 Console.Write( node.Data + " " ); 145 146 // traverse right subtree 147 InorderHelper( node.RightNode ); 148 } // end method InorderHelper 149 150 // begin postorder traversal 151 public void PostorderTraversal() 152 { 153 PostorderHelper( root ); 154 } // end method PostorderTraversal 155 156 // recursive method to perform postorder traversal 157 private void PostorderHelper( TreeNode node ) 158 { 159 if ( node == null ) 160 return; 161 162 // traverse left subtree 163 PostorderHelper( node.LeftNode ); 164 165 // traverse right subtree 166 PostorderHelper( node.RightNode ); 167 168 // output node data 169 Console.Write( node.Data + " " ); 170 } // end method PostorderHelper 171 172 } // end class Tree 173 } // end namespace BinaryTreeLibrary2 |
Figure 25.24. Demonstrating class TRee with IComparable objects.
(This item is displayed on pages 1357 - 1359 in the print version)
|
1 // Fig. 25.24: TreeTest.cs 2 // This program tests class Tree. 3 using System; 4 using BinaryTreeLibrary2; 5 6 // class TreeTest declaration 7 public class TreeTest 8 { 9 // test class Tree 10 static void Main( string[] args ) 11 { 12 int[] intArray = { 8, 2, 4, 3, 1, 7, 5, 6 }; 13 double[] doubleArray = 14 { 8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6 }; 15 string[] stringArray = { "eight", "two", "four", 16 "three", "one", "seven", "five", "six" }; 17 18 // create int Tree 19 Tree intTree = new Tree(); 20 populateTree( intArray, intTree, "intTree" ); 21 traverseTree( intTree, "intTree" ); 22 23 // create double Tree 24 Tree doubleTree = new Tree(); 25 populateTree( doubleArray, doubleTree, "doubleTree" ); 26 traverseTree( doubleTree, "doubleTree" ); 27 28 // create string Tree 29 Tree stringTree = new Tree(); 30 populateTree( stringArray, stringTree, "stringTree" ); 31 traverseTree( stringTree, "stringTree" ); 32 } // end Main 33 34 // populate Tree with array elements 35 static void populateTree( Array array, Tree tree, string name ) 36 { 37 Console.WriteLine( " Inserting into " + name + ":" ); 38 39 foreach ( IComparable data in array ) 40 { 41 Console.Write( data + " " ); 42 tree.InsertNode( data ); 43 } // end foreach 44 } // end method populateTree 45 46 // insert perform traversals 47 static void traverseTree( Tree tree, string treeType ) 48 { 49 // perform preorder traveral of tree 50 Console.WriteLine( " Preorder traversal of " + treeType ); 51 tree.PreorderTraversal(); 52 53 // perform inorder traveral of tree 54 Console.WriteLine( " Inorder traversal of " + treeType ); 55 tree.InorderTraversal(); 56 57 // perform postorder traveral of tree 58 Console.WriteLine( " Postorder traversal of " + treeType ); 59 tree.PostorderTraversal(); 60 } // end method traverseTree 61 } // end class TreeTest
|
Class treeTest (Fig. 25.24) creates three tree objects to store int, double and string values, all of which the .NET Framework defines as IComparable types. The program populates the trees with the values in arrays intArray (line 12), doubleArray (lines 1314) and stringArray (lines 1516), respectively.
Method PopulateTree (lines 3544) receives as arguments an Array containing the initializer values for the tree, a tree in which the array elements will be placed and a string representing the TRee name, then inserts each Array element into the tree. Method TRaverseTree (lines 4760) receives as arguments a TRee and a string representing the tree name, then outputs the preorder, inorder and postorder traversals of the tree. Note that the inorder traversal of each tree outputs the data in sorted order regardless of the data type stored in the tree. Our polymorphic implementation of class Tree invokes the appropriate data type's CompareTo method to determine the path to each value's insertion point by using the standard binary search tree insertion rules. Also, notice that the tree of strings appears in alphabetical order.