判断整数序列是不是二叉查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如:输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历(左右根)结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
分析:最后一个输出的节点为,根节点。因为7大于根节点,所以前三个节点应该为右子树。而4应该为5左子树所以此序列不是任何一个二叉查找树的后续遍历结果。
求解思路:采用分治思想。
先是整体:最后一个为根节点,然后从前向后遍历序列,直到大于根节点(此时将左子树过滤)
然后验证:过滤掉左子树,除去根节点后,剩余节点为右子树。只要右子树所有节点大于根则正确,否则不是后序遍历序列。
分治验证:对左、右子树,采用同样的方法验证。
源码:
#include"stdio.h"
/*后序遍历,最后输出的节点,一定是根节点
此题的解法,采用思想:分治
*/
bool Test_Squence_BST(int squence[], int length)
{
if(squence == NULL || length <= 0)//如果输出序列为空,或者输出长度为0则返回false
return false;
int root = squence[length - 1];//
int i = 0;
for(; i < length - 1; ++ i)//将二叉查找树,左子树过滤掉
{
if(squence[i] > root) //找到大于根的节点
break;
}
int j = i;//采用j的原因是,让i记录左子树个数
for(; j < length - 1; ++ j) //过滤掉左子树后,剩余的除了根节点外,理论上全为右子树
{
if(squence[j] < root)
return false;//如果存在不正确的,这里就会返回false .不会继续递归调用子树
}
bool left = true;//验证左子树,是否也为后序遍历序列
if(i > 0)
left = Test_Squence_BST(squence, i);
bool right = true;//验证右子树,是否也为后序遍历序列
if(i < length - 1)
right = Test_Squence_BST(squence + i, length - i - 1);
return (left && right);
}
int main()
{
//int a[7]={5,7,6,9,11,10,8};
int a[4]={7,4,6,5};
if(Test_Squence_BST(a,4))
printf("YES");
else
printf("NO");
}
分享到:
相关推荐
输入一整数序列,建立二叉排序树,然后中序遍历。 输入说明 输入第一行为整数的个数n,第二行是具体的n个整数。 输出说明 建立二叉排序树,然后输出中序遍历的结果。 输入样例 5 1 6 5 9 8 输出样例 1 5 6 8 9
采用llink-rlink方式存储二叉排序树,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序
中序遍历 二叉查找树 折半查找,适合初学者。
二叉查找树的先序中序后续遍历
C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好
java基础面试题二叉搜索树的后续遍历序列本资源系百度网盘分享地址
二叉查找树的插入、删除、遍历和查找等操作的C++实现,二叉查找树采用泛型结构
查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列就是按照从小到大的顺序排列的,而最后删除二叉排序树的时候,要先删除子节点,才能删除父节点,其实...
大学课程、数据结构、C代码、设计一个读入一串整数构成一颗二叉排序树的程序,从二叉排序树中删除一个结点,使该二叉树仍保持二叉排序树的特性。
这个程序实现了二叉查找树的删除,增加,先序遍历,后序遍历,中序遍历,还有一些非递归和层次遍历!
建立一位数组,然后以一位数组为例进行二叉排序树的中序遍历
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。
对二叉排序树的遍历,插入和删除操作 C语言实现。。
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5...
java实现二叉查找树的插入、删除、遍历、查询
//输入一个数列以0为结束标志,建立二叉遍历树,并对其进行逆中序遍历,释放空间,0代表null
二叉排序树的建立和遍历~~~ 二叉排序树的建立和遍历~~~ 二叉排序树的建立和遍历~~~
根据输入数据建造二叉排序树,并中序遍历,从而输出结果