tree.cpp

大学计算机专业课程中数据结构各章的算法设计

#include"Tree1.h"  //二叉数文件
#include"Queue2.h"  //队列文件
TreeNode1 * zu(TreeNode1 *q,Tree1 &T) 
{
	Queue2<TreeNode1 *> q2;
	TreeNode1 *p=T.root;

	q2.enQueue(p);
	while(!q2.isEmpty())
	{
		p=q2.deQueue();
		if(p->left!=NULL)
		{
	        if(p->left->data==q->data)
			return p;
		}
		if(p->right!=NULL)
		{
	        if(p->right->data==q->data)
			return p;
		}

	    if(p->left!=NULL)
				q2.enQueue(p->left);
	    if(p->right!=NULL)
				q2.enQueue(p->right);
	}
	cout<<"不存在"<<endl;
	return NULL;
}
TreeNode1 * neartree(TreeNode1 *p,TreeNode1 *q,Tree1 &T)
{
	TreeNode1 *q1=NULL,*p1=NULL;
 
	for(p1=zu(p,T);p1!=T.root&&p1!=NULL;p1=zu(p1,T))
	
	{
		q1=zu(q,T);
		while(q1!=T.root&&q1!=NULL)
		{
			if(p1->data==q1->data)
			    return q1;
		    else
				q1=zu(q1,T);
		}
	}
	if(p1==T.root)
		return p1;
	else
		cout<<"无祖先"<<endl;
	return NULL;
}

void main()
{
char *str="ABD.G...CE..FH...";
cout<<"The  Tree: "<<str<<"\0";
Tree1 t1(str);
t1.preorder();
//t1.inorder();
//t1.postorder();

TreeNode1 * a=NULL;
TreeNode1 * b=NULL;
TreeNode1 * c=NULL;

a=new TreeNode1('G');
b=new TreeNode1('H');

c=neartree(a,b,t1);
cout<<"两节点为："<<a->data<<"  "<<b->data<<endl;
if(c!=NULL)
cout<<"最进祖先为："<<c->data<<endl;
}