Section 24.7. Trees


24.7. Trees

Linked 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 Terminology

We 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 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 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 Values

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

  1  ' Fig. 24.20: BinaryTreeLibrary.vb  2  ' Declaration of class TreeNode and class Tree.  3  4  Public Class TreeNode  5     Private leftNodeReference As TreeNode ' link to left child    6     Private dataValue As Integer ' dataValue stored in node       7     Private rightNodeReference As TreeNode ' link to right child  8  9     ' initialize dataValue and make this a leaf node 10     Public Sub New(ByVal nodeData As Integer) 11        dataValue = nodeData           12        leftNodeReference = Nothing    13        rightNodeReference = Nothing   14     End Sub ' New 15 16     ' LeftNode property 17     Public Property LeftNode() As TreeNode 18        Get 19           Return leftNodeReference 20        End Get 21        Set(ByVal value As TreeNode) 22           leftNodeReference = value 23        End Set 24     End Property ' LeftNode 25 26     ' Data property 27     Public Property Data() As Integer 28        Get 29           Return dataValue 30        End Get 31        Set(ByVal value As Integer) 32           dataValue = value 33        End Set 34     End Property ' Data 35 36     ' RightNode property 37     Public Property RightNode() As TreeNode 38        Get 39           Return rightNodeReference 40        End Get 41        Set(ByVal value As TreeNode) 42           rightNodeReference = value 43        End Set 44     End Property ' RightNode 45 46     ' recursively insert TreeNode into Tree that contains nodes; 47     ' ignore duplicate values 48     Public Sub Insert(ByVal insertValue As Integer) 49        If insertValue < data Then ' insert in left subtree 50           ' insert new TreeNode 51           If LeftNode Is Nothing Then 52              LeftNode = New TreeNode(insertValue) 53           Else ' continue traversing left subtree 54              LeftNode.Insert(insertValue) 55           End If 56        ElseIf insertValue > data Then ' insert in right subtree 57           ' insert new TreeNode 58           If RightNode Is Nothing Then 59              RightNode =  New TreeNode(insertValue) 60           Else ' continue traversing right subtree 61              RightNode.Insert(insertValue) 62           End If 63        End If 64     End Sub ' Insert 65  End Class ' TreeNode 66 67  ' class Tree declaration 68  Public Class Tree 69     Private root As TreeNode ' reference to root node of tree 70 71     ' construct an empty Tree of integers 72     Public Sub New() 73        root = Nothing 74     End Sub ' New 75 76     ' Insert a new node in the binary search tree. 77     ' If the root node is Nothing, create the root node  here. 78     ' Otherwise, call the insert method of class TreeNode. 79     Public Sub InsertNode(ByVal insertValue As Integer) 80        If root Is Nothing Then 81           root = New TreeNode(insertValue) 82        Else 83           root.Insert(insertValue) 84        End If 85     End Sub ' InsertNode 86 87     ' begin preorder traversal 88     Public Sub PreorderTraversal() 89        PreorderHelper(root) 90     End Sub ' PreorderTraversal 91 92     ' recursive method to perform preorder traversal 93     Private Sub PreorderHelper(ByVal node As TreeNode) 94        If node Is Nothing Then 95           Return 96        End If 97 98        ' output node data             99        Console.Write(node.Data & " ") 100 101        ' traverse left subtree       102        PreorderHelper(node.LeftNode) 103 104        ' traverse right subtree       105        PreorderHelper(node.RightNode) 106     End Sub ' PreorderHelper 107 108     ' begin inorder traversal 109     Public Sub InorderTraversal() 110        InorderHelper(root) 111     End Sub ' InorderTraversal 112 113     ' recursive method to perform inorder traversal 114     Private Sub InorderHelper(ByVal node As TreeNode) 115        If node Is Nothing Then 116           Return 117        End If 118 119        ' traverse left subtree    120        InorderHelper(node.LeftNode) 121 122        ' output node data             123        Console.Write(node.Data & " ") 124 125        ' traverse right subtree      126        InorderHelper(node.RightNode) 127     End Sub ' InorderHelper 128 129     ' begin postorder traversal 130     Public Sub PostorderTraversal() 131        PostorderHelper(root) 132     End Sub ' PostorderTraversal 133 134     ' recursive method to perform postorder traversal 135     Private Sub PostorderHelper(ByVal node As TreeNode) 136        If node Is Nothing Then 137           Return 138        End If 139 140        ' traverse left subtree        141        PostorderHelper(node.LeftNode) 142 143        ' traverse right subtree        144        PostorderHelper(node.RightNode) 145 146        ' output node data             147        Console.Write(node.Data & " ") 148     End Sub ' PostorderHelper 149  End Class ' Tree 

