您好,登錄后才能下訂單哦!
輸入一個(gè)整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則返回true,否則返回false。假設(shè)輸入數(shù)組的任意兩個(gè)數(shù)組都互不相同。
二叉搜索樹的特點(diǎn)就是每個(gè)結(jié)點(diǎn)的左子樹的值都比自身的值小,而右子樹的值都比自身值要大。比如如上的二叉搜索樹后序遍歷的結(jié)果就是{5,7,6,9,11,10,8},但是題意并不是給出一棵二叉搜索樹讓判斷數(shù)組是否為后序遍歷序列,而是只有一組數(shù)據(jù)讓判斷是否為某個(gè)二叉搜索樹的后序遍歷結(jié)果,因此之能依據(jù)二叉搜索樹后序遍歷結(jié)果的特點(diǎn)來進(jìn)行分析判斷;
就拿上面的結(jié)果來說,可以發(fā)現(xiàn),因?yàn)槭呛笮虮闅v,因此數(shù)組的最后一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn),而因?yàn)槭嵌嫠阉鳂?,所以根結(jié)點(diǎn)前面的部分可以分為兩塊,一塊都比根結(jié)點(diǎn)的值要小,因此為其左結(jié)點(diǎn),而另一部分都比根結(jié)點(diǎn)的值要大,因此是根結(jié)點(diǎn)的右子樹部分,然后可以用遞歸來再對(duì)左右子樹部分進(jìn)行判斷,如果不滿足上述的任一部分則返回false.....(balabalabala.......其實(shí)本來不是這個(gè)樣子的,可是都要插入結(jié)果圖片發(fā)布了突然網(wǎng)卡了,再恢復(fù)就發(fā)現(xiàn)什么都沒有了系統(tǒng)沒有保存,又重新開始寫,不說了心好累5555555555555555很晚了要洗洗睡了 ,直奔程序吧 T_T)
程序設(shè)計(jì)如下:
#include <iostream> 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)行判斷,如不滿足直接返回false { if(arr[j] < arr[end]) return ret; } if(j == end)//如果滿足條件則當(dāng)前狀態(tài)為true,接著就需要進(jìn)行遞歸判斷左右子樹部分 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; }
運(yùn)行程序:
《完》
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。