判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果[折疊]

　　題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true，否則返回false。

　　例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：

　　8

　　/ \

　　6 10

　　/ \ / \

　　5 7 9 11

　　因此返回true。

　　如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。

　　分析：這是一道trilogy的筆試題，主要考查對(duì)二元查找樹的理解。

　　在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹的根結(jié)點(diǎn)。從頭開始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分;從第一個(gè)大于跟結(jié)點(diǎn)開始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。

　　參考代碼：

　　using namespace std;

　　///////////////////////////////////////////////////////////////////////

　　// Verify whether a squence of integers are the post order traversal

　　// of a binary search tree (BST)

　　// Input: squence - the squence of integers

　　// length - the length of squence

　　// Return: return ture if the squence is traversal result of a BST,

　　// otherwise, return false

　　///////////////////////////////////////////////////////////////////////

　　bool verifySquenceOfBST(int squence[], int length)

　　{

　　if(squence == NULL || length <= 0)

　　return false;

　　// root of a BST is at the end of post order traversal squence

　　int root = squence[length - 1];

　　// the nodes in left sub-tree are less than the root

　　int i = 0;

　　for(; i < length - 1; ++ i)

　　{

　　if(squence[i] > root)

　　break;

　　}

　　// the nodes in the right sub-tree are greater than the root

　　int j = i;

　　for(; j < length - 1; ++ j)

　　{

　　if(squence[j] < root)

　　return false;

　　}

　　// verify whether the left sub-tree is a BST

　　bool left = true;

　　if(i > 0)

　　left = verifySquenceOfBST(squence, i);

　　// verify whether the right sub-tree is a BST

　　bool right = true;

　　if(i < length - 1)

　　right = verifySquenceOfBST(squence + i, length - i - 1);

　　return (left && right);

　　}

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識(shí)點(diǎn)總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識(shí)點(diǎn)總結(jié)匯總