BST二叉排序树

二叉排序树是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有

如下性质的二叉树： ⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ⑵ 若

它的右子树非空，则右子树上所有结点的值均大于根结点的值； ⑶ 左、右子树本身又各是一棵二

叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序

序列。
相同n个结点的二叉排序树是不唯一的，形态和深度可能不同。

 

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

 

Output

如果序列相同则输出YES，否则输出NO

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct node
{
    int data;
    struct node *left,*right;
}*BiTree,BTNode;

void insert(BiTree &t,BiTree s)//&t 这个地址一定要加，否则不能改变树的结构，个t可以像平时这样用t
{
    /*
    a指向address1;
    t亦都指向address1, 但后面t已经变左，如果不用&,则a不能随着t的变而变
    */
    if(s==NULL)
        return;
    BiTree p,temp;
    if(t==NULL)
    {
        t=s;//t用来指向头结点的，下面没有用到，提供访问
    }
    else
    {
        p=t;
        while(p!=NULL)
        {
            temp=p;
            if(s->data < p->data)//遍历左子树
            {
                p=p->left;
            }
            else//往右，题目已经说明是没有重复的数字
            {
                p=p->right;
            }
        }

        if(s->data < temp->data)//插入到左子树,temp指向父结点，把s插入进来
        {
            temp->left=s;
        }
        else
        {
            temp->right=s;
        }

    }

}

int check(BiTree s, BiTree t)//比较两树是否相同；0表示相同，1表示不同
{
    if(s==NULL && t==NULL)
    {
        return 0;
    }
    else if((s==NULL && t!=NULL) || (s!=NULL && t==NULL))
    {
        return 1;
    }
    else
    {
        if(s->data != t->data)
        {
            return 1;
        }
        else
        {
            return check(s->left,t->left)+check(s->right,t->right);
        }

    }
}

int main()
{
    int n,len1,len2,i,result;
    char s[11],q[11];
    while(scanf("%d",&n)!=EOF)
    {
           if(n==0)break;

           scanf("%s",s);
           len1=strlen(s);
           BiTree t;
           t=NULL;
           for(i=0;i<len1;i++)//建立示范序列的二叉树；
           {
                 BiTree p;
                 p=(BiTree)malloc(sizeof(BTNode));
                 p->data=s[i]-'0';
                 p->left=NULL;
                 p->right=NULL;
                 insert(t,p);
           }
           while(n--)
         {
                 scanf("%s",q);
                 len2=strlen(q);
                 BiTree r;
                 r=NULL;
                 for(i=0;i<len1;i++)//建立示范序列的二叉树；
                 {
                     BiTree p;
                     p=(BiTree)malloc(sizeof(BTNode));
                     p->data=q[i]-'0';
                     p->left=NULL;
                     p->right=NULL;
                     insert(r,p);
                 }
                 result=check(r,t);
                 if(result==0){
                      printf("YES\n");
                 }
                 else{
                      printf("NO\n");
                 }
           }

    }
    return 0;
}