d_stree.h

非常有用的数据结构库

	// set the tree size
	treeSize = rhs.treeSize;

	// return reference to current object
	return *this;
}

template <typename T>
int stree<T>::empty() const
{
	return root == NULL;
}

template <typename T>
int stree<T>::size() const
{
	return treeSize;
}

template <typename T>
void stree<T>::erase(iterator pos)
{
	// dNodePtr = pointer to node D that is deleted
	// pNodePtr = pointer to parent P of node D
	// rNodePtr = pointer to node R that replaces D
	stnode<T> *dNodePtr = pos.nodePtr, *pNodePtr, *rNodePtr;

	if (treeSize == 0)
 		throw
			underflowError("stree erase(): tree is empty");

	if (dNodePtr == NULL)
 		throw
			referenceError("stree erase(): invalid iterator");

	// assign pNodePtr the address of P
	pNodePtr = dNodePtr->parent;

	// If D has a NULL pointer, the
	// replacement node is the other child
	if (dNodePtr->left == NULL || dNodePtr->right == NULL)
	{
		if (dNodePtr->right == NULL)
			rNodePtr = dNodePtr->left;
		else
			rNodePtr = dNodePtr->right;

		if (rNodePtr != NULL)
			// the parent of R is now the parent of D
			rNodePtr->parent = pNodePtr;
	}
	// both pointers of dNodePtr are non-NULL.
	else
	{
		// find and unlink replacement node for D.
		// starting at the right child of node D,
		// find the node whose value is the smallest of all
		// nodes whose values are greater than the value in D.
		// unlink the node from the tree.
  
		// pOfRNodePtr = pointer to parent of replacement node
		stnode<T> *pOfRNodePtr = dNodePtr;

		// first possible replacement is right child of D
		rNodePtr = dNodePtr->right;

		// descend down left subtree of the right child of D,
		// keeping a record of current node and its parent.
		// when we stop, we have found the replacement
		while(rNodePtr->left != NULL)
		{
			pOfRNodePtr = rNodePtr;
			rNodePtr = rNodePtr->left;
		}
  
		if (pOfRNodePtr == dNodePtr)
		{
			// right child of deleted node is the replacement.
			// assign left subtree of D to left subtree of R
			rNodePtr->left = dNodePtr->left;
			// assign the parent of D as the parent of R
			rNodePtr->parent = pNodePtr;
			// assign the left child of D to have parent R
			dNodePtr->left->parent = rNodePtr;
		}
		else
		{
			// we moved at least one node down a left branch
			// of the right child of D. unlink R from tree by
			// assigning its right subtree as the left child of
			// the parent of R
			pOfRNodePtr->left = rNodePtr->right;

			// the parent of the right child of R is the
			// parent of R
			if (rNodePtr->right != NULL)
				rNodePtr->right->parent = pOfRNodePtr;

			// put replacement node in place of dNodePtr
			// assign children of R to be those of D
			rNodePtr->left = dNodePtr->left;
			rNodePtr->right = dNodePtr->right;
			// assign the parent of R to be the parent of D
			rNodePtr->parent = pNodePtr;
			// assign the parent pointer in the children
			// of R to point at R
			rNodePtr->left->parent = rNodePtr;
			rNodePtr->right->parent = rNodePtr;
		}
	}

	// complete the link to the parent node.

	// deleting the root node. assign new root
	if (pNodePtr == NULL)
		root = rNodePtr;
	// attach R to the correct branch of P
	else if (dNodePtr->nodeValue < pNodePtr->nodeValue)
		pNodePtr->left = rNodePtr;
	else
		pNodePtr->right = rNodePtr;
  
	// delete the node from memory and decrement tree size
	delete dNodePtr;
	treeSize--;
}

template <typename T>
int stree<T>::erase(const T& item)
{
	int numberErased = 1;
	// search tree for item
	stnode<T> *p  = findNode(item);

	// if item found, delete the node
	if (p != NULL)
		erase(iterator(p,this));
	else
		numberErased = 0;

	return numberErased;
}

template <typename T>
void stree<T>::erase(iterator first, iterator last)
{
	if (treeSize == 0)
 		throw
			underflowError("stree erase(): tree is empty");

	iterator p = first;

	if (first == begin() && last == end())
	{
		// we are asked to erase the entire tree.
		// erase the tree nodes from memory
		deleteTree(root);

		// tree is emtpy
		root = NULL;
		treeSize = 0;
	}
	else
		// erase each item in a subrange of the tree
		while (p != last)
			erase(p++);
}


// recursive inorder scan used to build the shadow tree
template <typename T>
stnodeShadow *stree<T>::buildShadowTree(stnode<T> *t, int level, int& column)
{
	// pointer to new shadow tree node
	stnodeShadow *newNode = NULL;
	// text and ostr used to perform format conversion
	char text[80];
	ostrstream ostr(text,80);

	if (t != NULL)
	{
		// create the new shadow tree node
		newNode = new stnodeShadow;

		// allocate node for left child at next level in tree; attach node
		stnodeShadow *newLeft = buildShadowTree(t->left, level+1, column);
		newNode->left = newLeft;

		// initialize data members of the new node
		ostr << t->nodeValue << ends;	// format conversion
		newNode->nodeValueStr = text;
		newNode->level = level;
		newNode->column = column;

		// update column to next cell in the table
		column++;

		// allocate node for right child at next level in tree; attach node
		stnodeShadow *newRight = buildShadowTree(t->right, level+1, column);
		newNode->right = newRight;
	}

	return newNode;
}

