判断一个序列是否是二叉查找树的后序、前序、中序遍历序列

2024-07-10 15:31| 来源: 网络整理| 查看: 265

本文参考：http://zhedahht.blog.163.com/blog/static/25411174200725319627/

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

8 / \ 6 10 / \ / \ 5 7 9 11

因此返回true。

在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于根结点开始到根结点前面的一个元素为止，所有元素都应该大于根结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。

就拿上面那个序列{5、7、6、9、11、10、8}为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的节点的左子树节点；后3个数字9,11,10都比8大，是值为8的节点的右子树节点。我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列5,7,6，最后一个数字6是左子树的根节点的值。数字5比6小，是值为6的节点的左子结点，而7则是它的右子节点。同样，在序列9,11,10中，最后一个数字10是右子树的根节点，数字9比10小，是值为10的节点的左子结点，而11则是它的右子结点。

我们再来分析另一个序列{7,4,6,5}。后序遍历的最后一个数是根节点，因此根节点的值是5.由于第一个数字7大于5，因此在对应的二叉搜索树中，根节点上是没有左子树的，数字7,4,6都是右子树节点的值。但我们发现在右子树中有一个节点的值是4，比根节点的值5小，这违背了二叉搜索树的定义。因此不存在一颗儿茶搜索树，它的后续遍历的结果是7,4,6,5。

明白规律后，代码如下：

#include using namespace std; bool invaluedInput = false; //检查序列sequence是否是二叉查找树的后序遍历序列,start与end分别是序列的开始与结束位置 bool CheckSequenceOfLRDOfBST(int sequence[],int start,int end) { if(NULL == sequence || start > end) { invaluedInput = true; return false; } //只有一个节点时，返回true if(start == end) return true; //根节点为序列的最后一个值 int root = sequence[end]; int bound = start; /*bound为序列的左子树与右子树的分界点，左子树的值都小于根节点的值，bound指向序列中第一个大于root的值，即右子树的开始节点,bound--en-1为右子树序列*/ for(bound; bound root) break; } int i = bound; //在右子树的序列中如果查找到一个节点值小于根节点的值，则不符合二叉查找树的定义，返回false for(i; istart) left = CheckSequenceOfLRDOfBST(sequence,start,bound-1); //递归判断序列右半边是不是二叉查找树的后续序列，如果bound==end则这颗二叉查找树无右子树 if(bound

【本文地址】

公司简介

联系我们