Second Edition

by Michael Main and Walter Savitch

ISBN 0-201-70297-5, Softcover, 816 pages

Section 10.3 of the Second Edition includes a class for binary tree nodes. Among other things, there are two member functions to get copies of the left and right pointers of a node. From page 465, we have these functions:

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

Michael Main (main@colorado.edu)