19.7 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.
Basic Terminology
With binary trees (Fig. 19.18), each tree node contains 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 leaf node. Computer scientists normally draw trees from the root node down—the opposite of the way most trees grow in nature.
Fig. 19.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 19.19 illustrates a binary search tree with 9 integer values. 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.
Fig. 19.19 Binary search tree containing 9 values.
19.7.1 Binary Search Tree of Integer Values
The app of Figs. 19.20 and 19.21 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) in three ways—using recursive inorder, preorder and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Figure 19.20 defines class Tree in namespace BinaryTreeLibrary for reuse purposes. Figure 19.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’ll discuss these traversals shortly.
Fig. 19.20 Declaration of class TreeNode and class Tree.
Alternate View
1 // Fig. 19.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 // automatic property LeftNode
11 public TreeNode LeftNode { get; set; }
12
13 // automatic property Data
14 public int Data { get; private set; }
15
16 // automatic property RightNode
17 public TreeNode RightNode { get; set; }
18
19 // initialize Data and make this a leaf node
20 public TreeNode(int nodeData)
21 {
22 Data = nodeData;
23 }
24
25 // insert TreeNode into Tree that contains nodes;
26 // ignore duplicate values
27 public void Insert(int insertValue)
28 {
29 if (insertValue < Data) // insert in left subtree
30 {
31 // insert new TreeNode
32 if (LeftNode == null)
33 {
34 LeftNode = new TreeNode(insertValue);
35 }
36 else // continue traversing left subtree
37 {
38 LeftNode.Insert(insertValue);
39 }
40 }
41 else if (insertValue > Data) // insert in right subtree
42 {
43 // insert new TreeNode
44 if (RightNode == null)
45 {
46 RightNode = new TreeNode(insertValue);
47 }
48 else // continue traversing right subtree
49 {
50 RightNode.Insert(insertValue);
51 }
52 }
53 }
54 }
55
56 // class Tree declaration
57 public class Tree
58 {
59 private TreeNode root;
60
61 // Insert a new node in the binary search tree.
62 // If the root node is null, create the root node here.
63 // Otherwise, call the insert method of class TreeNode.
64 public void InsertNode(int insertValue)
65 {
66 if (root == null)
67 {
68 root = new TreeNode(insertValue);
69 }
70 else
71 {
72 root.Insert(insertValue);
73 }
74 }
75
76 // begin preorder traversal
77 public void PreorderTraversal()
78 {
79 PreorderHelper(root);
80 }
81
82 // recursive method to perform preorder traversal
83 private void PreorderHelper(TreeNode node)
84 {
85 if (node != null)
86 {
87 // output node Data
88 Console.Write($"{node.Data} ");
89
90 // traverse left subtree
91 PreorderHelper(node.LeftNode);
92
93 // traverse right subtree
94 PreorderHelper(node.RightNode);
95 }
96 }
97
98 // begin inorder traversal
99 public void InorderTraversal()
100 {
101 InorderHelper(root);
102 }
103
104 // recursive method to perform inorder traversal
105 private void InorderHelper(TreeNode node)
106 {
107 if (node != null)
108 {
109 // traverse left subtree
110 InorderHelper(node.LeftNode);
111
112 // output node data
113 Console.Write($"{node.Data} ");
114
115 // traverse right subtree
116 InorderHelper(node.RightNode);
117 }
118 }
119
120 // begin postorder traversal
121 public void PostorderTraversal()
122 {
123 PostorderHelper(root);
124 }
125
126 // recursive method to perform postorder traversal
127 private void PostorderHelper(TreeNode node)
128 {
129 if (node != null)
130 {
131 // traverse left subtree
132 PostorderHelper(node.LeftNode);
133
134 // traverse right subtree
135 PostorderHelper(node.RightNode);
136
137 // output node Data
138 Console.Write($"{node.Data} ");
139 }
140 }
141 }
142 }
Fig. 19.21 Testing class Tree with a binary tree.
Alternate View
1 // Fig. 19.21: TreeTest.cs
2 // Testing class Tree with a binary tree.
3 using System;
4 using BinaryTreeLibrary;
5
6 // class TreeTest declaration
7 class TreeTest
8 {
9 // test class Tree
10 static void Main()
11 {
12 Tree tree = new Tree();
13
14 Console.WriteLine("Inserting values: ");
15 Random random = new Random();
16
17 // insert 10 random integers from 0-99 in tree
18 for (var i = 1; i <= 10; i++)
19 {
20 int insertValue = random.Next(100);
21 Console.Write($"{insertValue} ");
22
23 tree.InsertNode(insertValue);
24 }
25
26 // perform preorder traversal of tree
27 Console.WriteLine("
Preorder traversal");
28 tree.PreorderTraversal();
29
30 // perform inorder traversal of tree
31 Console.WriteLine("
Inorder traversal");
32 tree.InorderTraversal();
33
34 // perform postorder traversal of tree
35 Console.WriteLine("
Postorder traversal");
36 tree.PostorderTraversal();
37 Console.WriteLine();
38 }
39 }
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 8–54 of Fig. 19.20) is a self-referential class containing three properties—LeftNode and RightNode of type TreeNode and Data of type int. TreeNode is not a public class, because only class List needs to manipulate TreeNodes. Initially, every TreeNode is a leaf node—by default LeftNode and RightNode are initialized to null. We discuss TreeNode method Insert (lines 27–53) shortly.
Class Tree (lines 57–141) manipulates objects of class TreeNode. Class Tree has as private data root (line 59)—a reference to the root node of the tree—which is null by default. The class contains public method InsertNode (lines 64–74) to insert a new node in the tree and public methods PreorderTraversal (lines 77–80), InorderTraversal (lines 99–102) and PostorderTraversal (lines 121–127) 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.
Tree method InsertNode (lines 64–74) first determines whether the tree is empty. If so, line 68 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 27–53), 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.
The TreeNode method Insert compares the value to insert with the data value in the specified node. If the insert value is less than the specified node’s, the program determines whether the left subtree is empty (line 32). If so, line 34 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference LeftNode. Otherwise, line 38 recursively calls Insert for the left subtree to insert the value into the left subtree. If the insert value is greater than the specified node’s data, the program determines whether the right subtree is empty (line 44). If so, line 46 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference Right-Node. Otherwise, line 50 recursively calls Insert for the right subtree to insert the value in the right subtree. If the insert value matches an existing node value, the insert value is ignored.
Methods PreorderTraversal, InorderTraversal and PostorderTraversal call helper methods PreorderHelper (lines 83–96), InorderHelper (lines 105–118) and PostorderHelper (lines 127–140), respectively, to traverse the tree and display 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 instance 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. 19.22.
Fig. 19.22 Binary search tree.
Inorder Traversal Algorithm
Method InorderHelper (lines 105–118) defines the steps for an inorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Recursively traverse the left subtree with a call to
InorderHelper(line 110).Process the value in the node (line 113).
Recursively traverse the right subtree with a call to
InorderHelper(line 116).
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. 19.22 is
6 13 17 27 33 42 48
The inorder traversal of a binary search tree displays 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 83–96) defines the steps for a preorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Process the value in the node (line 88).
Recursively traverse the left subtree with a call to
PreorderHelper(line 91).Recursively traverse the right subtree with a call to
PreorderHelper(line 94).
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. 19.22 is
27 13 6 17 42 33 48
Postorder Traversal Algorithm
Method PostorderHelper (lines 127–140) defines the steps for a postorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Recursively traverse the left subtree with a call to
PostorderHelper(line 132).Recursively traverse the right subtree with a call to
PostorderHelper(line 135).Process the value in the node (line 138).
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. 19.22 is
6 17 13 33 48 42 27
Duplicate Elimination
A 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 19.22 is a tightly packed binary tree. A tightly packed binary search tree with n elements has a minimum of levels. For such a tree, at most 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 . Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because .
Overview of the Level-Order Binary-Tree Exercise
The chapter exercises present the algorithm for a level-order traversal of a binary tree, which 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.
19.7.2 Binary Search Tree of IComparable Objects
The binary-tree example in Section 19.7.1 works nicely when all the data is of type int. Suppose that you want to manipulate a binary tree of doubles. You could rewrite the TreeNode and Tree classes with different names and customize the classes to manipulate doubles. Similarly, for each data type you could create customized versions of classes TreeNode and Tree. This proliferates code, and can become difficult to manage and maintain.
Ideally, we’d like to define the binary tree’s functionality once and reuse it for many types. Languages like C# provide capabilities that enable all objects to be manipulated in a uniform manner. Using such capabilities enables us to design a more flexible data structure. C# provides these capabilities with generics (Chapter 20).
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 tree, 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.
Figures 19.23–19.24 enhance the program of Section 19.7.1 to manipulate IComparable objects. One restriction on the new versions of classes TreeNode and Tree is that each Tree object can contain objects of only one type (e.g., all strings or all doubles). If a program attempts to insert multiple types in the same Tree object, ArgumentExceptions will occur. We modified only five lines of code in class TreeNode (lines 14, 20, 27, 29 and 41 of Fig. 19.23) and one line of code in class Tree (line 64) to enable processing of IComparable objects. Except for lines 30 and 42, all other changes simply replaced int with IComparable. Lines 30 and 42 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’s 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 (Chapter 20), the type of data, int or IComparable, could be replaced at compile time by any other type that implements the necessary operators and methods.]
Fig. 19.23 Declaration of class TreeNode and class Tree.
Alternate View
1 // Fig. 19.23: BinaryTreeLibrary2.cs
2 // Declaration of class TreeNode and class Tree.
3 using System;
4
5 namespace BinaryTreeLibrary2
6 {
7 // class TreeNode declaration
8 class TreeNode
9 {
10 // automatic property LeftNode
11 public TreeNode LeftNode { get; set; }
12
13 // automatic property Data
14 public IComparable Data { get; private set; }
15
16 // automatic property RightNode
17 public TreeNode RightNode { get; set; }
18
19 // initialize Data and make this a leaf node
20 public TreeNode(IComparable nodeData )
21 {
22 Data = nodeData;
23 }
24
25 // insert TreeNode into Tree that contains nodes;
26 // ignore duplicate values
27 public void Insert(insertValue )
28 {
29 if (insertValue.CompareTo(Data) < 0) // insert in left subtree
30 {
31 // insert new TreeNode
32 if (LeftNode == null)
33 {
34 LeftNode = new TreeNode(insertValue);
35 }
36 else // continue traversing left subtree
37 {
38 LeftNode.Insert(insertValue);
39 }
40 }
41 else if (insertValue.CompareTo(Data) > 0) // insert in right
42 {
43 // insert new TreeNode
44 if (RightNode == null)
45 {
46 RightNode = new TreeNode(insertValue);
47 }
48 else // continue traversing right subtree
49 {
50 RightNode.Insert(insertValue);
51 }
52 }
53 }
54 }
55
56 // class Tree declaration
57 public class Tree
58 {
59 private TreeNode root;
60
61 // Insert a new node in the binary search tree.
62 // If the root node is null, create the root node here.
63 // Otherwise, call the insert method of class TreeNode.
64 public void InsertNode(IComparable insertValue)
65 {
66 if (root == null)
67 {
68 root = new TreeNode(insertValue);
69 }
70 else
71 {
72 root.Insert(insertValue);
73 }
74 }
75
76 // begin preorder traversal
77 public void PreorderTraversal()
78 {
79 PreorderHelper(root);
80 }
81
82 // recursive method to perform preorder traversal
83 private void PreorderHelper(TreeNode node)
84 {
85 if (node != null)
86 {
87 // output node Data
88 Console.Write($"{node.Data} ");
89
90 // traverse left subtree
91 PreorderHelper(node.LeftNode);
92
93 // traverse right subtree
94 PreorderHelper(node.RightNode);
95 }
96 }
97
98 // begin inorder traversal
99 public void InorderTraversal()
100 {
101 InorderHelper(root);
102 }
103
104 // recursive method to perform inorder traversal
105 private void InorderHelper(TreeNode node)
106 {
107 if (node != null)
108 {
109 // traverse left subtree
110 InorderHelper(node.LeftNode);
111
112 // output node data
113 Console.Write($"{node.Data} ");
114
115 // traverse right subtree
116 InorderHelper(node.RightNode);
117 }
118 }
119
120 // begin postorder traversal
121 public void PostorderTraversal()
122 {
123 PostorderHelper(root);
124 }
125
126 // recursive method to perform postorder traversal
127 private void PostorderHelper(TreeNode node)
128 {
129 if (node != null)
130 {
131 // traverse left subtree
132 PostorderHelper(node.LeftNode);
133
134 // traverse right subtree
135 PostorderHelper(node.RightNode);
136
137 // output node Data
138 Console.Write($"{node.Data} ");
139 }
140 }
141 }
142 }
Class TreeTest (Fig. 19.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 (line 13) and stringArray (lines 14–15), respectively.
Fig. 19.24 Testing class Tree with IComparable objects.
Alternate View
1 // Fig. 19.24: TreeTest.cs
2 // Testing class Tree with IComparable objects.
3 using System;
4 using BinaryTreeLibrary2;
5
6 // class TreeTest declaration
7 public class TreeTest
8 {
9 // test class Tree
10 static void Main()
11 {
12 int[] intArray = {8, 2, 4, 3, 1, 7, 5, 6};
13 double[] doubleArray = {8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6};
14 string[] stringArray =
15 {"eight", "two", "four","three", "one", "seven", "five", "six"};
16
17 // create int Tree
18 Tree intTree = new Tree();
19 PopulateTree(intArray, intTree, nameof(intTree));
20 TraverseTree(intTree, nameof(intTree));
21
22 // create double Tree
23 Tree doubleTree = new Tree();
24 PopulateTree(doubleArray, doubleTree, nameof(doubleTree));
25 TraverseTree(doubleTree, nameof(doubleTree));
26
27 // create string Tree
28 Tree stringTree = new Tree();
29 PopulateTree(stringArray, stringTree, nameof(stringTree));
30 TraverseTree(stringTree, nameof(stringTree));
31 }
32
33 // populate Tree with array elements
34 private static void PopulateTree(Array array, Tree tree, string name)
35 {
36 Console.WriteLine($"
Inserting into {name}:");
37
38 foreach (IComparable data in array)
39 {
40 Console.Write($"{data} ");
41 tree.InsertNode(data);
42 }
43 }
44
45 // perform traversals
46 private static void TraverseTree(Tree tree, string treeType)
47 {
48 // perform preorder traversal of tree
49 Console.WriteLine($"
Preorder traversal of {treeType}");
50 tree.PreorderTraversal();
51
52 // perform inorder traversal of tree
53 Console.WriteLine($"
Inorder traversal of {treeType}");
54 tree.InorderTraversal();
55
56 // perform postorder traversal of tree
57 Console.WriteLine($"
Postorder traversal of {treeType}");
58 tree.PostorderTraversal();
59 }
60 }
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
Method PopulateTree (lines 34–43) 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 46–59) receives as arguments a Tree and a string representing the Tree name, then outputs the preorder, inorder and postorder traversals of the Tree. 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.