// BinaryTree.h: 樹的類定義
//文件名稱： BinaryTree.h
//項目名稱：shortest_way_main.dsw
//創(chuàng)建者：黃冀渝
//創(chuàng)建時間：Sept.30 2004
//最后修改時間：Oct.6 2004
//功能： 打印給定兩個結(jié)點的最短路徑
 
//與其他文件的依賴關(guān)系：頭文件
#include "BinaryTreeNode.h"
#include <stack>
#include <queue>

//類名稱：BinaryTree 
//定義該類的目的：樹定義
//類屬性：基類
//類中函數(shù)及功能：詳見注釋
//與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對象中的什么函數(shù)）：是BinaryTreeNode類的友元
template <class T>
class BinaryTree  
{
protected:
	BinaryTreeNode<T>*  root;      							//二叉樹根結(jié)點指針
public:
	BinaryTree(){root=NULL;};								//構(gòu)造函數(shù)
	virtual ~BinaryTree(){DeleteBinaryTree(root);};			//析構(gòu)函數(shù)
	bool isEmpty() const							
	{return ((root == NULL)?true:false);};							//判定二叉樹是否為空樹
	BinaryTreeNode<T>* getRoot(){return root;};
	void Initialize(BinaryTreeNode<T>* pointer){root=pointer;};
	//刪除二叉樹或其子樹
	void DeleteBinaryTree(BinaryTreeNode<T>* root);		
	//從二叉樹的root結(jié)點開始，查找current結(jié)點的父結(jié)點
	BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current);
	//前序遍歷打印二叉樹
	void PreOrderPrint(BinaryTreeNode<T>* root);
	//指定內(nèi)容，前序遍歷得到指針
	BinaryTreeNode<T>* PreOrderGetPointer(BinaryTreeNode<T>* root, T element); 
 
	//按照中序輸入內(nèi)容產(chǎn)生對應(yīng)的樹
	BinaryTreeNode<T>* GenerateTree(T* num);
	//一個打印從祖先到子孫(自下而上)的函數(shù)，利用遞歸實現(xiàn)
	int Print_upTodown(BinaryTreeNode<T>* p,BinaryTreeNode<T>* node);
	//打印兩個結(jié)點的最短路徑
	void PrintPath( BinaryTreeNode<T>* ancestor,BinaryTreeNode<T>* Node1,BinaryTreeNode<T>* Node2);
	//前序遞歸查找結(jié)點
	bool PreOrder_Search(BinaryTreeNode<T>* root, T element);
	//尋找兩個結(jié)點的最近的公共祖先并將找到的祖先返回
	BinaryTreeNode<T>* FindAncestor(BinaryTreeNode<T>* root, T ele1, T ele2);

};
//函數(shù)名稱：GetParent
//函數(shù)功能描述：返回父結(jié)點
//函數(shù)調(diào)用之前的預(yù)備條件：傳入根結(jié)點
//返回值（如果有的話）：父結(jié)點指針
//函數(shù)的輸入?yún)?shù)：根結(jié)點、目標(biāo)結(jié)點
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被Print_upTodown調(diào)用
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current)
{
	//從二叉樹的root結(jié)點開始，查找current結(jié)點的父結(jié)點
	if(root == current)
		return root;
	BinaryTreeNode<T>* temp;
	if(root==NULL)
		return NULL;
	//找到父結(jié)點
	if((root->leftchild()==current)||(root->rightchild()==current))
		return root;
	//遞歸尋找父結(jié)點
	else if((temp=GetParent(root->leftchild(),current)) != NULL)
			return temp;
		else return GetParent(root->rightchild(),current);	
}
//函數(shù)名稱：DeleteBinaryTree
//函數(shù)功能描述：刪除樹
//函數(shù)調(diào)用之前的預(yù)備條件：樹存在
//返回值（如果有的話）：無
//函數(shù)的輸入?yún)?shù)：根結(jié)點指針
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被析溝函數(shù)調(diào)用
template<class T>
void BinaryTree<T>::DeleteBinaryTree(BinaryTreeNode<T>* root)		//刪除二叉樹或其子樹
{

    if(root != NULL)
	{
		DeleteBinaryTree(root->left);
		DeleteBinaryTree(root->right);
		delete root;
	}
}
//函數(shù)名稱：PreOrderPrint
//函數(shù)功能描述：前序遍歷打印樹
//函數(shù)調(diào)用之前的預(yù)備條件：已經(jīng)存在樹
//返回值（如果有的話）：無
//函數(shù)的輸入?yún)?shù)：根結(jié)點指針
//函數(shù)的輸出參數(shù)：縮進樹的圖形
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被主函數(shù)調(diào)用
template<class T>
void BinaryTree<T>::PreOrderPrint(BinaryTreeNode<T>* root){ //前序縮進打印樹
	static int tab = 0; //靜態(tài)局部變量用于記錄縮進值
	if (root != NULL){		
		for (int i = 1; i <= tab; i++)
			cout<<"\t";
		cout<< root->value()<< endl;
		tab++;
		PreOrderPrint(root->leftchild());
		PreOrderPrint(root->rightchild());
		tab--;
	}
}
//函數(shù)名稱：PreOrderGetPointer
//函數(shù)功能描述：前序遍歷找到給定結(jié)點的指針
//函數(shù)調(diào)用之前的預(yù)備條件：傳入根結(jié)點
//返回值（如果有的話）：給定內(nèi)容的結(jié)點的指針
//函數(shù)的輸入?yún)?shù)：根結(jié)點和給定內(nèi)容
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被主函數(shù)調(diào)用
template<class T>
BinaryTreeNode<T>* PreOrderGetPointer(BinaryTreeNode<T>* root, T element)
//前序遍歷二叉樹或其子樹得到結(jié)點的指針
{	
	if (root == NULL)//就是這個地方忘了寫害我debug了很久~_~
		return NULL;
	if (root->value() == element)			//訪問當(dāng)前結(jié)點
			return root;
	if(root->isLeaf() == false){	
		BinaryTreeNode<T>* p = NULL;
	    if ((p = PreOrderGetPointer(root->leftchild(),element) ) != NULL)//訪問左子樹
			return p;
		else
			return PreOrderGetPointer(root->rightchild(),element);			//訪問右子樹
	}
	return NULL; //用于當(dāng)遍歷結(jié)束都找不到element時,返回null
}
//函數(shù)名稱：PreOrder_Search
//函數(shù)功能描述：前序遞歸查找某個結(jié)點
//函數(shù)調(diào)用之前的預(yù)備條件：傳入根結(jié)點
//返回值（如果有的話）：bool值。true代表存在，false代表不存在
//函數(shù)的輸入?yún)?shù)：根指針和某個結(jié)點內(nèi)容
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被FindAncestor調(diào)用 

