www.gibmonks.com

Main Page

[Page 1025]

21.7. 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).

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.

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

[Page 1026]

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

[Page 1027]

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 <iostream>
4  using std::cout;
5  using std::cin;
6  using std::fixed;
7
8  #include <iomanip>
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:\n";
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 << "\nPreorder traversal\n";
28     intTree.preOrderTraversal();
29
30     cout << "\nInorder traversal\n";
31     intTree.inOrderTraversal();
32
33     cout << "\nPostorder traversal\n";
34     intTree.postOrderTraversal();
35
36     Tree< double > doubleTree; // create Tree of double values
37     double doubleValue;
38
39     cout << fixed << setprecision( 1 )
40        << "\n\n\nEnter 10 double values:\n";
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 << "\nPreorder traversal\n";
50     doubleTree.preOrderTraversal();
51
52     cout << "\nInorder traversal\n";
53     doubleTree.inOrderTraversal();
54
55     cout << "\nPostorder traversal\n";
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 ```

[Page 1029]

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.

[Page 1031]

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.

[Page 1032]

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.

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

[Page 1033]

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.