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

創(chuàng)新互聯(lián)公司專注于綠春網(wǎng)站建設服務及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供綠春營銷型網(wǎng)站建設，綠春網(wǎng)站制作、綠春網(wǎng)頁設計、綠春網(wǎng)站官網(wǎng)定制、微信平臺小程序開發(fā)服務，打造綠春網(wǎng)絡公司原創(chuàng)品牌,更為您提供綠春網(wǎng)站排名全網(wǎng)營銷落地服務。

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

  就拿上面的結果來說，可以發(fā)現(xiàn)，因為是后序遍歷，因此數(shù)組的最后一個結點一定是根結點，而因為是二叉搜索樹，所以根結點前面的部分可以分為兩塊，一塊都比根結點的值要小，因此為其左結點，而另一部分都比根結點的值要大，因此是根結點的右子樹部分，然后可以用遞歸來再對左右子樹部分進行判斷，如果不滿足上述的任一部分則返回false.....(balabalabala.......其實本來不是這個樣子的，可是都要插入結果圖片發(fā)布了突然網(wǎng)卡了，再恢復就發(fā)現(xiàn)什么都沒有了系統(tǒng)沒有保存，又重新開始寫，不說了心好累5555555555555555很晚了要洗洗睡了 ，直奔程序吧 T_T)

程序設計如下：

#include <iostream>
using namespace std;

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

        size_t j = i;
        for(; j < end; ++j)//對分塊之后的部分進行判斷，如不滿足直接返回false
        {
            if(arr[j] < arr[end])
                return ret;
        }
        if(j == end)//如果滿足條件則當前狀態(tài)為true，接著就需要進行遞歸判斷左右子樹部分
            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<<JudgeIsPostOrderOfBST(arr1, 0, sizeof(arr1)/sizeof(arr1[0]-1))<<endl;
    cout<<JudgeIsPostOrderOfBST(arr2, 0, sizeof(arr2)/sizeof(arr2[0]-1))<<endl;
    return 0;
}

運行程序：

《完》

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

本文標題：二叉搜索樹的后序遍歷序列——24-創(chuàng)新互聯(lián)
當前URL：http://www.chinadenli.net/article34/dchpse.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、靜態(tài)網(wǎng)站、商城網(wǎng)站、企業(yè)建站、域名注冊、網(wǎng)站內鏈

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)