Trees

Linked lists, stacks and queues are linear data structures. A tree is a nonlinear, two-dimensional data structure. Tree nodes contain two or more links. This section discusses binary trees (Fig. 21.18)trees whose nodes all contain two links (none, one or both of which may be null).

Figure 21.18. A graphical representation of a binary tree.

 

Basic Terminology

For the purposes of this discussion, refer to nodes A, B, C and D in Fig. 21.18. The root node (node B) is the first node in a tree. Each link in the root node refers to a child (nodes A and D). The left child (node A) is the root node of the left subtree (which contains only node A), and the right child (node D) is the root node of the right subtree (which contains nodes D and C). The children of a single node are called siblings (e.g., nodes A and D are siblings). A node with no children is called a leaf node (e.g., nodes A and C are leaf nodes). Computer scientists normally draw trees from the root node downexactly the opposite of how trees grow in nature.

Binary Search Trees

This section discusses 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 its parent node, and the values in any right subtree are greater than the value in its parent node. Figure 21.19 illustrates a binary search tree with 9 values. Note that the shape of the binary search tree that corresponds to a set of data can vary, depending on the order in which the values are inserted into the tree.

Figure 21.19. A binary search tree.

(This item is displayed on page 1026 in the print version)

 

Implementing the Binary Search Tree Program

The program of Figs. 21.2021.22 creates a binary search tree and traverses it (i.e., walks through all its nodes) three waysusing recursive inorder, preorder and postorder traversals. We explain these traversal algorithms shortly.

Figure 21.20. treeNode class-template definition.

(This item is displayed on pages 1026 - 1027 in the print version)

 1 // Fig. 21.20: Treenode.h
 2 // Template TreeNode class definition.
 3 #ifndef TREENODE_H
 4 #define TREENODE_H
 5
 6 // forward declaration of class Tree
 7 template< typename NODETYPE > class Tree;
 8
 9 // TreeNode class-template definition
10 template< typename NODETYPE >
11 class TreeNode
12 {
13 friend class Tree< NODETYPE >;
14 public:
15 // constructor
16 TreeNode( const NODETYPE &d )
17 : leftPtr( 0 ), // pointer to left subtree
18 data( d ), // tree node data
19 rightPtr( 0 ) // pointer to right substree
20 {
21 // empty body
22 } // end TreeNode constructor
23
24 // return copy of node's data
25 NODETYPE getData() const
26 {
27 return data;
28 } // end getData function
29 private:
30 TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
31 NODETYPE data;
32 TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
33 }; // end class TreeNode
34
35 #endif

---

We begin our discussion with the driver program (Fig. 21.22), then continue with the implementations of classes TReeNode (Fig. 21.20) and TRee (Fig. 21.21). Function main (Fig. 21.22) begins by instantiating integer tree intTree of type TRee< int > (line 15). The program prompts for 10 integers, each of which is inserted in the binary tree by calling insertNode (line 24). The program then performs preorder, inorder and postorder traversals (these are explained shortly) of intTree (lines 28, 31 and 34, respectively). The program then instantiates floating-point tree doubleTree of type TRee< double > (line 36). The program prompts for 10 double values, each of which is inserted in the binary tree by calling insertNode (line 46). The program then performs preorder, inorder and postorder traversals of doubleTree (lines 50, 53 and 56, respectively).

---

Figure 21.21. TRee class-template definition.

(This item is displayed on pages 1027 - 1029 in the print version)

 1 // Fig. 21.21: Tree.h
 2 // Template Tree class definition.
 3 #ifndef TREE_H
 4 #define TREE_H
 5
 6 #include 
 7 using std::cout;
 8 using std::endl;
 9
