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

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

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

根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
选项
答案算法实现如下： bool verifySquenceofBST(int squence[]，int length) { ／／判断非法输入数组 if(squence==NULL ｜｜ length＜=0) return false； ／／将数组的最后一个值赋值给根结点的值 int root=squence[1ength-1]； ／／在二叉排序树中左子树的结点值小于根结点的值 int i=0; for(；i＜length-1；i++) { if(squence[i]＞root) break； } ／／在二叉捧序树中右子树的结点值大于根结点的值 int j=i; for(；j＜length-1；j++) { if{squence[j]＜root) return false； } ／／判断左子树是不是二叉排序树 booi left=true; if(i＞0) left=verifySquenceOfBST(squence，i)； ／／判断右子树是不是二叉排序树 bool right=true； if(i＜length-i) right=verifySquenceOfBST(squence+i，length-i-1)； return(1eft＆＆right)； }
解析
转载请注明原文地址:https://kaotiyun.com/show/ujRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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