比如：
我们知道，后序遍历的最后一个元素就是根节点，前边比它小的都位于根的左子树上，比它大的都位于根的右子树上。所以，对于上述的序列： 8是这棵二叉搜索树的根。 3，7 ，6都小于8，都位于8的左子树上。 6又是左子树的根，3小于6，是左子树的左孩子，7大于6，是左子树的右孩子。 11，12都大于8，都位于8的右子树上。 12又是右子树的根，11小于12，是右子树的左孩子，右子树没有右孩子。 这个序列是合法的二叉搜索树的后序遍历序列 ， 推导结束。
再如：给定序列是：7 3 6 9 5 5是这棵二叉搜索树的根。 7大于5，所以，这棵树没有左子树。7 3 6 9都位于右子树上。 而右子树的序列中 3小于5，所以这个序列不是合法的二叉搜索树的后序遍历序列。 下边给出代码实现： //判断给定序列是否是BST的后序序列 template<typename T> class PostOrder { public: PostOrder(int a[],int n) :_size(n) { _a = new T[_size]; for(int i = 0; i < n; ++i) { _a[i] = a[i]; } } bool IsCurrentPostOrder() { return _IsCurrentPostOrder(_a,_size); } protected: bool _IsCurrentPostOrder(int a[],int len) { if( a == NULL ||len <= 0) return false; //对区间进行分段 int i = 0; for(i = 0; i < len - 1; ++i) { if(a[i] > a[len - 1]) break;//找到分割点 } for(int j = i; j < len - 1 ; ++j) { if(a[j] < a[len - 1])//遇到小于根节点的值，说明不是合法后序序列，返回 return false; } bool left = true; if(i > 0) left = _IsCurrentPostOrder(a,i); bool right = true; if(i < len - 1) right = _IsCurrentPostOrder(a+i,len-i-1); return left && right; } private: T* _a; int _size; }; void TestPostOrder() { //int a[] = {3,7,6,11,12,8}; int a[] = {7,4,6,5}; PostOrder<int> p(a,4); cout<<p.IsCurrentPostOrder()<<endl; }