template<class T>
bool BinaryTree<T>::PreOrder_Search(BinaryTreeNode<T>* root,T ele)//查找一個結(jié)點
{
	if(root!=NULL)
	{
		if (root->value() == ele )			//訪問當(dāng)前結(jié)點
			return true;
			
		bool b1 = PreOrder_Search(root->leftchild(), ele);			//訪問左子樹
		bool b2 = PreOrder_Search(root->rightchild(), ele);			//訪問右子樹
		return b1||b2;
	}
	return false;
}
//函數(shù)名稱：FindAncestor
//函數(shù)功能描述：尋找兩個結(jié)點的公共祖先
//函數(shù)調(diào)用之前的預(yù)備條件：傳入根結(jié)點、兩個操作結(jié)點
//返回值（如果有的話）：祖先指針
//函數(shù)的輸入?yún)?shù)：根結(jié)點、兩個操作結(jié)點
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被主函數(shù)調(diào)用，調(diào)用PreOrder_Search
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::FindAncestor(BinaryTreeNode<T>* root, T ele1, T ele2)
{
	if ( PreOrder_Search(root, ele1)==false 
		||PreOrder_Search(root, ele2)==false )
			return NULL; //樹中不存在某個參數(shù)結(jié)點  

	if (root == NULL)
		return NULL;
	else if( root->value() == ele1 || root->value() == ele2 )
		return root;

	bool b1 = PreOrder_Search(root->leftchild(), ele1);
	bool b2 = PreOrder_Search(root->leftchild(), ele2); //都去左邊找
	
	if (b1 == true && b2 == true)
		return FindAncestor(root->leftchild(), ele1, ele2);
	else if (b1 == false && b2 == false)
		return FindAncestor(root->rightchild(), ele1, ele2);
	else											//各在一邊
			return root;
}
//函數(shù)名稱：Print_upTodown
//函數(shù)功能描述：從頭向下打印路徑
//函數(shù)調(diào)用之前的預(yù)備條件：傳入根結(jié)點和被打印結(jié)點
//返回值（如果有的話）：路徑長度
//函數(shù)的輸入?yún)?shù)：根結(jié)點和被打印結(jié)點
//函數(shù)的輸出參數(shù)：路徑
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被PrintPath調(diào)用
template<class T>
int BinaryTree<T>::Print_upTodown(BinaryTreeNode<T>* p,BinaryTreeNode<T>* node)
{
	static int nCount = 0; //計數(shù)器
	if (p == node) //跳出遞歸
	{
		p->visit();
		return 0;
	}
	Print_upTodown(p, GetParent(p,node));
	cout<< " --> ";
	nCount++;
	node->visit();
	
	return nCount; //將計數(shù)器返回
}
//函數(shù)名稱：PrintPath
//函數(shù)功能描述：打印兩個結(jié)點的路徑
//函數(shù)調(diào)用之前的預(yù)備條件：已經(jīng)找到公共祖先
//返回值（如果有的話）：無
//函數(shù)的輸入?yún)?shù)：兩個結(jié)點（可以相同）及其公共祖先
//函數(shù)的輸出參數(shù)：路徑和路徑長度
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：調(diào)用GetParent和Print_upTodown
template<class T>
void BinaryTree<T>::PrintPath(BinaryTreeNode<T>* p,BinaryTreeNode<T>* n1,BinaryTreeNode<T>* n2)
{
	//實參p是指向公共祖先的指針
	//先打印從Node1到祖先的路徑
	static int nCount1 = 0; //計數(shù)器1
	if(n1 != p)
		do{
			n1->visit();
			cout<< " --> ";
			nCount1++;
			n1 = GetParent(p,n1);
		}while (n1 != p);

	//再利用一個遞歸函數(shù)來實現(xiàn)從祖先打印到n2。
	int nCount2 = Print_upTodown(p, n2); //計數(shù)器2
	cout<< "\n他們的路徑長度之和為 "
		<< nCount1 + nCount2
		<< " 個邊徑單位(edge)\n";
}
//函數(shù)名稱：GenerateTree
//函數(shù)功能描述：按照前序輸入內(nèi)容產(chǎn)生對應(yīng)的樹
//函數(shù)調(diào)用之前的預(yù)備條件：有一個前序表達(dá)式
//返回值（如果有的話）：根結(jié)點的指針
//函數(shù)的輸入?yún)?shù)：表達(dá)式指針
//函數(shù)的輸出參數(shù)：無
//函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：被主函數(shù)調(diào)用
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GenerateTree(T* head) //按照前序輸入內(nèi)容產(chǎn)生對應(yīng)的樹
{
	static T* p = head;
	if(*p == '^' || *p == '\0') //后面的條件*p == '\0'是沒有必要的，但是當(dāng)有某些特殊情況的時候
								//（例如程序被修改使得某些預(yù)判斷輸入正確的函數(shù)失效時）
								//它可以增強程序的乳棒性，故做了保留
		return NULL;

	BinaryTreeNode<T>* pNode = new BinaryTreeNode<T>;
	pNode->setValue(*p);
	pNode->setLeftchild(GenerateTree(++p) );
	pNode->setRightchild(GenerateTree(++p) );
	return pNode;
}