九度OJ 1009：二叉搜索树 （二叉树）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：6321

解决：2767

题目描述：

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

输入：

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

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

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

输出：

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

样例输入：

2

567432

543267

576342

0

样例输出：

YES

NO

来源：

2010年浙江大学计算机及软件工程研究生机试真题

思路：

有两种方法，一种是静态数组模拟二叉树，另一种是直接建树。

判断相等用递归即可。

代码：

#include <stdio.h>

#include <stdlib.h>

#define M 10

struct node {

    int k;

    struct node *l;

    struct node *r;

};

struct node *create (struct node *h, int k)

{

    if (h == NULL)

    {

        struct node *p = malloc(sizeof(struct node));

        p->k = k;

        p->l = NULL;

        p->r = NULL;

        return p;

    }

    if (k == h->k)

        return h;

    if (k < h->k)

        h->l = create(h->l, k);

    else

        h->r = create(h->r, k);

    return h;

}

int issame(struct node *ha, struct node *hb)

{

    if (ha == NULL && hb == NULL)

        return 1;

    if (ha == NULL || hb == NULL)

        return 0;

    if (ha->k != hb->k)

        return 0;

    if ( issame(ha->l, hb->l) == 0)

        return 0;

    if ( issame(ha->r, hb->r) == 0)

        return 0;

    return 1;

}

void delete(struct node *h)

{

    if (h == NULL)

        return;

    delete(h->l);

    delete(h->r);

    free(h);

}

int main()

{

    int i, k, n, tmp;

    int result;

    char s[M+1];

    struct node *ha = NULL, *hb = NULL;

    while(scanf("%d", &n) != EOF)

    {

        if (n == 0)

            break;

        ha = NULL;

        scanf("%s", s);

        for (i=0; s[i]; i++)

        {

            tmp = s[i]-48;

            //printf("i=%d\n", i);

            ha = create(ha, tmp);

        }

        for (k=0; k<n; k++)

        {

            hb = NULL;

            scanf("%s", s);

            for (i=0; s[i]; i++)

            {

                tmp = s[i]-48;

                //printf("i=%d\n", i);

                hb = create(hb, tmp);

            }

            result = issame(ha, hb);

            if (result == 1)

                printf("YES\n");

            else

                printf("NO\n");

            delete(hb);

        }

    }

    return 0;

}

/**************************************************************

    Problem: 1009

    User: liangrx06

    Language: C

    Result: Accepted

    Time:0 ms

    Memory:912 kb

****************************************************************/