Computer Science - C++ Lesson 37:
Binary Tree Algorithms
OBJECTIVES:
The student will code a recursive algorithm to print out a binary tree using an inorder traversal.
The student will predict the output of a preorder and postorder traversal of a binary tree
The student will code a searching algorithm to locate a value in a binary tree.
INTRODUCTION:
Having built a binary tree in the memory of your computer, we need the algorithms to verify that the tree is indeed ordered. The recursive inorder algorithm is elegant, clean, but difficult to follow. You must understand this algorithm, for it provides a template for many binary tree routines. Once convinced that the tree is correct we will code a recursive search algorithm.
The key topics for this lesson are:
A.
Inorder Tree Traversal
B. Preorder
and Postorder Tree Traversals
C. Counting
the Nodes in a Tree
D. Searching
a Binary Tree
VOCABULARY:
INORDER | TREE TRAVERSAL |
PREORDER | VISITING A NODE |
POSTORDER |
DISCUSSION:
A.
Inorder Tree Traversal
2. As a review, assume the following type definitions apply in this student outline.
struct treeNode
{
int data;
treeNode *left, *right;
// struct constructor declaration
};
typedef treeNode* treePtr;
3. A tree traversal is an algorithm which visits every node in the tree. To visit a node means to process something regarding the data stored in the node. For now, visiting the node will involve printing the data field.
4. An inorder tree traversal visits every node in a certain order. Each node is processed in the following sequence:
Solve left subtree inorder
Visit node
Solve right subtree inorder
Notice that visiting the node is placed between the two recursive calls.
5. Here is the code for function inorder:
void inorder (treePtr temp)
{
if (temp != NULL)
{
inorder (temp->left);
cout << temp->data << endl;
inorder (temp->right);
}
}
6. The first call of inorder is asked to process the root node. The first step of the function is a recursive call of inorder to process the left pointer of the root node. This recursive call to solve the left pointer will take place before the cout statement.
7. Solving for the node with value 14 results in another recursive call to solve the left pointer to the node having value 9. The inorder to process the node with value 9 in turn calls inorder which hits a NULL. This recursive call results in nothing executed.
8. The recursion backtracks to the inorder processing the node with value 9. Our first cout occurs and the value 9 is printed. We recursively visit the node to the right and since nothing is there, we return to the node with value 9.
9. For the node with value 9, we have now done all three steps. We checked left, printed the 9, and checked right. This function call is done and we backtrack to where we left off, which is processing the node with value 14.
10. From here, the recursion will continue
working its way through the tree. Inorder
calls which are postponed are placed on the stack.
When a call of inorder is
completed, the program will go to the stack (if necessary) to backtrack through
the tree.
B. Preorder and Postorder Tree Traversals
1. A preorder tree traversal processes each node in a different order.
Visit the node
Process the left subtree preorder
Process the right subtree preorder
The only difference is that we will print first, then go left, then right. The preorder output of the same binary tree will be:
26 14 9 21 79 53 35 99 87
2. A postorder tree traversal has this order:
Process left subtree postorder
Process right subtree postorder
Visit the node
The prefix “post” refers to after, hence the location of visiting the node after the recursive calls. The printout of the same tree will be as follows:
9
21 14
35 53 87
99 79
26
C. Counting the Nodes in a Tree
1. A standard binary tree algorithm is to count the number of nodes in the tree. Here is a pseudocode version.
Count
left subtree recursively
Count
the current node as one
Count right subtree recursively
2. As you develop the code, consider what base case will terminate the solution.
D. Searching a Binary Tree
1. Searching an ordered binary tree can be solved iteratively or recursively. Here is the iterative version.
treePtr search (treePtr temp, int idToFind)
{
treePtr back;
while ((temp != NULL) && (idToFind != temp->data))
{
back = temp;
if (idToFind < temp->data)
temp = temp->left;
else
temp = temp->right;
}
return temp;
}
2. If the value is not in the tree, the temp pointer will eventually hit a NULL.
3. A recursive version is left for you to solve as part of the lab exercise.
4. The order of searching an ordered binary tree is O(log2N) for the best case situation. For a perfectly balanced tree, the capacity of each level is 2level #.
Level #
Capacity of Level
Capacity of Tree
0
1
1
1
2
3
2
4
7
3
8
15
4
16
31
5
32
63
etc.
5.
So starting at the root node, a tree of 63 nodes would require a maximum
of 5 left or right moves to find a value. The
number of steps in searching an ordered binary tree is approximately O(log2N).
SUMMARY/REVIEW:
The most important topic of this lesson is recursive algorithms required
to process binary trees. Study the
examples, draw pictures, do whatever it takes to understand recursive tree
traversals. Many of the algorithms
in future lessons will require recursion.
ASSIGNMENT:
Worksheet W.A.37.1, Recursive Tree Traversals
Lab Exercise L.A.37.1, BTree
BTree (continued) Assignment:
1.
Continuing the lab exercise L.A.36.1, BTree,
from the previous lesson, add function inorder to print out the binary tree. Format the output into two columns, Id and Inv amounts.
2. Complete the search and countNode algorithms.