d_stree.h

非常有用的数据结构库

#ifndef BINARY_SEARCH_TREE_CLASS
#define BINARY_SEARCH_TREE_CLASS

#ifndef NULL
#include <cstddef>
#endif  // NULL

#include <iomanip>		// for setw()
#include <strstream>		// for format conversion
#include <string>			// node data formatted as a string
#include <queue>
#include <utility>		// pair class

#include "d_except.h"	// exception classes
#include "d_circsh.h"	// for drawing a node
#include "d_linesh.h"	// for drawing an edge
#include "d_textsh.h"	// for drawing the node value

using namespace std;

// declares a binary search tree node object
template <typename T>
class stnode
{
   public:
		// stnode is used to implement the binary search tree class
		// making the data public simplifies building the class functions

		T nodeValue;
			// node data
		stnode<T> *left, *right, *parent;
		// child pointers and pointer to the node's parent

      // constructor
		stnode (const T& item, stnode<T> *lptr = NULL, 
              stnode<T> *rptr = NULL, stnode<T> *pptr = NULL):
				nodeValue(item), left(lptr), right(rptr), parent(pptr)
		{}
};

// objects hold a formatted label string and the level,column
// coordinates for a shadow tree node
class stnodeShadow
{
	public:
		string nodeValueStr;	// formatted node value
		int level,column;
		stnodeShadow *left, *right;

		stnodeShadow ()
		{}
};

template <typename T>
class stree
{
	public:

// include the iterator nested classes
#include "d_stiter.h"

		static bool graphWinOpen;
		stree();
			// constructor. initialize root to NULL and size to 0
		stree(T *first, T *last);
			// constructor. insert the elements from the pointer
			// range [first, last) into the tree
		stree(const stree<T>& tree);
			// copy constructor
		~stree();
			// destructor
		stree<T>& operator= (const stree<T>& rhs);
			// assignment operator

		// search for item. if found, return an iterator pointing
		// at it in the tree; otherwise, return end()
		iterator find(const T& item)
		{
			stnode<T> *curr;

			// search tree for item
			curr = findNode (item);

			// if item found, return const_iterator with value current;
			// otherwise, return end()
			if (curr != NULL)
				return iterator(curr, this);
			else
				return end();
		}

		// constant version
		const_iterator find(const T& item) const
		{
			stnode<T> *curr;

			// search tree for item
			curr = findNode (item);

			// if item found, return const_iterator with value current;
			// otherwise, return end()
			if (curr != NULL)
				return const_iterator(curr, this);
			else
				return end();
		}

		int empty() const;
			// indicate whether the tree is empty
		int size() const;
			// return the number of data items in the tree

		// if item is not in the tree, insert it and
		// return a pair whose iterator component points
		// at item and whose bool component is true. if item
		// is in the tree, return a pair whose iterator
		// component points at the existing item and whose
		// bool component is false
		// Postcondition: the tree size increases by 1 if item
		// is not in the tree
		pair<iterator, bool> insert(const T& item)
		{
			// t is current node in traversal, parent the previous node
			stnode<T> *t = root, *parent = NULL, *newNode;

			// terminate on on empty subtree
			while(t != NULL)
			{
				// update the parent pointer. then go left or right
				parent = t;
				// if a match occurs, return a pair whose iterator
				// component points at item in the tree and whose
				// bool component is false
				if (item == t->nodeValue)
					return pair<iterator, bool> (iterator(t, this), false);
				else if (item < t->nodeValue)
					t = t->left;
				else 
					t = t->right;
			}
		    
			// create the new leaf node
			newNode = getSTNode(item,NULL,NULL,parent);

			// if parent is NULL, insert as root node
			if (parent == NULL)
				root = newNode;
			else if (item < parent->nodeValue)                   
				// insert as left child        
				parent->left = newNode;  
			else
				// insert as right child     
				parent->right = newNode;
		  
			// increment size
			treeSize++;

			// return an pair whose iterator component points at
			// the new node and whose bool component is true
			return pair<iterator, bool> (iterator(newNode, this), true);
		}

		int erase(const T& item);
			// if item is in the tree, erase it and return 1;
			// otherwise, return 0
			// Postcondition: the tree size decreases by 1 if
			// item is in the tree

		void erase(iterator pos);
			// erase the item pointed to by pos.
			// Preconditions: the tree is not empty and pos points
			// to an item in the tree. if the tree is empty, the
			// function throws the underflowError exception. if the
			// iterator is invalid, the function throws the referenceError
			// exception.
			// Postcondition: the tree size decreases by 1

		void erase(iterator first, iterator last);
			// erase all items in the range [first, last).
			// Precondition: the tree is not empty. if the tree
			// is empty, the function throws the underflowError
			// exception.
			// Postcondition: the size of the tree decreases by
			// the number of elements in the range [first, last)

		// return an iterator pointing to the first item
		// inorder
		iterator begin()
		{
			stnode<T> *curr = root;

			// if the tree is not empty, the first node
			// inorder is the farthest node left from root
			if (curr != NULL)
				while (curr->left != NULL)
					curr = curr->left;

			// build return value using private constructor
			return iterator(curr, this);
		}

		// constant version
		const_iterator begin() const
		{
			const stnode<T> *curr = root;

			// if the tree is not empty, the first node
			// inorder is the farthest node left from root
			if (curr != NULL)
				while (curr->left != NULL)
					curr = curr->left;

			// build return value using private constructor
			return const_iterator(curr, this);
		}

