二叉搜索树（BST）- HDU 3791

ACM算法日常

发布于 2018-08-07 10:45:31

81500

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

虽然二叉查找树的最坏效率是O(n)，但它支持动态查询，且有很多改进版的二叉查找树可以使树高为O(log n)，如SBT，AVL树，红黑树等。故不失为一种好的动态查找方法。

题目：

Problem Description

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

Input

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

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

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

Output

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

Sample Input

567432

543267

576342

Sample Output

YES

解题思路：

对于任意的一个输入序列S，第一个元素是根节点，每次将序列中的元素与第一个元素比较，小于的放在左边，大于的放在右边，对于每次分好的左孩子序列SL和右孩子序列SR，执行与S相同的操作。

性能关键点：采用数组的方式存储左右孩子，函数传递参数时不需要拷贝字符串操作，不涉及堆内存分配和销毁操作。

源代码：G++ 0ms

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

//是否是同一棵binary search tree
int is_same_bst(char * bst, char * bst_cmp, int len) {
    //第一个表示根节点，根节点肯定相同
    if (bst[0] != bst_cmp[0])
        return 0;
    //长度为0或者为1或者为2的时候比较一下
    if (len <= 1 || (len == 2 && bst[1] == bst_cmp[1])) {
        return 1;
    }
    //分配左右孩子树的存储空间
    char bst_left[10] = "", bst_right[10] = "", 
        bst_cmp_left[10] = "", bst_cmp_right[10] = "";
    int bl = 0, br = 0, bcl = 0, bcr = 0;

    for (int i = 1; i < len; i++) {
        //依次放在左右孩子上
        bst[i] > bst[0] ? (bst_right[br++] = bst[i]) : (bst_left[bl++] = bst[i]);
        bst_cmp[i] > bst_cmp[0] ? (bst_cmp_right[bcr++] = 
            bst_cmp[i]) : (bst_cmp_left[bcl++] = bst_cmp[i]);
    }
    //递归判断子树是否是一样的
    return is_same_bst(bst_left, bst_cmp_left, bl) && 
        is_same_bst(bst_right, bst_cmp_right, br);
}

int main() {
    int cmp_count;
    char bst[30], bst_cmp[30];

    while (~scanf("%d", &cmp_count) && cmp_count) {
        scanf("%s", bst);
        while (cmp_count--) {
            scanf("%s", bst_cmp);
            //判断是否是一样的bst函数
            printf("%s\n", is_same_bst(bst, bst_cmp, 
                strlen(bst)) ? "YES" : "NO");
        }
    }
    return 0;
}