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

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

admin2014-04-17  64
问题 输入一整数数组{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[length一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； } ／／判断左子树是不是二叉排序树 bool left=true； if(i＞0) left=verifySquenceofBST(squence，i)； ／／判断右予树是不是二叉排序树 bool right=true； if(i＜length-1) right=verifySquenceOfBST(squence+i，length-i-1)； return(left ＆＆right)； }
解析
转载请注明原文地址:https://kaotiyun.com/show/Klxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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