Previous Section
 < Free Open Study > 
Next Section


8.5 Recursive Binary Search Tree Operations

The TreeType class contains the external pointer to the list of nodes as a data member (root). The recursive implementations of the tree operations should reçurse on nodes. Therefore each member function calls a secondary recursive function that takes root as a parameter. The names of the secondary functions make it clear which operations they help to implement. Because we must declare a function before we can use it, we must list each recursive function before the class function or we must list its prototype. Because it is easy to forget to place them in what seems like reverse order, it is a good idea to list the prototypes at the beginning of the implementation. We now develop these recursive functions.

The Functions IsFull and IsEmpty

The observer functions are identical to those used in a linear linked implementation. We can just borrow the code, using the appropriate variable names.

bool TreeType::IsFull() const
// Returns true if the free store has no room for another node
//  and false otherwise.
{
  TreeNode* location;
  try
  {
    location = new TreeNode;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

bool TreeType::IsEmpty() const
// Returns true if the tree is empty and false otherwise.
{
return root == NULL;
}

The Function LengthIs

In the function Factorial, we could determine the factorial of N if we knew the factorial of N - 1. The analogous statement here is that we can determine the number of nodes in the tree if we know the number of nodes in the left subtree and the number of nodes in the right subtree. That is, the number of nodes in a tree is

  • Number of nodes in left subtree + number of nodes in right subtree + 1

This is easy. Given a function CountNodes and a pointer to a tree node, we know how to calculate the number of nodes in a subtree; we call CountNodes recursively with the pointer to the subtree as the argument! Thus we know how to write the general case. What about the base case? A leaf node has no subtrees, so the number of nodes is 1. How do we determine that a node has no subtrees? The pointers to its children are NULL. Let's try summarizing these observations into an algorithm, where tree is a pointer to a node.

Let's try this algorithm on a couple of examples to be sure that it works (see Figure 8.5).

Click To expand
Figure 8.5: Two binary search trees

We call CountNodes with the tree in Figure 8.5(a). The left and right children of the root node (M) are not NULL, so we call CountNodes with the node containing A as the root. Because both the left and right children are NULL on this call, we send back the answer 1. Now we call CountNodes with the tree containing Q as the root. Both of its children are NULL, so we send back the answer 1. Now we can calculate the number of nodes in the tree with M in the root:

1+1+1=3

This seems to work correctly.

The tree in Figure 8.5(b) is not balanced; let's see if this condition poses a problem. It is not true that both children of the root (L) are NULL, so CountNodes is called with the left child as the argument. Oops-we do have a problem. The first statement checks

whether the children of the root are NULL, but the root itself is NULL. The function crashes when we try to access tree->left when tree is NULL. Well, we can check whether the left or right child is NULL, and not call CountNodes if it is.

Version 2 works correctly if the function CountNodes has a precondition that the tree is not empty. However, an initially empty tree causes a crash. We must check whether the tree is empty as the first statement in the algorithm and, if it is, return zero.

This algorithm certainly looks complicated. There must be a simpler solution-and there is. We can collapse the two base cases into one. There is no need to turn the leaf node into a special case. We can simply have one base case: An empty tree returns zero.

We have taken the time to work through the versions containing errors because they illustrate two important points about recursion with trees: (1) always check for the empty tree first, and (2) leaf nodes do not need to be treated as separate cases. Table 8.1 reviews the design notation and the corresponding C++ code.

Table 8.1: Comparing Node Design Notation to C++ Code

Design Notation

C++ Code

Node(location)

*location

Info(location)

location->info

Right(location)

location->right

Left(location)

location->left

Set Info(location) to value

location->info = value

Here is the function specification:

int CountNodes(TreeNode* tree);

int TreeType::LengthIs() const
// Calls the recursive function CountNodes to count the
//  nodes in the tree.
{
  return CountNodes(root);
}

int CountNodes(TreeNode* tree)
// Post: Returns the number of nodes in the tree.
}
  if (tree == NULL)
    return 0;
  else
    return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

The Function RetrieveItem

At the beginning of this chapter, we demonstrated how to search for an element in a binary search tree. That is, we first check whether the item is in the root. If it is not, we compare the element with the root and look in either the left or the right subtree. This statement looks recursive. Let's apply the general guidelines for determining recursive solutions.

We have two choices for the size of the problem: the number of nodes in the tree or the number of nodes in the path from the root to the node for which we are searching (or until we reach an empty tree). Either is acceptable. The first is easier to say; the second is more precise. One base case arises when we find the element with the same key; another occurs when we determine that an element with the same key is not in the tree. The general case is either to retrieve the element from the left subtree or to retrieve it from the right subtree. Because the left or right subtree is at least one node smaller than the original tree and one level deeper, the size decreases with each call.

Only one question remains: How do we know there is no item with the same key in the tree? If the tree is empty, then it cannot contain an item with the same key as item's key. Let's summarize these observations. We define a recursive routine Retrieve, which is invoked by the RetrieveItem member function.

void Retrieve(TreeNode* tree,
     ItemType& item, bool& found);

void TreeType::RetrieveItem(ItemType& item, bool& found) const
// Calls recursive function Retrieve to search the tree for item.
{
  Retrieve(root, item, found);
}

void Retrieve(TreeNode* tree,
     ItemType& item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
//       found is true and item is set to a copy of someItem;
//       otherwise, found is false and item is unchanged.
{
  if (tree == NULL)
    found = false;                      // item is not found.
  else if (item < tree->info)
    Retrieve(tree->left, item, found); // Search left subtree.
  else if (item > tree->info)
    Retrieve(tree->right, item, found);// Search right subtree.
  else
  {
    item = tree->info;                 // item is found.
    found = true;
  }
)

Let's trace this operation, using the tree in Figure 8.6. We want to find the element with the key 18, so the nonrecursive call is

Click To expand
Figure 8.6: Tracing the Retrieve operation
Retrieve(root, 18, found)

root is not NULL, and 18 > tree->info, so we issue the first recursive call:

Retrieve(tree->right, 18, found)

tree now points to the node whose key is 20 so 18 < tree->info. The next recursive call is

Retrieve(tree->left, 18, found)

Now tree points to the node with the key 18 so 18 = tree->info. We set found and item, and the recursion halts.

Next, let's look at an example where the key is not found in the tree. We want to find the element with the key 7. The nonrecursive call is

Retrieve(root, 7, found)

tree is not NULL and 7 < tree->info, so the first recursive call is

Retrieve(tree->left, 7, found)

tree points to the node that contains 9. tree is not NULL, and we issue the second recursive call:

Retrieve(tree->left, 7, found)

Now tree is NULL; we set found to false, and item is unchanged.

The Function InsertItem

To create and maintain the information stored in a binary search tree, we need an operation that inserts new nodes into the tree. We use the following insertion approach. A new node is always inserted into its appropriate position in the tree as a leaf. Figure 8.7 shows a series of insertions into a binary tree.

Click To expand
Figure 8.7: Insertions into a binary search tree

We want to write a function Insert that inserts an item into the tree, given a pointer to the root of the whole tree:

insert(tree, item);

Before developing the algorithm, we want to reiterate that every node in a binary search tree is the root node of a binary search tree. In Figure 8.8(a), we want to insert a node with the key value 13 into the tree whose root is the node containing 7. Because 13 is greater than 7, we know that the new node belongs in the root node's right subtree. We have now redefined a smaller version of our original problem: We want to insert a node with the key value 13 into the tree whose root is tree->right (Figure 8.8b). Of course, we already have a function to insert elements into a binary search tree: Insert. Insert is called recursively:

Insert(tree->right, item);

Click To expand
Figure 8.8: The recursive Insert operation

Insert begins its execution, looking for the place to insert item in the tree whose root is the node with the key value 15. We compare the key of item (13) to the key of the root node; 13 is less than 15, so we know that the new item belongs in the tree's left subtree. Again, we have redefined a smaller version of the problem: We want to insert a node with the key value 13 into the tree whose root is tree->left (Figure 8.8c). We call Insert recursively to perform this task. Remember that in this (recursive) execution of Insert, tree points to the node whose key is 15, not the original tree root:

Insert(tree->left, item);

Again, we recursively execute Insert. We compare the key of item to the key of the (current) root node and then call Insert to insert item into the correct subtree-the left subtree if item's key is less than the key of the root node, and the right subtree if item's key is greater than the key of the root node.

Where does it all end? There must be a base case, in which space for the new element is allocated and the value of item copied into it. This case occurs when tree is NULL, when the subtree we wish to insert into is empty. (Remember-we will add item as a leaf node.) Figure 8.8(d) illustrates the base case. We can create the new node and link it to the correct member of its logical parent with the following statement:

tree = new TreeNode;

Wait a minute! How does this execution of new link the new node to the existing tree? To understand this point, we must consider the meaning of tree in a recursive execution of the function. The last recursive call (Figure 8.9a) is Insert(tree-> right, item). Because tree is a reference parameter, in the final recursive execution of Insert, tree refers to the right data member of the node containing 10 (the logical parent of the new node). The statement executing new gets the address of the new node and stores it into tree, the right data member of the node containing 10, thereby linking the new node into the tree structure (Figure 8.9b). It is critical that tree be a reference parameter. If it is not, the pointer passed to Insert will be a copy of the root of the subtree and not the location of the root itself.

Click To expand
Figure 8.9: The tree parameter is a pointer within the tree

This technique should sound familiar. We used it in Chapter 7 when we inserted an element into a linked implementation of a sorted list recursively. The important point to remember is that passing a pointer by value allows the function to change what the caller's pointer points to; passing a pointer by reference allows the function to change the caller's pointer as well as to change what the pointer points to. The recursive function is summarized as follows:

Here is the code that implements this recursive algorithm:

void Insert(TreeNode*& tree, ItemType item);

void TreeType::InsertItem(ItemType item)
// Calls the recursive function Insert to insert item into tree.
{
  Insert(root, item):
}


void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post: item is in tree; search property is maintained.
{
  if (tree == NULL)
  {// Insertion place found.
    tree = new TreeNode;
    tree->right = NULL;
    tree->left = NULL:
    tree->info = item;
  }
  else if (item < tree->info)
    Insert(tree->left, item);     // Insert in left subtree.
  else
    Insert(tree->right, item);    // Insert in right subtree.
}

Insertion Order and Tree Shape Because we always add nodes as leaves, the order in which we insert nodes determines the shape of the tree. Figure 8.10 illustrates how the same data, inserted in different orders, produce very differently shaped trees. If the values are inserted in order (or in reverse order), the tree will be very skewed. A random mix of the elements produces a shorter, "bushy" tree. Because the height of the tree determines the maximum number of comparisons in a search, the tree's shape has very important implications. Obviously, minimizing the height of the tree maximizes the efficiency of the search. Some algorithms adjust a tree to make its shape more desirable; these schemes are subjects for more advanced courses.

Click To expand
Figure 8.10: The input order determines the shape of the tree

The Function DeleteItem

Delete (the recursive helper function for DeleteItem) receives the external pointer to a binary search tree and an item, and then finds and deletes the node matching the item's key from the tree. According to the specifications of the operation, an item with the same key exists in the tree. These specifications suggest a two-part operation:

We know how to find the node; we did it in Retrieve. The second part of the operation-deleting this node from the tree-is more complicated. This task varies according to the position of the node in the tree. Obviously, it is simpler to delete a leaf node than to delete the root of the tree. In fact, we can break down the deletion algorithm into three cases, depending on the number of children linked to the node we want to delete:

  1. Deleting a leaf (no children): As shown in Figure 8.11, deleting a leaf is simply a matter of setting the appropriate link of its parent to NULL and then disposing of the unnecessary node.

    Click To expand
    Figure 8.11: Deleting a leaf node

  2. Deleting a node with only one child: The simple solution for deleting a leaf does not suffice for deleting a node with a child, because we don't want to lose all of its descendants from the tree. Instead, we want the pointer from the parent to skip over the deleted node and point to the child of the node we intend to delete. We then dispose of the unwanted node (see Figure 8.12).

    Click To expand
    Figure 8.12: Deleting a node with one child

  3. Deleting a node with two children: This case is the most complicated because we cannot make the parent of the deleted node point to both of the deleted node's children. The tree must remain a binary tree, and the search property must remain intact. We have several ways to accomplish this deletion. The method we use does not delete the node but rather replaces its info data member with the info data member from another node in the tree that maintains the search property. We then delete this other node.

    Which element could we use to replace the deleted item that would maintain the search property? The elements whose keys immediately precede or follow item's-that is, item's logical predecessor or successor. We replace the info data member of the node we wish to delete with the info data member of its logical predecessor-the node whose key is closest in value to, but less than, the key of the node to be deleted. Look at Figure 8.7(j) and locate the logical predecessor of nodes 5, 9, and 7. Do you see the pattern? The logical predecessor of 5 is the largest value in 5's left subtree. The logical predecessor of 9 is the largest value in 9's left subtree. The logical predecessor of 7 is 6, the largest value in 7's left subtree. This replacement value is found in a node with either zero or one child. We then delete the node originally containing the replacement value by changing one of its parent's pointers (see Figure 8.13). Figure 8.14 shows examples of all of these types of deletions.

    Click To expand
    Figure 8.13: Deleting a node with two children

    Click To expand
    Figure 8.14: Deletions from a binary search tree

Clearly, the delete task involves changing pointers of the parent of the node to be deleted. If our recursive algorithm passes tree as a reference parameter, then tree itself is the parent that we must change. Let's look at the three cases in terms of our implementation.

If both child pointers are NULL, the node is a leaf, so we just set tree to NULL. If one child pointer is NULL, we set tree to the other child pointer. If neither child pointer is NULL, we replace the info data member of tree with the info data member of the node's logical predecessor and delete the node containing the predecessor. Let's summarize this algorithm as DeleteNode.

Now we can write the recursive definition and code for Delete.

void DeleteNode(TreeNode*& tree);

void Delete(TreeNode*& tree, ItemType item);

void TreeType::DeleteItem(ItemType item)
// Calls the recursive function Delete to delete item from tree.
{
  Delete(root, item);
}

void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post:  item is not in tree.
{
  if (item < tree->info)
    Delete(tree->left, item);    // Look in left subtree.
  else if (item > tree->info)
    Delete(tree->right, item);   // Look in right subtree.
  else
    DeleteNode(tree);            // Node found; call DeleteNode.
}

Before we code DeleteNode, let's look at it again. We can remove one of the tests if we notice that the action taken when the left child pointer is NULL also takes care of the case in which both child pointers are NULL. When the left child pointer is NULL, the right child pointer is stored into tree. If the right child pointer is also NULL, then NULL is stored into tree, which is what we want if both are NULL.

In good top-down fashion, let's now write the code for DeleteNode using GetPredecessor as the name of an operation that returns a copy of the info data member of the predecessor of the node with two children.

void GetPredecessor(TreeNode* tree, ItemType& data);

void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user's data in the node pointed to by tree is no
//       longer in the tree.  If tree is a leaf node or has only one
//       non-NULL child pointer, the node pointed to by tree is
//       deleted; otherwise, the user's data is replaced by its
//       logical predecessor and the predecessor's node is deleted.
{
  ItemType data;
  TreeNode* tempPtr;

  tempPtr = tree;
  if (tree->left == NULL)
  {
    tree = tree->right;
    delete tempPtr;
  }
  else if (tree->right == NULL)
  {
    tree = tree->left;
    delete tempPtr;
  }
  else
  {
    GetPredecessor(tree->left, data);
    tree->info = data;
    Delete(tree->left, data);  // Delete predecessor node.
  }
}

Next, we look at the operation for finding the logical predecessor. We know that the logical predecessor is the maximum value in tree's left subtree. Where is this node found? The maximum value in a binary search tree is located in its rightmost node. Therefore, given tree's left subtree, we just keep moving right until the right child is NULL. When this event occurs, we set data to the info member of the node. We have no reason to look for the predecessor recursively in this case. A simple iteration until tree->right is NULL suffices.

void GetPredecessor(TreeNode* tree, ItemType& data)
// Sets data to the info member of the rightmost node in tree.
{
  while (tree->right != NULL)
    tree = tree->right;
  data = tree->info;
}

The Function Print

To traverse a linear linked list, we set a temporary pointer equal to the start of the list and then follow the links from one node to the other until we reach a node whose pointer value is NULL. Similarly, to traverse a binary tree, we initialize our pointer to the root of the tree. But where do we go from there-to the left or to the right? Do we access the root or the leaves first? The answer is "all of these." There are only two ways to traverse a list: forward and backward. In contrast, there are many ways to traverse a tree.

An inorder traversal accesses the nodes in such a way that the values in the nodes are accessed in order from the smallest to the largest. This technique is the one we want for Print.

First, we print the root's left subtree-that is, all values in the tree that are smaller than the value in the root node. Next, we print the value in the root node. Finally, we print the values in the root's right subtree-that is, all the values that are larger than the value in the root node (see Figure 8.15).

Click To expand
Figure 8.15: Printing all the nodes in order

Let's describe this problem again, thinking recursively (and writing a recursive helper function named Print). We want to print the elements in the binary search tree rooted at tree in order; that is, first we print the left subtree in order, then we print the root, and finally we print the right subtree in order. Of course, tree->left points to the root of the left subtree. Because the left subtree is also a binary search tree, we can call the function Print to print it, using tree->left as the root parameter. When Print finishes printing the left subtree, we print the value in the root node. Then we call Print to print the right subtree with tree->right as the root parameter.

Both calls to the function Print use the same approach to print the subtree: Print the left subtree with a call to Print, print the root, and then print the right subtree with another call to Print. What happens if the incoming parameter is NULL on one of the recursive calls? This event signals that the parameter is the root of an empty tree. In this case, we just want to exit the function-clearly, there's no point to printing an empty subtree.

This description can be coded into the following recursive function. For simplicity, we assume that tree->info can be output directly using the stream insertion operator. Here is the helper function that does the printing.

void PrintTree(TreeNode* tree, std::ofstream& outFile)
// Prints info member of items in tree in sorted order on outFile.
{
  if (tree != NULL)
  {
    PrintTree(tree->left, outFile);   // Print left subtree.
    outFile << tree->info;
    PrintTree(tree->right, outFile);  // Print right subtree.
  }
)

This traversal is called an inorder traversal because it accesses each node's left subtree before it processes (prints) the information in the node itself, and then accesses the node's right subtree.

Finally, the Print member function of the TreeType class invokes PrintTree as follows:

void TreeType::Print(std::ofstream& outFile) const
// Calls recursive function Print to print items in the tree.
{
  PrintTree(root, outFile);
}

The Class Constructor and Destructor

The default class constructor simply creates an empty tree by setting root to NULL. As there is no other logical way of constructing an empty tree, we do not provide a parameterized constructor.

TreeType::TreeType()
{
  root = NULL;
}

In the same way that the class constructor takes care of each class object's initialization, the class destructor takes care of deallocating dynamic nodes when a class object goes out of scope. The operation invokes a recursive routine with the pointer to a binary search tree as a parameter and destroys all the nodes, leaving the tree empty. To delete the elements, we have to traverse the tree. Instead of printing each element, as we did in the previous section, we remove the node from the tree. We said that there is more than one way to traverse a binary tree. Is there a preferred way to destroy the tree?

While any of the traversals would result in the function working correctly, one traversal order is more efficient than the others. Knowing that the DeleteNode operation does less work to delete a leaf node than a node with children, we want to delete leaves first. The traversal that allows us to access leaf nodes first is called a postorder traversal: We access each node's left subtree and its right subtree before we process the node itself. If you delete the nodes in postorder, each node is a leaf by the time it is its turn to be deleted. The code for the destructor follows:

void Destroy(TreeNode*& tree);

TreeType::~TreeType()
// Calls recursive function Destroy to destroy the tree.
{
  Destroy(root);
)

void Destroy(TreeNode*& tree)
// Post: tree is empty; nodes have been deallocated.
{
  if (tree != NULL)
  {
    Destroy(tree->left);
    Destroy(tree->right);
    delete tree;
  }
}

The body of the MakeEmpty member function is identical to that of the class destructor, with one exception: After the call to Destroy, it must set root to NULL.

Copying a Tree

Both the copy constructor and the overloading of the assignment operator involve making a copy of a tree. Copying a tree may be the most interesting-and complex- algorithm associated with trees. Clearly, it entails a recursive algorithm. We must do what we did with all the other member functions: Call an auxiliary recursive function with root as a parameter. Both the copy constructor and the assignment operator must call this function.

void CopyTree(TreeNode*& copy,
     const TreeNode* originalTree);

TreeType::TreeType(const TreeType& originalTree)
// Calls the recursive function CopyTree to copy originalTree
//  into root.
{
  CopyTree(root, originalTree.root);
}

void TreeType::operator=
     (const TreeType& originalTree)
// Calls the recursive function CopyTree to copy originalTree
// into root.
{
  {
    if (&originalTree == this)
      return;              // Ignore assigning self to self.
    Destroy(root);         // Deallocate existing tree nodes.
    CopyTree(root, originalTree.root);
  }
}

The recursive function CopyTree has two parameters, both pointers to tree nodes. Let's call them copy and otherTree. What is the base case? If otherTree is NULL, then copy is NULL. What is copy if otherTree is not NULL? We get a node for copy to point to and put otherTree->info into it. We then store a copy of otherTree's left subtree into copy's left child and store a copy of otherTree's right subtree into copy's right child. Where do we get a copy of the subtrees? We use CopyTree recursively, of course.

void CopyTree(TreeNode*& copy,
     const TreeNode* originalTree)
// Post: copy is the root of a tree that is a duplicate
//       of originalTree.
{
  if (originalTree == NULL)
    copy = NULL;
  else
  {
    copy = new TreeNode;
    copy->info = originalTree->info;
    CopyTree(copy->left, originalTree->left);
    CopyTree(copy->right, originalTree->right);
  }
}

Be sure you understand how this code works before going on to the next section. Like many recursive algorithms, this short function is elegant but not obvious. In fact, let's trace CopyTree on the following tree:

Click To expand

As in Chapter 7, RO stands for the nonrecursive call, R1 stands for the first recursive call (copy->left), and R2 stands for the second recursive call (copy->right). In the trace, an arrow pointing to the contents of a node stands for the pointer to that node. A Comments column in the table shows the trace.

Call

copy

originalTree

Return

Comment

1

external pointer to new tree

L

RO

copy is given a node to point to; L is copied into the info member; R1 is executed

2

left of node allocated in call 1

D

R1

copy is given a node to point to; D is copied into the info member; R1 is executed

3

left of node allocated in call 2

NULL

R1

null is copied into copy (i.e., left of node allocated in call 2) and call 3 is completed

At this point the third call is finished, and copy looks like this:

Click To expand

We return to finish the second call. We shade the completed calls to show that the execution of that call has finished and that activation record is no longer on the stack.

Call

copy

originalTree

Return

Comment

1

external pointer to new tree

L

RO

copy is given a node to point to; L is copied into the info member; R1 is executed

2

left of node allocated in call 1

D

R1

copy is given a node to point to; D is copied into the info member; R1 is executed

3

left of node allocated in call 2

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 2) and call 3 is completed

4

right of node allocated in call 2

K

R2

copy is given a node to point to; K is copied into the info member; R1 is executed

5

left of node allocated in call 4

NULL

R1

NULL is copied into copy (i.e., left of node in call 4) and call 5 is completed

After the completion of the fifth call, control returns to the fourth call. Because the fifth call came from R1, R2 must be executed.

Call

copy

originalTree

Return

Comment

1

external pointer to new tree

L

RO

copy is given a node to point to; L is copied into the info member; R1 is executed

2

left of node allocated in call 1

D

R1

copy is given a node to point to; D is copied into the info member; R1 is executed

3

left of node allocated in call 2

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 2) and call 3 is completed

