二叉排序树

柔情只为你懂 2024-02-18 22:49 5阅读 0赞

#### 二叉排序树 ####

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

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

Input

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

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

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

Output

Sample Input

2
    123456789
    987654321
    432156789
    0

Sample Output

NO
    NO

Hint

Source

思路：和上一个一样，套模板建立二叉排序树，比较树的数值

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        char data;
        struct node *lc;
        struct node *rc;
    };
    struct node *creat(struct node *root, int x)
    {
        if(root == NULL)
        {
            root = (struct node *)malloc(sizeof(struct node));
            root->lc = NULL;
            root->rc = NULL;
            root->data = x;
        }
        else
        {
            if(x > root->data)
            {
                root->rc = creat(root->rc, x);
            }
            else
            {
                root->lc = creat(root->lc, x);
            }
        }
        return root;
    };
    int flag;
    void bijiao(struct node *root, struct node *root1)
    {
        if(root != 0 && root1 != 0)
        {
            if(root->data != root1->data)
            {
                flag = 1;
                return;
            }
            bijiao(root->lc, root1->lc);
            bijiao(root->rc, root1->rc);
        }
    }
    int main()
    {
        int n, i, len1, len2;
        char a[11], b[11];
        struct node *root;
        struct node *root1;
        while(scanf("%d", &n) != EOF)
        {
            if(n == 0)
            {
                break;
            }
            else
            {
                scanf("%s", a);
                len1 = strlen(a);
                root = NULL;
                for(i = 0; i < len1; i++)
                {
                    root = creat(root, a[i]);
                }
                while(n--)
                {
                    flag = 0;
                    scanf("%s", b);
                    len2 = strlen(b);
                    root1 = NULL;
                    for(i = 0; i < len2; i++)
                    {
                        root1 = creat(root1, b[i]);
                    }
                    bijiao(root, root1);
                    if(flag == 0)
                    {
                        printf("YES\n");
                    }
                    else
                    {
                        printf("NO\n");
                    }
                }
            }
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2563/pid/2482.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2563/pid/2482.html