19.6 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. 19.18)—trees whose nodes all contain two links (none, one or both of which may have the value nullptr).
19.6.1 Basic Terminology
For this discussion, refer to nodes A, B, C and D in Fig. 19.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 given node are called siblings (e.g., nodes A and D are siblings). A node with no children is a leaf node (e.g., nodes A and C are leaf nodes). Computer scientists normally draw trees from the root node down—the opposite of how trees grow in nature.
Fig. 19.18 A graphical representation of a binary tree.
19.6.2 Binary Search Trees
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 19.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.
Fig. 19.19 A binary search tree.
Implementing the Binary Search Tree Program
The program of Figs. 19.20–19.22 creates a binary search tree and traverses it (i.e., walks through all its nodes) three ways—using recursive inorder, preorder and postorder traversals. We explain these traversal algorithms shortly.
19.6.3 Testing the Tree Class Template
We begin our discussion with the driver program (Fig. 19.20), then continue with the implementations of classes TreeNode (Fig. 19.21) and Tree (Fig. 19.22). Function main (Fig. 19.20) begins by instantiating integer tree intTree of type Tree<int> (line 9). The program prompts for 10 integers, each of which is inserted in the binary tree by calling insertNode (line 17). The program then performs preorder, inorder and postorder traversals (these are explained shortly) of intTree (lines 21, 24 and 27, respectively). Next, we instantiate floating-point tree doubleTree of type Tree<double> (line 29), then prompt for 10 double values, each of which is inserted in the binary tree by calling insertNode (line 38). Finally, we perform preorder, inorder and postorder traversals of doubleTree (lines 42, 45 and 48, respectively).
Fig. 19.20 Creating and traversing a binary tree.
Alternate View
1 // Fig. 19.20: fig19_20.cpp
2 // Creating and traversing a binary tree.
3 #include <iostream>
4 #include <iomanip>
5 #include "Tree.h" // Tree class definition
6 using namespace std;
7
8 int main() {
9 Tree<int> intTree; // create Tree of int values
10
11 cout << "Enter 10 integer values:
";
12
13 // insert 10 integers to intTree
14 for (int i{0}; i < 10; ++i) {
15 int intValue = 0;
16 cin >> intValue;
17 intTree.insertNode(intValue);
18 }
19
20 cout << "
Preorder traversal
";
21 intTree.preOrderTraversal();
22
23 cout << "
Inorder traversal
";
24 intTree.inOrderTraversal();
25
26 cout << "
Postorder traversal
";
27 intTree.postOrderTraversal();
28
29 Tree<double> doubleTree; // create Tree of double values
30
31 cout << fixed << setprecision(1)
32 << "
Enter 10 double values:
";
33
34 // insert 10 doubles to doubleTree
35 for (int j{0}; j < 10; ++j) {
36 double doubleValue = 0.0;
37 cin >> doubleValue;
38 doubleTree.insertNode(doubleValue);
39 }
40
41 cout << "
Preorder traversal
";
42 doubleTree.preOrderTraversal();
43
44 cout << "
Inorder traversal
";
45 doubleTree.inOrderTraversal();
46
47 cout << "
Postorder traversal
";
48 doubleTree.postOrderTraversal();
49 cout << endl;
50 }
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
19.6.4 Class Template TreeNode
The TreeNode class template (Fig. 19.21) definition declares Tree<NODETYPE> as its friend (line 12). This makes all member functions of a given specialization of class template Tree (Fig. 19.22) 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 20–22 declare a TreeNode’s private data—the node’s data value, and pointers leftPtr (to the node’s left subtree) and rightPtr (to the node’s right subtree). Both pointers are initialized to nullptr—thus initializing this node to be a leaf node. The constructor (line 15) sets data to the value supplied as a constructor argument. Member function getData (line 18) returns the data value.
Fig. 19.21 TreeNode class-template definition.
Alternate View
1 // Fig. 19.21: TreeNode.h
2 // TreeNode class-template 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 friend class Tree<NODETYPE>;
13 public:
14 // constructor
15 TreeNode(const NODETYPE& d) : data{d} {}
16
17 // return copy of node"s data
18 NODETYPE getData() const {return data;}
19 private:
20 TreeNode<NODETYPE>* leftPtr{nullptr}; // pointer to left subtree
21 NODETYPE data;
22 TreeNode<NODETYPE>* rightPtr{nullptr}; // pointer to right subtree
23 };
24
25 #endif
19.6.5 Class Template Tree
Class template Tree (Fig. 19.22) has as private data rootPtr (line 33), a pointer to the tree’s root node that’s initialized to nullptr to indicate an empty tree. The class’s public member functions are insertNode (lines 13–15) that inserts a new node in the tree and preOrderTraversal (lines 18–20), inOrderTraversal (lines 23–25) and postOrderTraversal (lines 28–30), each of which walks the tree in the designated manner. Each of these member functions calls its own 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.
Fig. 19.22 Tree class-template definition.
Alternate View
1 // Fig. 19.22: Tree.h
2 // Tree class-template definition.
3 #ifndef TREE_H
4 #define TREE_H
5
6 #include <iostream>
7 #include "TreeNode.h"
8
9 // Tree class-template definition
10 template<typename NODETYPE> class Tree {
11 public:
12 // insert node in Tree
13 void insertNode(const NODETYPE& value) {
14 insertNodeHelper(&rootPtr , value);
15 }
16
17 // begin preorder traversal of Tree
18 void preOrderTraversal() const {
19 preOrderHelper(rootPtr);
20 }
21
22 // begin inorder traversal of Tree
23 void inOrderTraversal() const {
24 inOrderHelper(rootPtr);
25 }
26
27 // begin postorder traversal of Tree
28 void postOrderTraversal() const {
29 postOrderHelper(rootPtr);
30 }
31
32 private:
33 TreeNode<NODETYPE>* rootPtr{nullptr};
34
35 // utility function called by insertNode; receives a pointer
36 // to a pointer so that the function can modify pointer"s value
37 void insertNodeHelper(
38 TreeNode<NODETYPE>** ptr, const NODETYPE& value) {
39 // subtree is empty; create new TreeNode containing value
40 if (*ptr == nullptr) {
41 *ptr = new TreeNode<NODETYPE>(value);
42 }
43 else { // subtree is not empty
44 // data to insert is less than data in current node
45 if (value < (*ptr )->data) {
46 insertNodeHelper(&((*ptr)->leftPtr), value);
47 }
48 else {
49 // data to insert is greater than data in current node
50 if (value > (*ptr)->data) {
51 insertNodeHelper(&((*ptr)->rightPtr), value);
52 }
53 else { // duplicate data value ignored
54 cout << value << " dup" << endl;
55 }
56 }
57 }
58 }
59
60 // utility function to perform preorder traversal of Tree
61 void preOrderHelper (TreeNode<NODETYPE>* ptr) const {
62 if (ptr != nullptr) {
63 cout << ptr->data << ' '; // process node
64 preOrderHelper(ptr->leftPtr); // traverse left subtree
65 preOrderHelper(ptr->rightPtr); // traverse right subtree
66 }
67 }
68
69 // utility function to perform inorder traversal of Tree
70 void inOrderHelper (TreeNode<NODETYPE>* ptr) const {
71 if (ptr != nullptr) {
72 inOrderHelper(ptr->leftPtr); // traverse left subtree
73 cout << ptr->data << ' '; // process node
74 inOrderHelper(ptr->rightPtr); // traverse right subtree
75 }
76 }
77
78 // utility function to perform postorder traversal of Tree
79 void postOrderHelper (TreeNode<NODETYPE>* ptr) const {
80 if (ptr != nullptr) {
81 postOrderHelper(ptr->leftPtr); // traverse left subtree
82 postOrderHelper(ptr->rightPtr); // traverse right subtree
83 cout << ptr->data << ' '; // process node
84 }
85 }
86 };
87
88 #endif
19.6.6 Tree Member Function insertNodeHelper
The Tree class’s utility function insertNodeHelper (lines 37–58) is called by insertNode (lines 13–15) 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 40–42).
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 45), the program recursively calls insertNodeHelper (line 46) to insert the value in the left subtree. If the insert value is larger (line 50), the program recursively calls insertNodeHelper (line 51) 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 54) and returns without inserting the duplicate value into the tree. Note that insertNode passes the address of rootPtr to insertNodeHelper (line 14) 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.
19.6.7 Tree Traversal Functions
Member functions preOrderTraversal (lines 18–20), inOrderTraversal (lines 23–25) and postOrderTraversal (lines 28–30) traverse the tree and print the node values. For the purpose of the following discussion, we use the binary search tree in Fig. 19.23.
Fig. 19.23 A binary search tree.
Inorder Traversal Algorithm
Function inOrderTraversal invokes utility function inOrderHelper (lines 70–76) to perform the inorder traversal of the binary tree. The steps for an inorder traversal are:
Traverse the left subtree with an inorder traversal. (This is performed by the call to
inOrderHelperat line 72.)Process the value in the node—i.e., print the node value (line 73).
Traverse the right subtree with an inorder traversal. (This is performed by the call to
inOrderHelperat line 74.)
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. 19.23 is
6 13 17 27 33 42 48
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—thus, this process is called the binary tree sort.
Preorder Traversal Algorithm
Function preOrderTraversal invokes utility function preOrderHelper (lines 61–67) to perform the preorder traversal of the binary tree. The steps for a preorder traversal are:
Process the value in the node (line 63).
Traverse the left subtree with a preorder traversal. (This is performed by the call to
preOrderHelperat line 64.)Traverse the right subtree with a preorder traversal. (This is performed by the call to
preOrderHelperat line 65.)
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. 19.23 is
27 13 6 17 42 33 48
Postorder Traversal Algorithm
Function postOrderTraversal invokes utility function postOrderHelper (lines 79–85) to perform the postorder traversal of the binary tree. The steps for a postorder traversal are:
Traverse the left subtree with a postorder traversal. (This is performed by the call to
postOrderHelperat line 81.)Traverse the right subtree with a postorder traversal. (This is performed by the call to
postOrderHelperat line 82.)Process the value in the node (line 83).
The value in each node is not printed until the values of its children are printed. The postOrderTraversal of the tree in Fig. 19.23 is
6 17 13 33 48 42 27
19.6.8 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 is also fast. If the tree is balanced, then each branch contains about half the 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 comparisons either to find a match or to determine that no match exists. For example, searching a (balanced) 1000-element binary search tree requires no more than 10 comparisons, because . Searching a (balanced) 1,000,000-element binary search tree requires no more than 20 comparisons, because .
19.6.9 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.