习题－44.c

本人收集的一些数据结构经典算法实现

//本程序只给出了算法思想
//读者可以自己完善本程序
int found=FALSE; 
Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)
//求二叉树T中结点p和q的最近共同祖先
{
	Bitree pathp[ 100 ],pathq[ 100 ] //设立两个辅助数组暂存从根到p,q的路径
		Findpath(T,p,pathp,0);
	found=FALSE;
	Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中
	for(i=0;pathp[i]==pathq[i]&&pathp[i];i++)
		; //查找两条路径上最后一个相同结点
	return pathp[--i];
}//Find_Near_Ancient 
void Findpath(Bitree T,Bitree p,Bitree path[ ],int i)//求从T到p路径的递归算法
{
	if(T==p)
	{
		found=TRUE;
		return; //找到
	}
	path[i]=T; //当前结点存入路径
	if(T->lchild) 
		Findpath(T->lchild,p,path,i+1); //在左子树中继续寻找
	if(T->rchild&&!found) 
		Findpath(T->rchild,p,path,i+1); //在右子树中继续寻找
	if(!found) 
		path[i]=NULL; //回溯
}//Findpath