Figure 24.21. Creating and traversing a binary tree.

  1  ' Fig. 24.21: TreeTest.vb  2  ' This program tests class Tree.  3  Imports BinaryTreeLibrary  4  5  ' class TreeTest declaration  6  Module TreeTest  7     ' test class Tree  8     Sub Main()  9        Dim tree As New Tree() 10        Dim insertValue As Integer 11 12        Console.WriteLine("Inserting values: ") 13        Dim random As New Random() 14 15        ' insert 10 random integers from 0-99 in tree 16        Dim i As Integer 17        For i = 1 To 10 18           insertValue = random.Next(100) 19           Console.Write(insertValue & " ") 20 21           tree.InsertNode(insertValue) 22        Next i 23 24        ' perform preorder traversal of tree 25        Console.WriteLine(vbCrLf & vbCrLf & _ 26           "Preorder traversal") 27        tree.PreorderTraversal() 28 29        ' perform inorder traversal of tree 30        Console.WriteLine(vbCrLf & vbCrLf & _ 31           "Inorder traversal") 32        tree.InorderTraversal() 33 34        ' perform postorder traversal of tree 35        Console.WriteLine(vbCrLf & vbCrLf & _ 36           "Postorder traversal") 37        tree.PostorderTraversal() 38     End Sub ' Main 39  End Module ' TreeTest 

 Inserting values: 39 69 94 47 50 72 55  41 97 73 Preorder traversal 39 69 47 41 50 55 94 72 73 97 Inorder traversal 39 41 47 50 55 69 72 73 94  97 Postorder traversal 41 55 50 47 73 72 97 94 69 39 



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 Algorithm

Method InorderHelper (lines 114-127) defines the steps for an inorder traversal. The steps are as follows:

1.

If the argument is Nothing, return immediately.

2.

Traverse the left subtree with a call to InorderHelper (line 120).

3.

Process the value in the node (line 123).

4.

Traverse the right subtree with a call to InorderHelper (line 126).

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 Algorithm

Method PreorderHelper (lines 93-106) defines the steps for a preorder traversal. The steps are as follows:

1.

If the argument is Nothing, return immediately.

2.

Process the value in the node (line 99).

3.

Traverse the left subtree with a call to PreorderHelper (line 102).

4.

Traverse the right subtree with a call to PreorderHelper (line 105).

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 Algorithm

Method PostorderHelper (lines 135-148) defines the steps for a postorder traversal. The steps are as follows:

1.

If the argument is Nothing, return immediately.

2.

Traverse the left subtree with a call to PostorderHelper (line 141).

3.

Traverse the right subtree with a call to PostorderHelper (line 144).

4.

