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.
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.
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.
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.
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 TreeNode
s. 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.
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.
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
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
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 .
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.
IComparable
ObjectsThe 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 double
s. You could rewrite the TreeNode
and Tree
classes with different names and customize the classes to manipulate double
s. 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 string
s or all double
s). If a program attempts to insert multiple types in the same Tree
object, ArgumentException
s 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.]
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.
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 string
s appears in alphabetical order.