4

right of node allocated in call 2

K

R2

copy is given a node to point to; K is copied into the info member; R1 is executed

5

left of node allocated in call 4

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 4) and call 5 is completed

6

right of node allocated in call 4

NULL

R2

NULL is copied into copy (i.e., right of node allocated in call 4) and call 6 is completed

Because the sixth call came from R2, the fourth call is now finished, and copy looks like this:

Click To expand

But as the fourth call came from R2, call 4 is also finished, leaving only the activation record from the original call on the stack. Execution continues with the second recursive call from call 1.

Call

Copy

originalTree

Return

Comment

1

external pointer to new tree

L

R0

copy is given a node to point to; L is copied into the info member; R1 is executed

2

left of node allocated in call 1

D

R1

copy is given a node to point to; D is copied into the info member; R1 is executed

3

left of node allocated in call 2

NULL

R1

NULL Is copied into copy (i.e., left of node allo cated in call 2) and call 3 is completed

4

right of node allocated in call 2

K

R2

copy is given a node to point to; K is copied into the info member; R1 is executed

5

left of node allocated in call 4

NULL

R1

NULL is copied into copy (i.e., left of node allo cated in call 4) and call 5 is completed

6

right of node allocated in call 4

NULL

R2

NULL is copied into copy (i.e., right of node allo cated in call 4) and call 6 is completed