10 #include "Treenode.h"
11
12 // Tree class-template definition
13 template< typename NODETYPE > class Tree
14 {
15 public:
16 Tree(); // constructor
17 void insertNode( const NODETYPE & );
18 void preOrderTraversal() const; 
19 void inOrderTraversal() const; 
20 void postOrderTraversal() const; 
21 private:
22 TreeNode< NODETYPE > *rootPtr;
23
24 // utility functions 
25 void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
26 void preOrderHelper( TreeNode< NODETYPE > * ) const; 
27 void inOrderHelper( TreeNode< NODETYPE > * ) const; 
28 void postOrderHelper( TreeNode< NODETYPE > * ) const; 
29 }; // end class Tree
30
31 // constructor
32 template< typename NODETYPE >
33 Tree< NODETYPE >::Tree()
34 {
35 rootPtr = 0; // indicate tree is initially empty
36 } // end Tree constructor
37
38 // insert node in Tree
39 template< typename NODETYPE >
40 void Tree< NODETYPE >::insertNode( const NODETYPE &value )
41 {
42 insertNodeHelper( &rootPtr, value );
43 } // end function insertNode
44
45 // utility function called by insertNode; receives a pointer
46 // to a pointer so that the function can modify pointer's value
47 template< typename NODETYPE >
48 void Tree< NODETYPE >::insertNodeHelper(
49 TreeNode< NODETYPE > **ptr, const NODETYPE &value )
50 {
51 // subtree is empty; create new TreeNode containing value
52 if ( *ptr == 0 )
53 *ptr = new TreeNode< NODETYPE >( value );
54 else // subtree is not empty
55 {
56 // data to insert is less than data in current node
57 if ( value < ( *ptr )->data )
58 insertNodeHelper( &( ( *ptr )->leftPtr ), value );
59 else
60 {
61 // data to insert is greater than data in current node
62 if ( value > ( *ptr )->data )
63 insertNodeHelper( &( ( *ptr )->rightPtr ), value );
64 else // duplicate data value ignored
65 cout << value << " dup" << endl;
66 } // end else
67 } // end else
68 } // end function insertNodeHelper
69
70 // begin preorder traversal of Tree
71 template< typename NODETYPE >
72 void Tree< NODETYPE >::preOrderTraversal() const
73 {
74 preOrderHelper( rootPtr );
75 } // end function preOrderTraversal
76
77 // utility function to perform preorder traversal of Tree
78 template< typename NODETYPE >
79 void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const
80 {
81 if ( ptr != 0 )
82 {
83 cout << ptr->data << ' '; // process node 
84 preOrderHelper( ptr->leftPtr ); // traverse left subtree 
85 preOrderHelper( ptr->rightPtr ); // traverse right subtree
86 } // end if
87 } // end function preOrderHelper
88
89 // begin inorder traversal of Tree
90 template< typename NODETYPE >
91 void Tree< NODETYPE >::inOrderTraversal() const
92 {
93 inOrderHelper( rootPtr );
94 } // end function inOrderTraversal
95
96 // utility function to perform inorder traversal of Tree
97 template< typename NODETYPE >
98 void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
99 {
100 if ( ptr != 0 )
101 {
102 inOrderHelper( ptr->leftPtr ); // traverse left subtree 
103 cout << ptr->data << ' '; // process node 
104 inOrderHelper( ptr->rightPtr ); // traverse right subtree
105 } // end if
106 } // end function inOrderHelper
107
108 // begin postorder traversal of Tree
109 template< typename NODETYPE >
110 void Tree< NODETYPE >::postOrderTraversal() const
111 {
112 postOrderHelper( rootPtr );
113 } // end function postOrderTraversal
114
115 // utility function to perform postorder traversal of Tree
116 template< typename NODETYPE >
117 void Tree< NODETYPE >::postOrderHelper(
118 TreeNode< NODETYPE > *ptr ) const
119 {
120 if ( ptr != 0 )
121 {
122 postOrderHelper( ptr->leftPtr ); // traverse left subtree 
123 postOrderHelper( ptr->rightPtr ); // traverse right subtree
124 cout << ptr->data << ' '; // process node 
125 } // end if
126 } // end function postOrderHelper
127
128 #endif

Figure 21.22. Creating and traversing a binary tree.

(This item is displayed on pages 1030 - 1031 in the print version)

 1 // Fig. 21.22: Fig21_22.cpp
 2 // Tree class test program.
 3 #include 
 4 using std::cout;
 5 using std::cin;
 6 using std::fixed;
 7
 8 #include 
 9 using std::setprecision;
