tree.cpp

《Visual C++ Bible》或者说是《Visual C++ 宝典》的对应的源码文件

///////////////////////////////////////////////////////////////////////
//
// Tree.cpp - use the tree structure for sorting and searching.
//
// Description:
//		This file contains the base functions for the Tree class.
//		These will be elaborated on by any subclass.
//
///////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Tree.h"

//
// Default constructor function for Node class - just NULLs out
// the pointer members.
//
Node::Node()
{
	left = right = NULL;
}

//
// Default constructor function for Tree class - just NULLs out
// the pointer member.
//
Tree::Tree()
{
	root = NULL;
}

//
// The insert function must be called on a Tree.  If the root node
// is empty, then the data is placed there.  If the data is already
// in the Tree, then delete the new copy and return the old one.
// Otherwise, insert the data wherever it fits.
//
Node *Tree::insert(Node *np)
{
	//
	// If the root is empty, put the data there.
	//
	if (root == NULL) {
		root = np;
		return(np);
	}

	Node *nPtr = root;

	//
	// Do an iterative descent down the tree, to find whether the
	// data is already there; and, if not, where on the edge of
	// the tree it can be inserted.
	//
	for (;;) {
		//
		// If the new data is identical to an existing node, then
		// just return that node.
		//
		if (nPtr == np)
			break;

		//
		// If the new data is equal to but not identical with an
		// existing node, then delete the new node and return the
		// old one.
		//
		if (nPtr->is_equal(np)) {
			delete(np);
			np = nPtr;
			break;
		}

		//
		// Walk down the tree.  If the current value is greater	than
		// the new value (per the subclass's definition of greater),
		// then look to the left; otherwise, look to the right.  Put
		// the new node in at the first empty space.
		//
		if (nPtr->is_greater(np)) {
			if (nPtr->left == NULL) {
				nPtr->left = np;
				break;
			}
			nPtr = nPtr->left;
		} else {
			if (nPtr->right == NULL) {
				nPtr->right = np;
				break;
			}
			nPtr = nPtr->right;
		}
	}

	// Return the node that is in place.
	return(np);
}

//
// The search function must be called on a Tree.  This function does
// the same iterative descent as the insertion, but returns NULL if
// it doesn't find a match with the Node passed in.
//
Node *Tree::search(Node *np)
{
	Node *nPtr	= root;

	for (;;) {
		if (nPtr == NULL)
			return(NULL);

		if (nPtr->is_equal(np))
			return(nPtr);

		if (nPtr->is_greater(np))
			nPtr = nPtr->left;
		  else
		  	nPtr = nPtr->right;
	}
}

//
// To list a Tree, list its root Node, starting at depth 0.
//
void Tree::list()
{
	if (root == NULL)
		cout << "(Null)" << endl;
	  else
	  	root->list(0);
}

//
// To list a node, list its left child (if it exists) at a depth 1
// greater than itself; then print the value of the node at its
// current depth; then list its right child (if it exists) at a
// depth 1 greater than itself.
//
void Node::list(int depth)
{
	register int i;

	// List the left child, 1 deeper.
	if (left != NULL)
		left->list(depth + 1);

	// Express the depth.
	for (i = 0; i < depth; ++i)
		cout << "    ";

	// Print the value.
	print();

	// List the right child, 1 deeper.
	if (right != NULL)
		right->list(depth + 1);
}