二叉搜索树(BST)- HDU 3791

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

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

虽然二叉查找树的最坏效率是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

2

567432

543267

576342

0

Sample Output

YES

NO

解题思路:

对于任意的一个输入序列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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-03-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

37460
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

30130
来自专栏我就是马云飞

ArrayList到底是什么?

ArrayList是日常开发中使用最频繁的集合类。首先这边简单介绍一下ArrayList:

19420
来自专栏数据结构与算法

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

31650
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

9610
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

20620
来自专栏JavaQ

源码阅读之ArrayList

源码阅读是基于JDK7,本篇主要涉及ArrayList常用方法源码分析。 1.概述 ArrayList是List接口的可调整大小的数组实现,可以包含任何类型的元...

34740
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

24070
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

21680
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

20970

扫码关注云+社区

领取腾讯云代金券