Process the value in the node (line 147).

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

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

  1  ' Fig. 24.23: BinaryTreeLibrary2.vb  2  ' Declaration of class TreeNode and class Tree for IComparable  3  ' objects.  4  5  Public Class TreeNode  6     Private leftNodeValue As TreeNode ' link to left child  7     Private dataValue As IComparable ' dataValue stored in node  8     Private rightNodeValue As TreeNode ' link to right subtree  9 10     ' initialize dataValue and make this a leaf node 11     Public Sub New (ByVal nodeData As IComparable) 12        dataValue = nodeData 13        leftNodeValue = Nothing 14        rightNodeValue = Nothing 15     End Sub ' New 16 17     ' LeftNode property 18     Public Property LeftNode() As TreeNode 19        Get 20           Return leftNodeValue 21        End Get 22        Set(ByVal value As TreeNode) 23           leftNodeValue = value 24        End Set 25     End Property ' LeftNode 26 27     ' Data property 28     Public Property Data() As IComparable 29        Get 30           Return dataValue 31        End Get 32        Set(ByVal value As IComparable) 33           dataValue = value 34        End Set 35     End Property ' Data 36 37     ' RightNode property 38     Public Property RightNode() As TreeNode 39        Get 40           Return rightNodeValue 41        End Get 42        Set(ByVal value As TreeNode) 43           rightNodeValue = value 44        End Set 45     End Property ' RightNode 46 47     ' insert TreeNode into Tree that contains nodes; 48     ' ignore duplicate values 49     Public Sub Insert(ByVal insertValue As IComparable) 50        If insertValue.CompareTo(data) < 0 Then 51           ' insert in left subtree 52           If LeftNode Is Nothing Then 53              LeftNode = New TreeNode(insertValue) 54           Else ' continue traversing left subtree 55              LeftNode.Insert(insertValue) 56           End If 57        ElseIf insertValue.CompareTo(data) > 0 Then 58           ' insert in right subtree 59           If RightNode Is Nothing Then 60              RightNode = New TreeNode(insertValue) 61           Else ' continue traversing right subtree 62              RightNode.Insert(insertValue) 63           End If 64        End If 65     End Sub ' Insert 66  End Class ' TreeNode 67 68  ' class Tree declaration 69  Public Class Tree 70     Private root As TreeNode 71 72     ' construct an empty Tree of integers 73     Public Sub New() 74        root = Nothing 75     End Sub ' New 76 77     ' Insert a new node in the binary search tree. 78     ' If the root node is Nothing, create the root node here. 79     ' Otherwise, call the insert method of class TreeNode. 80     Public Sub InsertNode(ByVal insertValue As IComparable) 81        If root Is Nothing Then 82           root = New TreeNode(insertValue) 83        Else 84           root.Insert(insertValue) 85        End If 86     End Sub ' InsertNode 87 88     ' begin preorder traversal 89     Public Sub PreorderTraversal() 90        PreorderHelper(root) 91     End Sub ' PreorderTraversal 92 93     ' recursive method to perform preorder traversal 94     Private Sub PreorderHelper(ByVal node As TreeNode) 95        If node Is Nothing Then 96           Return 97        End If 98        ' output node data 99        Console.Write(Convert.ToString(node.Data) & " ") 100 101       ' traverse left subtree 102       PreorderHelper(node.LeftNode) 103 104       ' traverse right subtree 105       PreorderHelper(node.RightNode) 106    End Sub ' PreorderHelper 107 108    ' begin inorder traversal 109    Public Sub InorderTraversal() 110       InorderHelper(root) 111    End Sub ' InorderTraversal 112 113    ' recursive method to perform inorder traversal 114    Private Sub InorderHelper(ByVal node As TreeNode) 115       If node Is Nothing Then 116          Return 117       End If 118       ' traverse left subtree 119       InorderHelper(node.LeftNode) 120 121       ' output node data 122       Console.Write(Convert.ToString(node.Data) & " ") 123 124       ' traverse right subtree 125       InorderHelper(node.RightNode) 126    End Sub ' InorderHelper 127 128    ' begin postorder traversal 129    Public Sub PostorderTraversal() 130       PostorderHelper(root) 131    End Sub ' PostorderTraversal 132 133    ' recursive method to perform postorder traversal 134    Private Sub PostorderHelper(ByVal node As TreeNode) 135       If node Is Nothing Then 136          Return 137       End If 138       ' traverse left subtree 139       PostorderHelper(node.LeftNode) 140 141       ' traverse right subtree 142       PostorderHelper(node.RightNode) 143 144       ' output node data 145       Console.Write(Convert.ToString(node.Data) & " ") 146    End Sub ' PostorderHelper 147 End Class ' Tree 

