document.write('二元查找树的特点是：对于任意一个结点，它的左子树上所有结点的值都小于这个结点的值，它的右子树上
所有结点的值都大于这个结点的值。根据它的这个特点以及二元查找树后序遍历的特点，可以看出，这个序
列的最后一个元素一定是树的根结点(上图中的结点4)，然后在数组中找到第一个大于根结点4的值5，那么结
点5之前的序列(1，3，2)对应的结点一定位于结点4的左子树上，结点5(包含这个结点)后面的序列一定位于
结点4的右子树上(也就是说结点5后面的所有值都应该大于或等于4)。对于结点4的左子树遍历的序列{1，3，
2}以及右子树的遍历序列{5，7，6}可以采用同样的方法来分析，因此，可以通过递归方法来实现，实现代码
如下：
"""
方法功能: 判断一个数组是否是二元查找树的后续遍历序列
输入参数: arr:数组:
返回值: true:是, 否则返回false
"""
def IsAfterOrder(arr,start,end):
if arr==None:
return False
#数组的最后一个结点必定是根结点
root=arr[end]
#找到第一个大于root的值, 那么前面所有的结点都位于root的左子树上
i=start
while i＜end:
if(arr[i]＞root):
break
i+=1
#如果序列是后续遍历的序列, 那么从i开始的所有值都应该大于根结点root的值
j=i
while j＜end:
if arr[j]＜root:
return False
j+=1
left_IsAfterOrder=True
right_IsAfterOrder=True
#判断小于root值的序列是否是某一二元查找树的后续遍历
if i＞start:
left_IsAfierOrder=IsAfterOrder(arr,start,i-1)
#判断大于root值的序列是否是某一二元查找树的后续遍历
if j＜end:
right_IsAfterOrder=IsAfterOrder(arr,i,end)
return left_IsAfterOrder and right_IsAfterOrder
if __name__="__main__":
arr=[1,3,2,5,7,6,4]
result=IsAfterOrder(arr,0,len(arr)-1)
i=0
while i＜len(arr):
print arr[i],
i+-=1
if result:
print "是某一二元查找树的后续遍历序列"
else:
print "不是某一二元查找树的后续遍历序列"
程序的运行结果为：
1 3 2 5 7 6 4是某一二元查找树的后序遍历序列
算法性能分析：
这种方法对数组只进行了一次遍历，因此，时间复杂度O(N)。
');