二叉搜索树（BST）- HDU 3791
二叉查找树（英语：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
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;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读