36.cpp

判断给定的二叉树是否相似

#include <iostream.h>
#include<strstrea.h>

struct BitreeNode
{
	char data;
	BitreeNode *lchild;
	BitreeNode *rchild;
};


void CreateBitree(BitreeNode *&BT,char *a)
{
	BitreeNode *s[10];
	int top=-1;
	BT=NULL;
	BitreeNode *p;
	int k;
	istrstream ins(a);
	char ch;
	ins>>ch;
	while(ch!='@')
	{
		switch(ch)
		{
			case '(':
				top++;
				k=1;
				s[top]=p;
				break;
			case ')':
				top--;
				break;
			case ',':
				k=2;
				break;
			default:
				p=new BitreeNode;
				p->data=ch;
				p->lchild=p->rchild=NULL;
			    if(BT==NULL)
				   BT=p;
				else
				{
					switch(k)
					{
					case 1:
						s[top]->lchild=p;
						break;
					case 2:
						s[top]->rchild=p;
					}
				}
		}

		ins>>ch;
	}
}


int Bitree_Similar(BitreeNode *B1,BitreeNode *B2)//判断两棵给定的二叉树是否相似的递归算法
{
  if(B1==NULL&&B2==NULL) return 1;
  else if(B1&&B2&&Bitree_Similar(B1->lchild,B2->lchild)&&Bitree_Similar(B1->rchild,B2->rchild))
    return 1;
  else return 0;
}

void main()
{
    int k;
	char a[50],b[50];
    BitreeNode *B1=NULL,*B2=NULL;
	cout<<"请输入第一个二叉树:"<<endl;
	cin.getline(a,sizeof(a));
    cout<<"请输入第一个二叉树:"<<endl;
    cin.getline(b,sizeof(b));
    CreateBitree(B1,a);
	CreateBitree(B2,b);
	k=Bitree_Similar(B1,B2);
	if(k==1)
		cout<<"这两个二叉树相似!"<<endl;
	else
		cout<<"这两个二叉树不相似!"<<endl;
}