		// return an iterator pointing just past the end of
		// the tree data
		iterator end()
		{
			// end indicated by an iterator with NULL stnode pointer
			return iterator(NULL, this);
		}

		// constant version
		const_iterator end() const
		{
			// end indicated by an iterator with NULL stnode pointer
			return const_iterator(NULL, this);
		}

		void displayTree(int maxCharacters);
			// tree display function. maxCharacters is the
			// largest number of characters required to draw
			// the value of a node

		void drawTree(int maxCharacters);
			// tree draw function. maxCharacters is the
			// largest number of characters required to draw
			// the value of a node

		void drawTrees(int maxCharacters);
			// repeated tree draw function. maxCharacters is the
			// largest number of characters required to draw
			// the value of a node

	private:
		stnode<T> *root;
			// pointer to tree root
		int treeSize;
			// number of elements in the tree

		stnode<T> *getSTNode(const T& item,
									stnode<T> *lptr,stnode<T> *rptr, stnode<T> *pptr);
			// allocate a new tree node and return a pointer to it.
			// if memory allocation fails, the function throws the
			// memoryAllocationError exception

		stnode<T> *copyTree(stnode<T> *t);
			// recursive function used by copy constructor and assignment
			// operator to assign the current tree as a copy of another tree

		void deleteTree(stnode<T> *t);
			// recursive function used by destructor and assignment
			// operator to delete all the nodes in the tree

		stnode<T> *findNode(const T& item) const;
			// search for item in the tree. if it is in the tree,
			// return a pointer to its node; otherwise, return NULL.
			// used by find() and erase()

		stnodeShadow *buildShadowTree(stnode<T> *t, int level, int& column);
			// recursive function that builds a subtree of the shadow tree
			// corresponding to node t of the tree we are drawing. level is the
			// level-coordinate for the root of the subtree, and column is the
			// changing column-coordinate of the tree nodes

		void deleteShadowTree(stnodeShadow *t);
			// remove the shadow tree from memory after displayTree()
			// displays the binary search tree

		void drawTreeFrame(int maxCharacters, bool simpleDraw);			
			// called by drawTree() and drawTrees() to display tree
};

template <typename T>
bool stree<T>::graphWinOpen = false;

template <typename T>
stnode<T> *stree<T>::getSTNode(const T& item,
			stnode<T> *lptr,stnode<T> *rptr, stnode<T> *pptr)
{
	stnode<T> *newNode;

	// initialize the data and all pointers
	newNode = new stnode<T> (item, lptr, rptr, pptr);
	if (newNode == NULL)
		throw memoryAllocationError("stree: memory allocation failure");

	return newNode;
}

template <typename T>
stnode<T> *stree<T>::copyTree(stnode<T> *t)
{
	stnode<T> *newlptr, *newrptr, *newNode;

	// if tree branch NULL, return NULL
	if (t == NULL)
		return NULL;
  
	// copy the left branch of root t and assign its root to newlptr
	newlptr = copyTree(t->left);

	// copy the right branch of tree t and assign its root to newrptr
	newrptr = copyTree(t->right);

	// allocate storage for the current root node, assign
	// its value and pointers to its left and right subtrees.
	// the parent pointer of newNode is assigned when
	// newNode's parent is created. if newNode is root,
	// NULL is the correct value for its parent pointer
	newNode = getSTNode(t->nodeValue, newlptr, newrptr, NULL);

	// the current node is the parent of any subtree that
	// is not empty
	if (newlptr != NULL)
		newlptr->parent = newNode;
	if (newrptr != NULL)
		newrptr->parent = newNode;

	return newNode;
}

// delete the tree stored by the current object
template <typename T>
void stree<T>::deleteTree(stnode<T> *t)
{
	// if current root node is not NULL, delete its left subtree,
	// its right subtree and then the node itself
	if (t != NULL)
	{
		deleteTree(t->left);
		deleteTree(t->right);
		delete t;
	}
}

// search for data item in the tree. if found, return its node
// address; otherwise, return NULL
template <typename T>
stnode<T> *stree<T>::findNode(const T& item) const
{   
	// cycle t through the tree starting with root
	stnode<T> *t = root;

	// terminate on on empty subtree
	while(t != NULL && !(item == t->nodeValue))
		if (item < t->nodeValue)
			t = t->left;
		else 
			t = t->right;

	// return pointer to node; NULL if not found
	return t;
}

template <typename T>
stree<T>::stree(): root(NULL),treeSize(0)
{}

template <typename T>
stree<T>::stree(T *first, T *last): root(NULL),treeSize(0)
{
	T *p = first;

	// insert each item in [first, last) into the tree
	while (p != last)
	{
		insert(*p);
		p++;
	}
}

template <typename T>
stree<T>::stree(const stree<T>& tree): treeSize(tree.treeSize)
{
	// copy tree to the current object
	root = copyTree(tree.root);
}

template <typename T>
stree<T>::~stree()
{
	// erase the tree nodes from memory
	deleteTree(root);

	// tree is emtpy
	root = NULL;
	treeSize = 0;
}

template <typename T>
stree<T>& stree<T>::operator= (const stree<T>& rhs)
{
	// can't copy a tree to itself
	if (this == &rhs)
		return *this;

	// erase the existing tree nodes from memory
	deleteTree(root);

	// copy tree rhs into current object
	root = copyTree(rhs.root);