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

根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
选项
答案算法实现如下： int rdfs (ADJLIST g，int vi) { int i，count， yes； yes=0； count=1； stack s； for(int i=0； i＜n； i++)visited[i] =0；//初始化访问标记数组 push (vi，s) ； visited [vi]=i； //初始化 while ( ! empty (s) &&yes—=0) { int w=top (s) ； p=g[w]，firstarc； while(p !=NULL&&visited[p—＞adj data]) { p=p—＞next； if (p==NULL) pop (s)； else { w=p—＞adjdata； visited [w]=1； count++； push (w， s) ； } } } if(count==n)//n为该有向图中的结点数 yes=1； return yes； break； } //在二叉排序树中右子树的结点值大于根结点的值 int j=i； for(；j＜length—1；j++) { if (sequence[j]＜root) return false； } //判断左子树是不是二叉排序树 bool left=true； if (i＞0) left=verifySquenceOfBST（（squence，i)， //判断右子树是不是二叉排序树 bool right=true； if (i＜length—1} right=verifySquenceofBSlf squence+i，length—i—1)； return (left＆＆right)， }
解析
转载请注明原文地址:https://kaotiyun.com/show/2XRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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