Figure 24.24. Demonstrating class tree with IComparable objects.

  1  ' Fig. 24.24: TreeTest.vb  2  ' This program tests class Tree.  3  Imports BinaryTreeLibrary2  4  5  ' class TreeTest declaration  6  Module TreeTest  7     ' test class Tree  8     Sub Main()  9        Dim integerArray As Integer() = {8, 2, 4, 3, 1, 7, 5, 6}         10        Dim doubleArray As Double() = _                                  11          {8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6}                         12        Dim stringArray As String() = _                                  13          {"eight", "two", "four", "three", "one", "seven", "five", "six"} 14 15        ' create Integer Tree 16        Dim integerTree As New Tree() 17        populateTree(integerArray, integerTree, "integerTree") 18        traverseTree(integerTree, "integerTree")               19 20        ' create Double Tree 21        Dim doubleTree As New Tree() 22        populateTree(doubleArray, doubleTree, "doubleTree") 23        traverseTree(doubleTree, "doubleTree")              24 25        ' create String Tree 26        Dim stringTree As New Tree() 27        populateTree(stringArray, stringTree, "stringTree") 28        traverseTree(stringTree, "stringTree")              29     End Sub ' Main 30 31     ' populate Tree with array elements 32     Sub populateTree(ByVal array As Array, _ 33        ByVal tree As Tree, ByVal name As String) 34 35        Console.WriteLine(vbCrLf & vbCrLf & _ 36           vbCrLf & "Inserting into " & name & ":") 37 38        For Each data As IComparable In array 39           Console.Write(Convert.ToString(data) & " ") 40           tree.InsertNode(data) 41        Next data 42     End Sub ' populateTree 43 44     ' insert perform traversals 45     Sub traverseTree(ByVal tree As Tree, ByVal treeType As String) 46        ' perform preorder traveral of tree 47        Console.WriteLine(vbCrLf & vbCrLf & _ 48           "Preorder traversal of " & treeType) 49        tree.PreorderTraversal() 50 51        ' perform inorder traveral of tree 52        Console.WriteLine(vbCrLf & vbCrLf & _ 53           "Inorder traversal of " & treeType) 54        tree.InorderTraversal() 55 56        ' perform postorder traveral of tree 57        Console.WriteLine(vbCrLf & vbCrLf & _ 58           "Postorder traversal of " & treeType) 59        tree.PostorderTraversal() 60     End Sub ' traverseTree 61  End Module ' TreeTest 

 Inserting into intTree: 8 2 4 3 1 7 5 6 Preorder traversal of intTree 8 2 1 4 3 7 5 6 Inorder traversal of intTree 1 2 3 4 5 6 7 8 Postorder traversal of intTree 1 3 6 5 7 4 2 8 Inserting into doubleTree: 8.8 2.2 4.4 3.3 1.1 7.7 5.5 6.6 Preorder traversal of doubleTree 8.8 2.2 1.1 4.4 3.3 7.7 5.5 6.6 Inorder traversal of doubleTree 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 Postorder traversal of doubleTree 1.1 3.3 6.6 5.5 7.7 4.4 2.2 8.8 Inserting into stringTree: eight two four three one seven  five six Preorder traversal of stringTree eight two four five three  one seven six Inorder traversal of stringTree eight five  four one seven six three two Postorder traversal of stringTree five six seven one three four two  eight 



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.



Visual BasicR 2005 for Programmers. DeitelR Developer Series
Visual Basic 2005 for Programmers (2nd Edition)
ISBN: 013225140X
EAN: 2147483647
Year: 2004
Pages: 435

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net