#include <iostream>
using namespace std;

typedef char datatype;
typedef struct node
{
 datatype data;
 struct node *lchild,*rchild;
}bintnode;

typedef bintnode *bintree;
bintree root;                    //指向树根结点指针

// 二叉树的创建（按前序遍历顺序）

void createbintree(bintree *t)
{
 char ch;
 if((ch=getchar())==' ')
  *t=NULL;
 else
 {
  *t=(bintnode*)malloc(sizeof(bintnode));
  (*t)->data=ch;
  createbintree(&(*t)->lchild);
  createbintree(&(*t)->rchild);
 }
}

//二叉树的查找算法

bintree locate(bintree t,datatype x)
{
 bintree p;
 if(t==NULL)
  return NULL;
 else
  if(t->data==x)
   return t;
  else
  {
   p=locate(t->lchild,x);
   if(p)
    return p;
   else
    return locate(t->rchild,x);
  }
}

//统计二叉树中结点个数

int numberofnode(bintree t)
{
 if(t==NULL)
  return 0;
 else
  return(numberofnode(t->lchild)+numberofnode(t->rchild)+1);
}

//判断二叉树是否等价 ，相等返回1

int isequal(bintree t1,bintree t2)
{
 int t;
 t=0;
 if(t1==NULL && t2==NULL)
  t=1;                     
 else
  if(t1!=NULL && t2!=NULL)
   if(t1->data==t2->data)
    if(isequal(t1->lchild,t2->lchild))          //如果左子树相等
     t=isequal(t1->rchild,t2->rchild);

 return (t);
}

//求二叉树的高度（深度）

int depth(bintree t)
{
 int h,lh,rh;
 if(t==NULL)
  h=0;
 else
 {
  lh=depth(t->lchild);
  rh=depth(t->rchild);
  if(lh>=rh)
   h=lh+1;
  else
   h=rh+1;
 }
 return h;
}

int main()
{
 bintree t1,t2;
 cout<<"输入要创建的树:"<<endl;

 cout<<"\n输入第一棵树:";
 createbintree(&t1);
 cout<<endl;
  
 char ch=getchar();      //接收 输入完第一棵树后的enter键消息
  
 cout<<"\n输入第二棵树:";
 createbintree(&t2);
 cout<<endl;

 ch=getchar();             //接收 输入完第二棵树后的enter键消息
  
 

 //数据查找

 cout<<"\n输入(在t1树中)要查找的数据:";
 datatype x;                   //x 为要找的数据
 cin>>x;
 bintree f;                   //f为返回的指针
 f=locate(t1,x);              //在树t1中查找
 if(f)
  cout<<"\n找到，此数据是 :"<<f->data<<endl;
 if(!f)
  cout<<"\n不存在此数据."<<endl;

 //统计二叉树结点个数

 int n1=numberofnode(t1);
 int n2=numberofnode(t2);
 cout<<"\nt1的结点个树为:"<<n1<<endl;
 cout<<"\nt2的结点个树为:"<<n2<<endl;

 //判断两棵树是否相等

 int n=isequal(t1,t2);
 if(n)
  cout<<"\n两棵树相等."<<endl;
 if(!n)
  cout<<"\n两棵树不等."<<endl;

 //求二叉树的深度

 n1=depth(t1);
 n2=depth(t2);
 cout<<"\nt1的深度为:"<<n1<<endl;
    cout<<"\nt2的深度为:"<<n2<<endl;

}

评论