binarytree.h

二叉树最短路径问题

// BinaryTree.h: 树的类定义
//文件名称： BinaryTree.h
//项目名称：shortest_way_main.dsw
//创建者：黄冀渝
//创建时间：Sept.30 2004
//最后修改时间：Oct.6 2004
//功能： 打印给定两个结点的最短路径
 
//与其他文件的依赖关系：头文件
#include "BinaryTreeNode.h"
#include <stack>
#include <queue>

//类名称：BinaryTree 
//定义该类的目的：树定义
//类属性：基类
//类中函数及功能：详见注释
//与其他类的关系（调用/被调用哪类对象中的什么函数）：是BinaryTreeNode类的友元
template <class T>
class BinaryTree  
{
protected:
	BinaryTreeNode<T>*  root;      							//二叉树根结点指针
public:
	BinaryTree(){root=NULL;};								//构造函数
	virtual ~BinaryTree(){DeleteBinaryTree(root);};			//析构函数
	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结点开始，查找current结点的父结点
	BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current);
	//前序遍历打印二叉树
	void PreOrderPrint(BinaryTreeNode<T>* root);
	//指定内容，前序遍历得到指针
	BinaryTreeNode<T>* PreOrderGetPointer(BinaryTreeNode<T>* root, T element); 
 
	//按照中序输入内容产生对应的树
	BinaryTreeNode<T>* GenerateTree(T* num);
	//一个打印从祖先到子孙(自下而上)的函数，利用递归实现
	int Print_upTodown(BinaryTreeNode<T>* p,BinaryTreeNode<T>* node);
	//打印两个结点的最短路径
	void PrintPath( BinaryTreeNode<T>* ancestor,BinaryTreeNode<T>* Node1,BinaryTreeNode<T>* Node2);
	//前序递归查找结点
	bool PreOrder_Search(BinaryTreeNode<T>* root, T element);
	//寻找两个结点的最近的公共祖先并将找到的祖先返回
	BinaryTreeNode<T>* FindAncestor(BinaryTreeNode<T>* root, T ele1, T ele2);

};
//函数名称：GetParent
//函数功能描述：返回父结点
//函数调用之前的预备条件：传入根结点
//返回值（如果有的话）：父结点指针
//函数的输入参数：根结点、目标结点
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被Print_upTodown调用
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current)
{
	//从二叉树的root结点开始，查找current结点的父结点
	if(root == current)
		return root;
	BinaryTreeNode<T>* temp;
	if(root==NULL)
		return NULL;
	//找到父结点
	if((root->leftchild()==current)||(root->rightchild()==current))
		return root;
	//递归寻找父结点
	else if((temp=GetParent(root->leftchild(),current)) != NULL)
			return temp;
		else return GetParent(root->rightchild(),current);	
}
//函数名称：DeleteBinaryTree
//函数功能描述：删除树
//函数调用之前的预备条件：树存在
//返回值（如果有的话）：无
//函数的输入参数：根结点指针
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被析沟函数调用
template<class T>
void BinaryTree<T>::DeleteBinaryTree(BinaryTreeNode<T>* root)		//删除二叉树或其子树
{

    if(root != NULL)
	{
		DeleteBinaryTree(root->left);
		DeleteBinaryTree(root->right);
		delete root;
	}
}
//函数名称：PreOrderPrint
//函数功能描述：前序遍历打印树
//函数调用之前的预备条件：已经存在树
//返回值（如果有的话）：无
//函数的输入参数：根结点指针
//函数的输出参数：缩进树的图形
//函数与其他对象中函数的调用和被调用关系：被主函数调用
template<class T>
void BinaryTree<T>::PreOrderPrint(BinaryTreeNode<T>* root){ //前序缩进打印树
	static int tab = 0; //静态局部变量用于记录缩进值
	if (root != NULL){		
		for (int i = 1; i <= tab; i++)
			cout<<"\t";
		cout<< root->value()<< endl;
		tab++;
		PreOrderPrint(root->leftchild());
		PreOrderPrint(root->rightchild());
		tab--;
	}
}
//函数名称：PreOrderGetPointer
//函数功能描述：前序遍历找到给定结点的指针
//函数调用之前的预备条件：传入根结点
//返回值（如果有的话）：给定内容的结点的指针
//函数的输入参数：根结点和给定内容
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被主函数调用
template<class T>
BinaryTreeNode<T>* PreOrderGetPointer(BinaryTreeNode<T>* root, T element)
//前序遍历二叉树或其子树得到结点的指针
{	
	if (root == NULL)//就是这个地方忘了写害我debug了很久~_~
		return NULL;
	if (root->value() == element)			//访问当前结点
			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; //用于当遍历结束都找不到element时,返回null
}
//函数名称：PreOrder_Search
//函数功能描述：前序递归查找某个结点
//函数调用之前的预备条件：传入根结点
//返回值（如果有的话）：bool值。true代表存在，false代表不存在
//函数的输入参数：根指针和某个结点内容
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被FindAncestor调用 

