<sdut-ACM> 2482二叉排序树

梦里梦外; 2022-09-25 06:23 134阅读 0赞

## 二叉排序树  Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ ##

## 题目描述 ##

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树

## 输入 ##

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)

## 输出 ##

## 示例输入 ##

2
    123456789
    987654321
    432156789
    0

## 示例输出 ##

NO
    NO

## 提示 ##

#include
         
          
    #include
          
           
    #include
           
            
    
    //char q[30];
    int k;
    
    typedef struct node
    {
        int data;
        struct node *l, *r;
    }tree;
    
    tree *inserttree(tree *p, int key)           //插入单个元素
    {
        if(p == NULL)                            //第一个节点
        {
            p = (tree *)malloc(sizeof(tree));
            p->l = p->r = NULL;
            p->data = key;
            return p;
        }
        if(key < p->data)
            p->l = inserttree(p->l, key);
        else
            p->r = inserttree(p->r, key);
        return p;
    }
    
    tree *creat(tree*p, char a[], int len)      //建树
    {
        for(int i=0; i
            
             data;
            pretravel(p->l, q);
            pretravel(p->r, q);
        }
    }
    
    int main()
    {
        tree *p, *f;
        char a[20], b[20];
        int n, len, len1;
        while(scanf("%d",&n)!=EOF)
        {
            if(n == 0)               //如果是0，直接结束
            return 0;
            scanf("%s",a);
            len = strlen(a);
            p = NULL;
            p = creat(p, a, len);
            pretravel(p,a);
            //q[k] = '\0';
            while(n--)
            {
                k = 0;
                scanf("%s",b);
                len1 = strlen(b);
                f = NULL;
                f = creat(f, b, len1);
                pretravel(f,b);
                //q[k] = '\0';
                if(strcmp(a,b) == 0)           //比较是否为同一棵树
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
        return 0;
    }