10
11 #include "Tree.h" // Tree class definition
12
13 int main()
14 {
15 Tree< int > intTree; // create Tree of int values
16 int intValue;
17
18 cout << "Enter 10 integer values:
";
19
20 // insert 10 integers to intTree
21 for ( int i = 0; i < 10; i++ )
22 {
23 cin >> intValue;
24 intTree.insertNode( intValue );
25 } // end for
26
27 cout << "
Preorder traversal
";
28 intTree.preOrderTraversal();
29
30 cout << "
Inorder traversal
";
31 intTree.inOrderTraversal();
32
33 cout << "
Postorder traversal
";
34 intTree.postOrderTraversal();
35
36 Tree< double > doubleTree; // create Tree of double values
37 double doubleValue;
38
39 cout << fixed << setprecision( 1 )
40 << "


Enter 10 double values:
";
41
42 // insert 10 doubles to doubleTree
43 for ( int j = 0; j < 10; j++ )
44 {
45 cin >> doubleValue;
46 doubleTree.insertNode( doubleValue );
47 } // end for
48
49 cout << "
Preorder traversal
";
50 doubleTree.preOrderTraversal();
51
52 cout << "
Inorder traversal
";
53 doubleTree.inOrderTraversal();
54
55 cout << "
Postorder traversal
";
56 doubleTree.postOrderTraversal();
57
58 cout << endl;
59 return 0;
60 } // end main

 

 Enter 10 integer values:
 50 25 75 12 33 67 88 6 13 68

 Preorder traversal
 50 25 12 6 13 33 75 67 68 88
 Inorder traversal
 6 12 13 25 33 50 67 68 75 88
 Postorder traversal
 6 13 12 33 25 68 67 88 75 50

 Enter 10 double values:
 39.2 16.5 82.7 3.3 65.2 90.8 1.1 4.4 89.5 92.5

 Preorder traversal
 39.2 16.5 3.3 1.1 4.4 82.7 65.2 90.8 89.5 92.5
 Inorder traversal
 1.1 3.3 4.4 16.5 39.2 65.2 82.7 89.5 90.8 92.5
 Postorder traversal
 1.1 4.4 3.3 16.5 65.2 89.5 92.5 90.8 82.7 39.2

 

---

Now we discuss the class-template definitions. We begin with the treeNode class template (Fig. 21.20) definition that declares tree< NODETYPE > as its friend (line 13). This makes all member functions of a given specialization of class template tree (Fig. 21.21) friends of the corresponding specialization of class template treeNode, so they can access the private members of treeNode objects of that type. Because the TReeNode template parameter NODETYPE is used as the template argument for tree in the friend declaration, treeNodes specialized with a particular type can be processed only by a tree specialized with the same type (e.g., a TRee of int values manages TReeNode objects that store int values).

Lines 3032 declare a TReeNode's private datathe node's data value, and pointers leftPtr (to the node's left subtree) and rightPtr (to the node's right subtree). The constructor (lines 1622) sets data to the value supplied as a constructor argument and sets pointers leftPtr and rightPtr to zero (thus initializing this node to be a leaf node). Member function geTData (lines 2528) returns the data value.

---

The TRee class template (Fig. 21.21) has as private data rootPtr (line 22), a pointer to the root node of the tree. Lines 1720 of the class template declare the public member functions insertNode (that inserts a new node in the tree) and preOrderTraversal, inOrderTraversal and postOrderTraversal, each of which walks the tree in the designated manner. Each of these member functions calls its own separate recursive utility function to perform the appropriate operations on the internal representation of the tree, so the program is not required to access the underlying private data to perform these functions. Remember that the recursion requires us to pass in a pointer that represents the next subtree to process. The tree constructor initializes rootPtr to zero to indicate that the tree is initially empty.

The tree class's utility function insertNodeHelper (lines 4768) is called by insertNode (lines 3943) to recursively insert a node into the tree. A node can only be inserted as a leaf node in a binary search tree. If the tree is empty, a new TReeNode is created, initialized and inserted in the tree (lines 5354).