7

right of node allocated in call 1

M

R2

copy is given a node to point to; M is copied into the info member; R1 is executed

8

left of node allocated in call 7

NULL

R1

NULL is copied into copy (i.e., left of node allo cated in call 7) and call 8 is completed

All we have left to do is the second recursive call from call 7.

Call

copy

originalTree

Return

Comment

1

external pointer to new tree

L

RO

copy is given a node to point to; L is copied into the info member; R1 is executed

2

left of node allocated in call 1

D

R1

copy is given a node to point to; D is copied into the info member; R1 is executed

3

left of node allocated in call 2

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 2) and call 3 is completed

4

right of node allocated in call 2

K

R2

copy is given a node to point to; K is copied into the info member; R1 is executed

5

left of node allocated in call 4

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 4) and call 5 is completed

6

right of node allocated in call 4

NULL

R2

NULL is copied into copy (i.e., right of node allocated in call 4) and call 6 is completed

7

right of node allocated in call 1

M

R2

copy is given a node to point to; M is copied into the info member; R1 is executed

8

left of node allocated in call 7

NULL

R1

NULL is copied into copy (i.e., left of node allocated in call 7) and call 8 is completed

9

right of node allocated in call 7

NULL

R2

NULL is copied into copy (i.e., right of node allocated in call 7) and call 9 is completed

