...
binary_tree_node* left( ) { return left_field; }
binary_tree_node* right( ) { return right_field; }
We recommend a slight change to these functions, so that the return type is
a reference to the left and right pointers, indicated by the ampersand
in the return type shown here:
...
binary_tree_node*& left( ) { return left_field; }
binary_tree_node*& right( ) { return right_field; }
This modified version of the binary tree node is available to download
from
www.cs.colorado.edu/~main/chapter10/bintree.h and it will also
appear in the second printing of the textbook.
Using a reference in the return type has some simple advantages
that we can illustrate by considering a call to p->left()
(for some pointer p). When the return value is
a reference, then we can use
p->left() to directly reference the left link in
a node. For example, we can write:
p->left() = NULL;
This is a small advantage only, but a larger advantage also occurs because
we can also use p->left() in any location that expects a variable
that is a pointer to a binary tree node.
In particular, recursive functions are often written to manipulate a binary
tree, and one of the parameters to such a function is sometimes
a reference parameter that points to one of the nodes. For example, from
Section 10.5:
template <class Item>
bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
// Precondition: root_ptr is a root pointer of a binary search tree
// or may be NULL for an empty tree).
// Postcondition: If target was in the tree, then one copy of target
// has been removed, and root_ptr now points to the root of the new
// (smaller) binary search tree. In this case the function returns true.
// If target was not in the tree, then the tree is unchanged (and the
// function returns false).
{
binary_tree_node<Item> *oldroot_ptr;
if (root_ptr == NULL)
{ // Empty tree
return false;
}
if (target < root_ptr->data( ))
{ // Continue looking in the left subtree
// Note: Any change made to root_ptr->left by this recursive
// call will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
return bst_remove(root_ptr->left( ), target);
}
if (target > root_ptr->data( ))
{ // Continue looking in the right subtree
// Note: Any change made to root_ptr->right by this recursive
// call will change the actual right pointer (because the return
// value from the right() member function is a reference to the
// actual right pointer.
return bst_remove(root_ptr->right( ), target);
}
if (root_ptr->left( ) == NULL)
{ // Target was found and there is no left subtree, so we can
// remove this node, making the right child be the new root.
oldroot_ptr = root_ptr;
root_ptr = root_ptr->right( );
delete oldroot_ptr;
return true;
}
// If code reaches this point, then we must remove the target from
// the current node. We'll actually replace this target with the
// maximum item in our left subtree.
// Note: Any change made to root_ptr->left by bst_remove_max
// will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
bst_remove_max(root_ptr->left( ), root_ptr->data( ));
return true;
}
In this function, any changes to the root_ptr (such as moving it down to its right child) will affect the actual argument (since it is a reference parameter).
Feel free to send me email if you'd like to discuss this more.