template <typename T>
void stree<T>::displayTree(int maxCharacters)
{
	string label;
	int level = 0, column = 0;
	int colWidth = maxCharacters + 1;
	// 
	int currLevel = 0, currCol = 0;

	if (treeSize == 0)
		return;

	// build the shadow tree
	stnodeShadow *shadowRoot = buildShadowTree(root, level, column);

	// use during the level order scan of the shadow tree
	stnodeShadow *currNode;

   // store siblings of each stnodeShadow object in a queue so that
	// they are visited in order at the next level of the tree
   queue<stnodeShadow *> q;

   // insert the root in the queue and set current level to 0
   q.push(shadowRoot);
   
   // continue the iterative process until the queue is empty
   while(!q.empty())
   {
      // delete front node from queue and make it the current node
      currNode = q.front();
		q.pop();

		// if level changes, output a newline
		if (currNode->level > currLevel)
		{
			currLevel = currNode->level;
			currCol = 0;
			cout << endl;
		}

		// if a left child exists, insert the child in the queue
      if(currNode->left != NULL)
			q.push(currNode->left);

		// if a right child exists, insert the child in the queue
      if(currNode->right != NULL)
			q.push(currNode->right);

		// output formatted node label
		if (currNode->column > currCol)
		{
			cout << setw((currNode->column-currCol)*colWidth) << " ";
			currCol = currNode->column;
		}
		cout << setw(colWidth) << currNode->nodeValueStr;
		currCol++;
   }
	cout << endl;

	// delete the shadow tree
	deleteShadowTree(shadowRoot);
}

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

template <typename T>
void stree<T>::drawTree(int maxCharacters)
{
	drawTreeFrame(maxCharacters, true);
}

template <typename T>
void stree<T>::drawTrees(int maxCharacters)
{
	drawTreeFrame(maxCharacters, false);
}


template <typename T>
void stree<T>::drawTreeFrame(int maxCharacters, bool simpleDraw)
{
	// approximate width of a character drawn by textShape
	const double UNITS_PER_CHAR = .15;

	// estimated width of a formatted node value.
	// add .2 to allow space outside the label
	double cellSide = maxCharacters*UNITS_PER_CHAR + 0.2;

	string label;

	int level = 0, column = 0;

	// build the shadow tree
	stnodeShadow *shadowRoot = buildShadowTree(root, level, column);

	// use during the level order scan of the shadow tree
	stnodeShadow *currNode;

	// node draws the circle shape that represents a node.
	// the radius is (cellSide + .20)/2.0
	circleShape node(0,0,cellSide/2.0, lightblue);

	// text draws the formatted value in a node
	textShape text(0,0,"",darkgray);

	// edge draws edges in the tree
	lineShape edge(0,0,0,0,black);

	// x, y coordinates of a circle center on the screen
	double x, childx, y, childy;

	// open the drawing window if not yet opened
	if (stree::graphWinOpen == false)
	{
		openWindow();
		stree::graphWinOpen = true;
	}

   // store siblings of each stnodeShadow object in a queue so that
	// they are visited in order at the next level of the tree
   queue<stnodeShadow *> q;

   // insert the root in the queue
   q.push(shadowRoot);

   // continue the iterative process until the queue is empty
   while(!q.empty())
   {
		// delete front node from queue and make it the current node
		currNode = q.front();
		q.pop();

		// assign formatted node label to string label
		label = currNode->nodeValueStr;

		// convert each (level, column) coordinate into screen
		// coordinates for the center of the node. add .1 so
		// we stay away from the edges of the screen
		x = currNode->column * cellSide + cellSide/2.0 + 0.1;
		y = currNode->level * cellSide + cellSide/2.0 + 0.1;

		// if a left child exists, draw an edge from the current
		// node center to the child node center. insert the child
		// in the queue
		if(currNode->left != NULL)
		{
			edge.move(x, y);
			// compute the center of the left child node
			childx = currNode->left->column * cellSide + cellSide/2.0 + 0.1;
			childy = currNode->left->level * cellSide + cellSide/2.0 + 0.1;
			edge.setEndPoint(childx, childy);
			edge.draw();
			q.push(currNode->left);
		}

		// if a right child exists, draw an edge from the current
		// node center to the child node center. insert the child
		// in the queue
      if(currNode->right != NULL)
		{
			edge.move(x, y);
			// compute the center of the right child node
			childx = currNode->right->column * cellSide + cellSide/2.0 + 0.1;
			childy = currNode->right->level * cellSide + cellSide/2.0 + 0.1;
			edge.setEndPoint(childx, childy);
			edge.draw();
			q.push(currNode->right);
		}

		// draw the current node
		node.move(x,y);
		node.draw();
		// draw the node data. use an appropriate offset from the node
		// center so the text is approximately aligned in the node
		text.move(x - label.length() * UNITS_PER_CHAR /2.0,
					 y - UNITS_PER_CHAR);
		text.setText(label);
		text.draw();
   }

	// pause to view the tree
	viewWindow();

	// erase or close the window
	if (simpleDraw)
	{
		closeWindow();
		stree::graphWinOpen = false;
	}
	else
		eraseWindow();
}


#endif  // BINARY_SEARCH_TREE_CLASS