Call 9's completion finishes up call 7, which then finishes up call 1. Because call 1 is the nonrecursive call, the process is finished. At last, copy is a duplicate of originalTree.

More about Traversals

In the Print function, we conducted an inorder traversal of a binary search tree: The value in a node was printed in between the printing of the values in its left subtree and the values in its right subtree. An inorder traversal prints the values in a binary search tree in ascending key order. When implementing the destructor for the binary search tree, we introduced a post-order traversal: A node was deleted after destroying its left subtree and its right subtree. One more important traversal exists: the preorder traversal. In a pre-order traversal, the values in a node are visited before the values in its left subtree and the values in its right subtree.

Inorder traversal A systematic way of visiting all nodes in a binary tree that visits the nodes in the left subtree of a node, then visits the node, and then visits the nodes in the right subtree of the node

Postorder traversal A systematic way of visiting all nodes in a binary tree that visits the nodes in the left subtree of a node, then visits the nodes in the right subtree of the node, and then visits the node

Preorder traversal A systematic way of visiting all nodes in a binary tree that visits a node, then visits the nodes in the left subtree of the node, and then visits the nodes in the right subtree of the node

Compare the algorithms for these three traversals to be sure you understand the difference among them.

When we say "visit," we mean that the algorithm does whatever it needs to do with the values in the node-print them, sum certain data members, or delete them, for example. Notice that the name given to each traversal specifies where the node itself is processed in relation to its subtrees.

