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

admin2014-04-17  44

问题 输入一整数数组{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://jikaoti.com/ti/M3ajFFFM
0

最新回复(0)