二叉排序树

偏执的太偏执、 2022-07-12 07:48 159阅读 0赞

Problem Description

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

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

Example Input

2  
123456789  
987654321  
432156789  
0  
Example Output

NO  
NO  
Hint

Author

**因为要判断是不是同一二叉排序树，所以就判断是否等于它本身。**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct node
    {
        int data;
        struct node *l, *r;
    };
    struct node *creat(struct node *root, char number)//建树
    {
        if(root == NULL)
        {
            root = (struct node *) malloc(sizeof(struct node));
            root -> data = number;
            root -> l = NULL;
            root -> r = NULL;
        }
        else
        {
            if(root -> data > number)
                root -> l = creat(root -> l, number);
            else
                root -> r = creat(root -> r, number);
        }
        return root;
    };
    int x = 0;
    void judge(struct node *root1, struct node *root2)
    {
        if(root1 == NULL || root2 == NULL)
        {
            return;
        }
        if(root1 && root2)
        {
            if(root1 -> data != root2 -> data)
                return;
            else
            {
                x++;
                judge(root1 -> l, root2 -> l);
                judge(root1 -> r, root2 -> r);
            }
        }
    }
    int main()
    {
        int n, len, i, j;
        char a[22], b[22];
        while(scanf("%d", &n) != EOF)
        {
            if(n == 0) break;
            struct node *root1 = NULL;//划重点
            scanf("%s", a);
            len = strlen(a);
            for(i = 0; i < len; i++)
                root1 = creat(root1, a[i]);
            for(i = 0; i < n; i++)
            {
                x = 0;//划重点
                struct node *root2 = NULL;//划重点
                scanf("%s", b);
                for(j = 0; j < len; j++)
                {
                    root2 = creat(root2, b[j]);
                }
                judge(root1, root2);
                if(x == len) printf("YES\n");
                else printf("NO\n");
            }
        }
        return 0;
    }