If you are having trouble visualizing these traversals, try the following exercise. Visualize each traversal order by drawing a "loop" around a binary tree as in Figure 8.16. Before drawing the loop, extend the nodes of the tree that have fewer than two children with short lines so that every node has two "edges." Then draw the loop from the root of the tree, down the left subtree, and back up again, hugging the shape of the tree as you go. Each node of the tree is "touched" three times by the loop (the touches are numbered in the figure): once on the way down before the left subtree is reached, once after finishing the left subtree but before starting the right subtree, and once on the way up, after finishing the right subtree.

Click To expand
Figure 8.16: Visualizing binary tree traversals

To generate a preorder traversal, follow the loop and visit each node the first time it is touched (before visiting the left subtree). To generate an inorder traversal, follow the loop and visit each node the second time it is touched (in between visiting the two subtrees). To generate a postorder traversal, follow the loop and visit each node the third time it is touched (after visiting the right subtree). Use this method on the tree in Figure 8.17 and see if you agree with the listed traversal orders.

Click To expand
Figure 8.17: Three tree traversals

An inorder traversal allows us to print the values in ascending order; a postorder traversal allows us to destroy a tree more efficiently. Where is a preorder traversal useful? This traversal is not particularly useful when dealing with binary search trees; however, in other applications of binary trees it is very useful.

