判断整数序列是不是二叉查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回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");
}
分享到:
相关推荐
在后续的分析题中,涉及了无向图的深度优先和宽度优先遍历、最小代价生成树的构建以及二叉排序树和平衡二叉树(AVL树)的构造,这些都是图论和数据结构的重要概念,具体解答如下: - 1)无向图的深度优先遍历(DFS...
5. 快速排序法对整数序列进行排序的具体步骤在这里无法详细展开,但基本流程是选取一个基准元素,将序列分为比基准小和大的两部分,然后对这两部分递归进行快速排序。 这些题目涉及到的数据结构知识是计算机科学...
2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
6. 二叉搜索树比较次数:在顺序插入10个数后构建的二叉搜索树中,元素62的比较次数取决于它在输入序列中的位置,通常情况下,如果62是中间值,比较次数最少;如果是最后一个,比较次数最多。 7. Hash链表长度:10个...
- 对二叉排序树进行中根遍历可以得到递增序列,因为中根遍历的顺序是左子树-根节点-右子树,对于排序树来说,左子树的键值小于根,右子树的键值大于根。 6. **栈和队列**: - 它们都是线性结构,但栈是后进先出...
算法利用了树的结构来高效地找到第K个节点,避免了全树遍历。 2. 原理解释:通过比较左子树和右子树的大小,可以快速定位第K大节点,减少了遍历的深度。 3. 时间复杂度证明:算法的时间复杂度与节点深度成正比,...
#### 九、AVL树的构建与删除 - **知识点概述**: - AVL树是一种自平衡的二叉搜索树,通过维护节点之间的平衡因子来保持树的高度平衡。 - **题目解析**: - 已给出一个序列,要求写出建立AVL树的过程及删除某一...
AVL树是一种自平衡二叉查找树,在任何节点处,两子树的高度差最多为1。本题中,所有非叶结点的平衡因子为1,意味着每个非叶结点都有一个孩子结点比另一个孩子结点高1层。根据平衡二叉树的性质,我们可以逐步构建出这...
要判断一棵二叉树是否为二叉排序树,可以利用中序遍历的特性。对于二叉排序树而言,其任何节点的左子树中的所有节点值均小于该节点值,而右子树中的所有节点值均大于该节点值。因此,对二叉树进行中序遍历时,节点值...
4. **内存查找**:一旦树节点被读入内存,后续的查找操作只需在内存中进行,而内存的速度远快于磁盘。 相比于普通的二叉搜索树,B+树能够显著减少磁盘I/O操作的次数,进而提高查询速度。 --- #### 三、选择题解析...
二叉搜索树、平衡树(如AVL树和红黑树)等都是重要的树结构,它们在搜索和排序中有重要作用。 6. **图**:图由节点和边组成,表示对象之间的关系。图可以用来解决复杂的问题,如网络路由、最短路径算法(Dijkstra...
《Python数据结构第三章:算法分析》 在Python编程中,数据结构与算法的理解和运用是至关重要的。本章节着重探讨了如何分析和利用各种数据结构实现高效的算法,旨在帮助初学者更好地掌握Python中的核心概念。以下是...
### 9. 数据结构中的非线性结构 在给定选项中,**二叉链表**属于非线性结构。非线性结构是指数据元素之间的关系不是简单的线性序列,而是具有分支或多对多的关系。常见的非线性结构还包括树形结构和图形结构等。 ##...
- **描述**:利用二叉查找树的数据结构来查找元素。 - **应用**:在动态数据集合中进行高效查找。 #### 三、排序 **1. 选择排序** - **描述**:每次从未排序部分找到最小(或最大)的元素,放到已排序序列的...