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

admin2017-11-20 57

问题输入一整数数组{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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

明朝初加强专制统治的措施中，与后来宦官专权有直接关系的是()。

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

为了使工件在夹具中有—个确定的位置，就需要将它的()个自由度全部加以限制。

“生当作人杰，死亦为鬼雄”两句诗的作者是()

作HLA-Ⅱ类分子分型时，应用最广，最简便快捷和精确的方法是

在土地承包经营期限内，对个别承包经营者之间承包的土地进行适当调整的，必须经()或()的同意，并报乡（镇）人民政府和县级人民政府农业行政主管部门批准。

税收合作信赖主义认为税收征纳双方的关系就其主流来看是相互信赖、相互合作的，而不是对抗性的。下列关于税收合作信赖主义的理解正确的是()。

国家助学贷款采取“借款人申请、银行审批、单户核算、发放”的方式。()

格式条款发生的下列情形中，不直接导致条款无效的是()。

开轩面场圃，__________。(孟浩然《过故人庄》)

有限责任公司的股东对公司负有限责任，是指()对公司承担责任。

由于染色体先天缺陷而导致的疾病是()。

计算机408

学硕统考专业

明朝初加强专制统治的措施中，与后来宦官专权有直接关系的是()。

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

为了使工件在夹具中有—个确定的位置，就需要将它的()个自由度全部加以限制。

“生当作人杰，死亦为鬼雄”两句诗的作者是()

作HLA-Ⅱ类分子分型时，应用最广，最简便快捷和精确的方法是

在土地承包经营期限内，对个别承包经营者之间承包的土地进行适当调整的，必须经()或()的同意，并报乡（镇）人民政府和县级人民政府农业行政主管部门批准。

税收合作信赖主义认为税收征纳双方的关系就其主流来看是相互信赖、相互合作的，而不是对抗性的。下列关于税收合作信赖主义的理解正确的是()。

国家助学贷款采取“借款人________申请、银行________审批、单户核算、________发放”的方式。()

格式条款发生的下列情形中，不直接导致条款无效的是()。

开轩面场圃，__________。(孟浩然《过故人庄》)

有限责任公司的股东对公司负有限责任，是指()对公司承担责任。

由于染色体先天缺陷而导致的疾病是()。

国家助学贷款采取“借款人申请、银行审批、单户核算、发放”的方式。()