The Functions ResetTree and GetNextItem

ResetTree gets the "current position" ready for a traversal; GetNextItem moves the current position to the next node and returns the value stored there. We have looked at three kinds of traversals, so what does "next node" mean here? Both ResetTree and GetNextItem have a parameter of type OrderType that allows the user to specify which traversal to use.

When traversing a linear structure, moving from one item to the next one is specified explicitly. Our tree traversals are recursive, so the location of the next item is a function of the current item and the run-time stack. We could use an auxiliary stack to implement the traversal, thereby saving the history that we need to find the next item. However, an even simpler way exists: We let ResetTree generate a queue of node contents in the proper order and let GetNextItem process the node contents from the queue. Recall that OrderType is specified as follows:

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER} ;

We let ResetTree call one of three recursive functions depending on the value of the parameter order. Each function implements a recursive traversal storing the node contents onto a queue. Thus we must have three queues declared in the private section of TreeType.

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER);

class TreeType
{
public:
  // Function prototypes go here.
private:
  TreeNode* root ;
  QueType preQue;
  QueType inQue;
  QueType postQue;
}
// Function prototypes for auxiliary functions.

void PreOrder(TreeNode*, QueType&);
// Enqueues tree items in preorder.

void InOrder(TreeNode*, QueType&);
// Enqueues tree items in inorder.

