24.7. TreesLinked lists, stacks and queues are linear data structures (i.e., sequence). A tree is a nonlinear, two-dimensional data structure with special properties. Tree nodes contain two or more links. Basic TerminologyWe now discuss binary trees (Fig. 24.18)trees whose nodes all contain two links (none, one or both of which may be Nothing). 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 leaf node. Computer scientists normally draw trees from the root node downexactly the opposite of the way most trees grow in nature. Figure 24.18. Binary tree graphical representation.Binary Search TreesIn 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 24.19 illustrates a binary search tree with nine 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 24.19. Binary search tree containing nine values.
24.7.1. Binary Search Tree of Integer ValuesThe application of Fig. 24.20 and 24.21 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) in three waysusing recursive inorder, preorde and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Figure 24.20 defines class tree in namespace BinaryTreeLibrary for reuse purposes (the name of the project is automatically used as the library's namespace). Figure 24.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 discuss these traversals shortly. Figure 24.20. TReeNode and TRee classes for a binary search tree.
Figure 24.21. Creating and traversing a binary tree.
Class treeNode (lines 4-65 of Fig. 24.20) is a self-referential class containing three Private data membersleftNodeReference and rightNodeReference of type treeNode and dataValue of type Integer. Initially, every treeNode is a leaf node, so the constructor (lines 10-14) initializes leftNodeReference and rightNodeReference to Nothing. Properties LeftNode (lines 17-24), Data (lines 27-34) and RightNode (lines 37-44) provide access to a ListNode's Private data members. We discuss TReeNode method Insert (lines 48-64) shortly. Class TRee (lines 68-149 of Fig. 24.20) manipulates objects of class treeNode. Class tree has as Private data root (line 69)a reference to the root node of the tree. The class contains Public method InsertNode (lines 79-85) to insert a new node in the tree and Public methods PreorderTraversal (lines 88-90), InorderTraversal (lines 109-111) and PostorderTraversal (lines 130-132) 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 72-74) initializes root to Nothing to indicate that the tree initially is empty. tree method InsertNode (lines 79-85) first determines whether the tree is empty. If so, line 81 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 48-64), 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 51). If so, line 52 allocates a new TReeNode, initializes it with the integer being inserted and assigns the new node to reference leftNode. Otherwise, line 54 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 58). If so, line 59 allocates a new TReeNode, initializes it with the integer being inserted and assigns the new node to reference rightNode. Otherwise, line 61 recursively calls Insert for the right subtree to insert the value in the right subtree. Methods InorderTraversal, PreorderTraversal and PostorderTraversal call the recursive helper methods InorderHelper (lines 114-127), PreorderHelper (lines 93-106) and PostorderHelper (lines 135-148), respectively, to traverse the tree and print the node values. The purpose of these 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. 24.22. Figure 24.22. Binary search tree.
Inorder Traversal AlgorithmMethod InorderHelper (lines 114-127) defines the steps for an inorder traversal. The steps are as follows:
The inorder traversal does not process the value in a node until the values in the node's left subtree are processed. The inorder traversal of the tree in Fig. 24.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 AlgorithmMethod PreorderHelper (lines 93-106) defines the steps for a preorder traversal. The steps are as follows:
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. 24.22 is 27 13 6 17 42 33 48 Postorder Traversal AlgorithmMethod PostorderHelper (lines 135-148) defines the steps for a postorder traversal. The steps are as follows:
The postorder traversal processes the value in each node after the values of all the node's children are processed. The postorder traversal of the tree in Fig. 24.22 is 6 17 13 33 48 42 27 Duplicate EliminationThe 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 24.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 to either find a match or determine that no match exists. Searching a (tightly packed) 1,000-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. 24.7.2. Binary Search Tree of IComparable ObjectsThe binary tree example in Section 24.7.1 works nicely when all the data is of type Integer. 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 Visual Basic, C# and Java 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 Visual Basic provides these capabilities with generics (Chapter 25). In our next example, we take advantage of Visual Basic's polymorphic capabilities by implementing treeNode and tree classes that manipulate objects of any type that implements interface IComparable (namespace System). It is imperative to compare objects stored in a binary search if we are to 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 Integer 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, the invoking and argument objects must be of the same data type; otherwise, the method throws an ArgumentException The program of Fig. 24.23 and 24.24 enhances the program from Section 24.7.1 to manipulate IComparable objects. One restriction on the new versions TReeNode and tree in Fig. 24.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 seven lines of code in class TReeNode (lines 7, 11, 28, 32, 49, 50 and 57) and one line of code in class tree (line 80) to enable processing of IComparable objects. With the exception of lines 50 and 57, all the other changes simply replaced the type Integer with the type IComparable. Lines 50 and 57 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 invoking object is less than the argument object) or greater than zero (the invoking object is greater than the argument object), respectively. [Note: If this class were written using generics, the type of data, Integer or IComparable could be replaced at compile time by any other type that implements the necessary operators and methods.] Figure 24.23. treeNode and TRee classes for manipulating IComparable objects.
Figure 24.24. Demonstrating class tree with IComparable objects.
Class treeTest (Fig. 24.24) creates three tree objects to store Integer, Double and String values, all of which the .NET Framework defines as IComparable types. The program populates the trees with the values in arrays integerArray (line 9), doubleArray (lines 10-11) and stringArray (lines 12-13), respectively. Method PopulateTree (lines 32-42) 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 45-60) 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 note that the tree of Strings appears in alphabetical order. |