binarytree.cpp

用C++写的寻找公共祖先

//:BinaryTree.cpp
//******************************************************
//Desinged by: Xinyun Yu	Date: 2006.4.16
//Implementation file for ADT BinaryTree in BinaryTree.h
//******************************************************
#include "BinaryTree.h"
#include "LinkedQueue.h"
#include "LinkedStack.h"
#include <iostream>
using namespace std;

BinaryTree::BinaryTree()
{
	root = 0;
} //end default constructor

BinaryTree::~BinaryTree()
{
	destroyTree(root);
} //end destructor

void BinaryTree::destroyTree(TreeNode* &node)
{
	if(!node)
	{
		//to destroy every node using recursion
		destroyTree(node->leftChild);
		destroyTree(node->rightChild);
		delete node;
		node = 0;
	}
}

void BinaryTree::createTree(istream& in)
{
	createTree(root, in);
} //end createTree in public

istream& operator>>(istream& in, BinaryTree& T)
{
	T.createTree(in);

	return in;
} //end operator>>

void BinaryTree::createTree(TreeNode* &node, istream& in)
{
	if(node != 0)
		throw TreeException("Can't overwrite existed tree!");

	char data;

	if(in >> data)
	{
		if(data != '#')
		{
			node = new TreeNode;
			node->item = data;
			node->leftChild = 0;
			node->rightChild = 0;
			createTree(node->leftChild, in);
			createTree(node->rightChild, in);
		}
	}
} //end creatTree in protected

void BinaryTree::preorderTraverse(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	preorder(root, visit);
} //end preorderTraverse

void BinaryTree::inorderTraverse(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	inorder(root, visit);
} //end inorderTraverse

void BinaryTree::postorderTraverse(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	postorder(root, visit);
} //end postorderTraverse

void BinaryTree::preorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode* node))
{
	if(node != 0)
	{
		(this->*visit)(node);
		preorder(node->leftChild, visit);
		preorder(node->rightChild, visit);
	}
} //end preorder

void BinaryTree::inorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode*))
{
	if(node != 0)
	{
		inorder(node->leftChild, visit);
		(this->*visit)(node);
		inorder(node->rightChild, visit);
	}
} //end inorder

void BinaryTree::postorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode*))
{
	if(node != 0)
	{
		postorder(node->leftChild, visit);
		postorder(node->rightChild, visit);
		(this->*visit)(node);
	}
} //end postorder

void BinaryTree::levelTraverse(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	LinkedQueue<TreeNode*> Q;
	Q.add(root);
	TreeNode* node;

	while(!Q.isEmpty())
	{
		Q.Delete(node);
		(this->*visit)(node);
			
		if(node->leftChild != 0)
			Q.add(node->leftChild);
		
		if(node->rightChild != 0)
			Q.add(node->rightChild);
	}
} //end levelTraverse

void BinaryTree::printNode(TreeNode* node)
{
	if(!node)
		throw TreeException("Empty node!");

	cout << node->item;
} //end printNode

void BinaryTree::prePrintTree()
{
	try{
		cout << "Using recursion:";
		preorderTraverse(printNode);
		cout << "\nNot using recursion:";
		preorderTraverse2(printNode);
	} catch(TreeException& E){
		cout << E.what() << endl;
	}
} //end prePrintTree

void BinaryTree::inPrintTree()
{
	try{
		cout << "Using recursion:";
		inorderTraverse(printNode);
		cout << "\nNot using recursion:";
		inorderTraverse2(printNode);
	} catch(TreeException& E){
		cout << E.what() << endl;
	}
} //end inPrintTree

void BinaryTree::postPrintTree()
{
	try{
		cout << "Using recursion:";
		postorderTraverse(printNode);
		cout << "\nNot using recursion:";
		postorderTraverse2(printNode);
	} catch(TreeException& E){
		cout << E.what() << endl;
	}
} //end postPrintTree