void PostOrder(TreeNode*, QueType&);
// Enqueues tree items in postorder.

void TreeType::ResetTree(OrderType order)
// Calls a function to create a queue of the tree elements in
// the desired order.
{
  switch (order)
  {
    case PRE_ORDER : PreOrder(root, preQue);
                     break;
    case IN_ORDER  : InOrder(root, inQue);
                     break;
    case POST_ORDER: PostOrder(root, postQue);
                     break;
  }
}

void PreOrder(TreeNode* tree,
     QueType& preQue)
// Post: preQue contains the tree items in preorder.
{
  if (tree != NULL)
  {
    preQue.Enqueue(tree->info);
    PreOrder(tree->left, preQue);
    PreOrder(tree->right, preQue);
  }
}

void InOrder(TreeNode* tree,
     QueType& inQue)
// Post: inQue contains the tree items in inorder.
{
  if (tree != NULL)
  {
    InOrder(tree->left, inQue);
    inQue.Enqueue(tree->info);
    InOrder(tree->right, inQue):
  }
}

void PostOrder(TreeNode* tree,
     QueType& postQue)
// Post: postQue contains the tree items in postorder.
{
  if (tree != NULL)
  {
    PostOrder(tree->left, postQue);
    PostOrder(tree->right, postQue);
    postQue.Enqueue(tree->info);
  )
}

void TreeType::GetNextItem(ItemType& item,
     OrderType order, bool& finished)
// Returns the next item in the desired order.
// Post: For the desired order, item is the next item in the queue.
//       If item is the last one in the queue, finished is true;
//       otherwise, finished is false.
{
  finished = false;
  switch (order)
  {
    case PRE_ORDER  : preQue.Dequeue(item);
                      if (preQue.IsEmpty())
                        finished = true;
                      break;
    case IN_ORDER   : inQue.Dequeue(item);
                      if (inQue.IsEmpty())
                       finished = true;
                     break:
    case POST_ORDER: postQue.Dequeue(item);
                     if (postQue.IsEmpty())
                       finished = true;
                     break;
  }
}


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)