nearzuxian.cpp

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

#include"Tree1.h"
#include"Queue2.h"
void property3(TreeNode1 *p,int &n0,int &n2)
{
	if(p!=NULL)
	{
		if(p->left==NULL&&p->right==NULL)
			n0++;
         if(p->left!=NULL&&p->right!=NULL)
			 n2++;
		 property3(p->left,n0,n2);
		 property3(p->right,n0,n2);
	}
}
TreeNode1* zu(TreeNode1 q,Tree1 T)
{
	Queue2<TreeNode1 *> q2;
	TreeNode1 *p=T.root;
	q2.enQueue(p);
	while(!q2.isEmpty())
	{
		p=q2.deQueue();
		if(p->data==q->data&&p->left==q->left&&p->right==q->right)
		return p;
		else
		{
			if(p->left!=NULL)
				q2.enQueue(p->left);
			if(p->right!=NULL)
				q2.enQueue(p->right);
		}
	}
}
TreeNode1 * neartree(TreeNode1 p,TreeNode1 q,Tree1 T)
{
	TreeNode1 q1=NULL;
	do(p=zu(p))
	while(p!=T.root)
	{
		q1=q;
		while(q1!=T.root)
		{
			if(p->data==zu(q1)&&p->left==q1->left&&p->right==q1->right)
			{
				cout<<zu(q1).data;
				return zu(q1);
			}
			else
				q1=zu(q1);
		}
		p=zu(p);
	};
	if(p=T.root)
		return p;
}

void main()
{
char *str="ABD.G...CE..FH...";
cout<<"The  Tree: "<<str<<"\0";
Tree1 t1(str);
t1.preorder();
t1.inorder();
t1.postorder();
int n0=0,n2=0;
property3(t1.root,n0,n2);
cout<<"验证二叉树性质；";
cout<<"n0="<<n0<<", n2="<<n2<<", n0==n2+1 ? ";

if(n0==n2+1)
    cout<<"正确"<<endl;
else
cout<<"错误"<<endl;
}