If the tree is not empty, the program compares the value to be inserted with the data value in the root node. If the insert value is smaller (line 57), the program recursively calls insertNodeHelper (line 58) to insert the value in the left subtree. If the insert value is larger (line 62), the program recursively calls insertNodeHelper (line 64) to insert the value in the right subtree. If the value to be inserted is identical to the data value in the root node, the program prints the message " dup" (line 65) and returns without inserting the duplicate value into the tree. Note that insertNode passes the address of rootPtr to insertNodeHelper (line 42) so it can modify the value stored in rootPtr (i.e., the address of the root node). To receive a pointer to rootPtr (which is also a pointer), insertNodeHelper's first argument is declared as a pointer to a pointer to a treeNode.

---

Each of the member functions inOrderTraversal (lines 9094), preOrderTraversal (lines 7175) and postOrderTraversal (lines 109113) traverses the tree and prints the node values. For the purpose of the following discussion, we use the binary search tree in Fig. 21.23.

Figure 21.23. A binary search tree.

 

Inorder Traversal Algorithm

Function inOrderTraversal invokes utility function inOrderHelper to perform the inorder traversal of the binary tree. The steps for an inorder traversal are:

1. Traverse the left subtree with an inorder traversal. (This is performed by the call to inOrderHelper at line 102.)
2. Process the value in the nodei.e., print the node value (line 103).
3. Traverse the right subtree with an inorder traversal. (This is performed by the call to inOrderHelper at line 104.)

The value in a node is not processed until the values in its left subtree are processed, because each call to inOrderHelper immediately calls inOrderHelper again with the pointer to the left subtree. The inorder traversal of the tree in Fig. 21.23 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 datathus, this process is called the binary tree sort.

Preorder Traversal Algorithm

Function preOrderTraversal invokes utility function preOrderHelper to perform the preorder traversal of the binary tree. The steps for an preorder traversal are:

1. Process the value in the node (line 83).
2. Traverse the left subtree with a preorder traversal. (This is performed by the call to preOrderHelper at line 84.)
3. Traverse the right subtree with a preorder traversal. (This is performed by the call to preOrderHelper at line 85.)

The value in each node is processed as the node is visited. After the value in a given node is processed, the values in the left subtree are processed. Then the values in the right subtree are processed. The preorder traversal of the tree in Fig. 21.23 is

27 13 6 17 42 33 48

---

Postorder Traversal Algorithm

Function postOrderTraversal invokes utility function postOrderHelper to perform the postorder traversal of the binary tree. The steps for an postorder traversal are:

1. Traverse the left subtree with a postorder traversal. (This is performed by the call to postOrderHelper at line 122.)
2. Traverse the right subtree with a postorder traversal. (This is performed by the call to postOrderHelper at line 123.)
3. Process the value in the node (line 124).

The value in each node is not printed until the values of its children are printed. The postOrderTraversal of the tree in Fig. 21.23 is

6 17 13 33 48 42 27

 

Duplicate Elimination

The binary search tree facilitates duplicate elimination. As the tree is being created, an attempt to insert a duplicate value will be recognized, because a duplicate will follow the same "go left" or "go right" decisions on each comparison as the original value did when it was inserted in the tree. Thus, the duplicate will eventually be compared with a node containing the same value. The duplicate value may be discarded at this point.

Searching a binary tree for a value that matches a key value is also fast. If the tree is balanced, then each branch contains about half the number of nodes in the tree. Each comparison of a node to the search key eliminates half the nodes. This is called an O (log n) algorithm (Big O notation is discussed in Chapter 20). So a binary search tree with n elements would require a maximum of log2 n comparisons either to find a match or to determine that no match exists. This means, for example, that when searching a (balanced) 1000-element binary search tree, no more than 10 comparisons need to be made, because 210 > 1000. When searching a (balanced) 1,000,000-element binary search tree, no more than 20 comparisons need to be made, because 220 > 1,000,000.

Overview of the Binary Tree Exercises

In the exercises, algorithms are presented for several other binary tree operations such as deleting an item from a binary tree, printing a binary tree in a two-dimensional tree format 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, the nodes are visited from left to right. Other binary tree exercises include allowing a binary search tree to contain duplicate values, inserting string values in a binary tree and determining how many levels are contained in a binary tree.