【正确答案】正确答案：基本设计思想：首先，使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。 以数组{5，7，6，9，1 1，10，8）为例，后序遍历结果的最后一个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的根结点的左子树特点；后3个数字9、11和10都比8大，是值为8的根结点的右子树结点。接下来需要用同样的方法确定与数组每一部分对应的子树结构。很明显，这是一个递归的过程。对于整数序列5、7和6，最后一个数字6是左子树的根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11和10中，最后一个数字10是右子树的根结点的值，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。 再举一个反例。例如整数数组{8，1，6，5}，后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字8大于5，因此可以肯定此二叉排序树的根结点上没有左子树，数字8、1和6都是右子树结点的值。但发现在右子树中有一个结点的值是1，比根结点的值5小，这就违背了二叉排序树的定义。因此，不存在一棵二叉排序树，它的后序遍历的结果是8、1、 6、 5。 以上分析足以看出规律所在。接下来写代码吧！

【正确答案】正确答案：算法实现如下： 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)， }

【正确答案】正确答案：算法每次确定当前数组中的最后一个为子树的根，然后对数组进行扫描，把数组分成两部分，前面一部分是比根小的，作为左子树，后面一部分比根大的，作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树，并判断构造出来的树是否合法。同样地考虑一个递增的数组，每次只能分离出最后一个作为树根，然后往下递归。在这个过程中，第i层的数组里有n—i+1个数，这样总的扫描的次数为n(n—1)/2，所以时间复杂度为O(n ² )。 扩展：输入一个整数数组，判断该数组是不是某二叉排序树的前序遍历的结果。该题与前面分析的后序遍历非常类似，只是在前序遍历得到的序列中，第一个数字是根结点的值。