2. 考研
  3. 输入一整数数组{5，7，6，9，1 1，10，8}，该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意

输入一整数数组{5，7，6，9，1 1，10，8}，该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意

admin2017-04-28  83
问题 输入一整数数组{5，7，6，9，1 1，10，8}，该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。要求：

给出算法的基本设计思想。
选项
答案基本设计思想：首先，使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。 以数组{5，7，6，9，1 1，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则是它的右子结点。 再举一个反例。例如整数数组{8，1，6，5}，后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字8大于5，因此可以肯定此二叉排序树的根结点上没有左子树，数字8、1和6都是右子树结点的值。但发现在右子树中有一个结点的值是1，比根结点的值5小，这就违背了二叉排序树的定义。因此，不存在一棵二叉排序树，它的后序遍历的结果是8、1、 6、 5。 以上分析足以看出规律所在。接下来写代码吧！
解析
转载请注明原文地址:https://jikaoti.com/ti/qKfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)