輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則返回true，否則返回false。假設(shè)輸入數(shù)組的任意兩個(gè)數(shù)組都互不相同。

成都創(chuàng)新互聯(lián)-專(zhuān)業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性?xún)r(jià)比館陶網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式館陶網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋館陶地區(qū)。費(fèi)用合理售后完善，十年實(shí)體公司更值得信賴(lài)。

    二叉搜索樹(shù)的特點(diǎn)就是每個(gè)結(jié)點(diǎn)的左子樹(shù)的值都比自身的值小，而右子樹(shù)的值都比自身值要大。比如如上的二叉搜索樹(shù)后序遍歷的結(jié)果就是{5,7,6,9,11,10,8}，但是題意并不是給出一棵二叉搜索樹(shù)讓判斷數(shù)組是否為后序遍歷序列，而是只有一組數(shù)據(jù)讓判斷是否為某個(gè)二叉搜索樹(shù)的后序遍歷結(jié)果，因此之能依據(jù)二叉搜索樹(shù)后序遍歷結(jié)果的特點(diǎn)來(lái)進(jìn)行分析判斷；

    就拿上面的結(jié)果來(lái)說(shuō)，可以發(fā)現(xiàn)，因?yàn)槭呛笮虮闅v，因此數(shù)組的最后一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn)，而因?yàn)槭嵌嫠阉鳂?shù)，所以根結(jié)點(diǎn)前面的部分可以分為兩塊，一塊都比根結(jié)點(diǎn)的值要小，因此為其左結(jié)點(diǎn)，而另一部分都比根結(jié)點(diǎn)的值要大，因此是根結(jié)點(diǎn)的右子樹(shù)部分，然后可以用遞歸來(lái)再對(duì)左右子樹(shù)部分進(jìn)行判斷，如果不滿(mǎn)足上述的任一部分則返回false.....(balabalabala.......其實(shí)本來(lái)不是這個(gè)樣子的，可是都要插入結(jié)果圖片發(fā)布了突然網(wǎng)卡了，再恢復(fù)就發(fā)現(xiàn)什么都沒(méi)有了系統(tǒng)沒(méi)有保存，又重新開(kāi)始寫(xiě)，不說(shuō)了心好累5555555555555555很晚了要洗洗睡了 ，直奔程序吧 T_T)

程序設(shè)計(jì)如下：

#include 
using namespace std;

bool JudgeIsPostOrderOfBST(int *arr, size_t start, size_t end)//名字臭長(zhǎng)臭長(zhǎng)的 -_-
{
    bool ret = false;
    if((arr != NULL) && (start < end))//參數(shù)條件判斷
    {
        size_t i = 0;
        for(; i < end; ++i)//在數(shù)組中查找第一個(gè)比根結(jié)點(diǎn)大的數(shù)，進(jìn)行分塊
        {
            if(arr[i] > arr[end])
                break;
        }

        size_t j = i;
        for(; j < end; ++j)//對(duì)分塊之后的部分進(jìn)行判斷，如不滿(mǎn)足直接返回false
        {
            if(arr[j] < arr[end])
                return ret;
        }
        if(j == end)//如果滿(mǎn)足條件則當(dāng)前狀態(tài)為true，接著就需要進(jìn)行遞歸判斷左右子樹(shù)部分
            ret = true;

        if(start < i-1)
            ret = JudgeIsPostOrderOfBST(arr, start, i-1);
        if(i < end-1)
            ret = JudgeIsPostOrderOfBST(arr, i, end-1);
    }
    return ret;
}

int main()
{
    int arr1[] = {5,7,6,9,11,10,8};
    int arr2[] = {4,5,2,6,7,3,1};

    cout<
運(yùn)行程序：
《完》
            
            
                        

            網(wǎng)頁(yè)標(biāo)題：二叉搜索樹(shù)的后序遍歷序列——24            

            URL鏈接：http://weahome.cn/article/pgoojo.html