void BinaryTree::levelPrintTree()
{
	try{
		levelTraverse(printNode);
	} catch(TreeException& E){
		cout << E.what() << endl;
	}
} //end levelPrintTree

void BinaryTree::preorderTraverse2(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	LinkedStack<TreeNode*> S;//Push treeNode to S
	TreeNode* node = root;

	while(node != 0)
	{
		(this->*visit)(node); //visit the parent first

		if(node->rightChild != 0)
			S.add(node->rightChild);
		
		if(node->leftChild != 0)
			node = node->leftChild;
		else if(S.isEmpty()) //Already visit every node
			node = 0;
		else
			S.Delete(node);
	}
} //end preorderTraverse2

void BinaryTree::inorderTraverse2(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	LinkedStack<TreeNode*> S;//Push treeNode to S
	TreeNode* node = root;

	while(node != 0)
	{				
		if(node->leftChild != 0)
		{
			S.add(node); //Push the parent into the stack if its leftChild exists
			node = node->leftChild; //go its leftChild to continue
		}
		else
		{
			(this->*visit)(node); //If it has no leftChild,  visit it
		
			while(node->rightChild == 0) //If it has no rightChild, pop its parent node out
			{
				if(S.isEmpty()) //Already visit every node
					break;
				else
					S.Delete(node); //node to be its parent node

				(this->*visit)(node); //visit node
			}
			
			node = node->rightChild;
		}
	}
} //end inorderTraverse2

void BinaryTree::postorderTraverse2(void (BinaryTree::*visit)(TreeNode*))
{
	if(!root)
		throw TreeException("Empty tree!");

	LinkedStack<TreeNode*> S;//Push treeNode to S
	LinkedStack<bool> popRight;//Determined the node in S is a rightChild,
							//which means its leftChild hasn't been visited
	TreeNode* node = root;

	while(node != 0)
	{
		S.add(node);
		popRight.add(false);

		if(node->rightChild != 0)
		{
			S.add(node->rightChild);
			popRight.add(true);
		}

		if(node->leftChild != 0)
			node = node->leftChild;
		else
		{
			while(!S.isEmpty())
			{
				bool temp;
				popRight.Delete(temp);
				S.Delete(node);

				if(temp)//Pop out a rightChild, so its leftChild not been visited
					break;
				else
					(this->*visit)(node);
			}
		}

		if(S.isEmpty())
			break;
	}
} //end postorderTraverse2

bool BinaryTree::findAncester(TreeNode* node, char m, char n, char& ancester)
{
	if(findM && findN) //If find both, not necessary to go on, save the run time
		return true;

	if(node == 0)
		return false;

	if(node->item == m) //Find m
	{
		if(findM)
			throw TreeException("Collision: the tree has same characters!");

		findM = true;

		if(findN) //Find both, so return
			return true;
	}
	else if(node->item == n) //Find n
	{
		if(findN)
			throw TreeException("Collision: the tree has same characters!");

		findN = true;

		if(findM)//Find both, so return
			return true;
	}

	findAncester(node->leftChild, m, n, ancester);//To find its leftChild tree

	if((findM || findN) && !setAn)//Find one and not set the ancester, so assume the node is the ancester
	{
		ancester = node->item;
		setAn = true;
	}

	findAncester(node->rightChild, m, n, ancester);//To find its rightChild tree

	if(findM && findN)//Find both, so the assume is right
		return true;
	else//The assume is wrong, so reset setAn
	{
		setAn = false;
		return false;
	}
} //end findAncester in protected, having 4 parameters

bool BinaryTree::findAncester(char m, char n, char& ancester)
{
	if(m == n)
		throw TreeException("Same characters!");

	if(!root)
		throw TreeException("Empty tree!");

	//Initialize
	findM = false;
	findN = false;
	setAn = false;

	return findAncester(root, m, n, ancester);
} //end findAncester in public