template<class T>
bool BinaryTree<T>::PreOrder_Search(BinaryTreeNode<T>* root,T ele)//查找一个结点
{
	if(root!=NULL)
	{
		if (root->value() == ele )			//访问当前结点
			return true;
			
		bool b1 = PreOrder_Search(root->leftchild(), ele);			//访问左子树
		bool b2 = PreOrder_Search(root->rightchild(), ele);			//访问右子树
		return b1||b2;
	}
	return false;
}
//函数名称：FindAncestor
//函数功能描述：寻找两个结点的公共祖先
//函数调用之前的预备条件：传入根结点、两个操作结点
//返回值（如果有的话）：祖先指针
//函数的输入参数：根结点、两个操作结点
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被主函数调用，调用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; //树中不存在某个参数结点  

	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;
}
//函数名称：Print_upTodown
//函数功能描述：从头向下打印路径
//函数调用之前的预备条件：传入根结点和被打印结点
//返回值（如果有的话）：路径长度
//函数的输入参数：根结点和被打印结点
//函数的输出参数：路径
//函数与其他对象中函数的调用和被调用关系：被PrintPath调用
template<class T>
int BinaryTree<T>::Print_upTodown(BinaryTreeNode<T>* p,BinaryTreeNode<T>* node)
{
	static int nCount = 0; //计数器
	if (p == node) //跳出递归
	{
		p->visit();
		return 0;
	}
	Print_upTodown(p, GetParent(p,node));
	cout<< " --> ";
	nCount++;
	node->visit();
	
	return nCount; //将计数器返回
}
//函数名称：PrintPath
//函数功能描述：打印两个结点的路径
//函数调用之前的预备条件：已经找到公共祖先
//返回值（如果有的话）：无
//函数的输入参数：两个结点（可以相同）及其公共祖先
//函数的输出参数：路径和路径长度
//函数与其他对象中函数的调用和被调用关系：调用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; //计数器1
	if(n1 != p)
		do{
			n1->visit();
			cout<< " --> ";
			nCount1++;
			n1 = GetParent(p,n1);
		}while (n1 != p);

	//再利用一个递归函数来实现从祖先打印到n2。
	int nCount2 = Print_upTodown(p, n2); //计数器2
	cout<< "\n他们的路径长度之和为 "
		<< nCount1 + nCount2
		<< " 个边径单位(edge)\n";
}
//函数名称：GenerateTree
//函数功能描述：按照前序输入内容产生对应的树
//函数调用之前的预备条件：有一个前序表达式
//返回值（如果有的话）：根结点的指针
//函数的输入参数：表达式指针
//函数的输出参数：无
//函数与其他对象中函数的调用和被调用关系：被主函数调用
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GenerateTree(T* head) //按照前序输入内容产生对应的树
{
	static T* p = head;
	if(*p == '^' || *p == '\0') //后面的条件*p == '\0'是没有必要的，但是当有某些特殊情况的时候
								//（例如程序被修改使得某些预判断输入正确的函数失效时）
								//它可以增强程序的乳棒性，故做了保留
		return NULL;

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