2022考研計(jì)算機(jī)復(fù)習(xí)備考：依據(jù)先序后序生成二叉樹

2022考研計(jì)算機(jī)復(fù)習(xí)備考：依據(jù)先序后序生成二叉樹

對于考研專業(yè)而言，計(jì)算機(jī)一定算的上是熱門專業(yè)之一，也就表示計(jì)算機(jī)專業(yè)考研競爭是非常激烈的，想要更好的復(fù)習(xí)準(zhǔn)備計(jì)算機(jī)，對于知識點(diǎn)的練習(xí)是日常復(fù)習(xí)必不可少的。小編整理“2022考研計(jì)算機(jī)復(fù)習(xí)備考：依據(jù)先序后序生成二叉樹”內(nèi)容，希望可以給備戰(zhàn)2022考研考生提供參考~~

題目：已知二叉樹的先序遍歷序列和后序遍歷序列，試編寫生成該二叉樹的算法。

思路：先序 pre = DLR，后序 post = LRD，D表示根結(jié)點(diǎn)，L表示左子樹，R為右子樹。

從先序出發(fā)：取先序的第一個(gè)元素pre[0]做根，第二個(gè)元素pre[1]做左子樹的根(不確定也可能是右子樹的根，但是先序是根左右，先認(rèn)為它是左子樹的根)，然后去后序序列找pre[1]這個(gè)元素的下標(biāo)位置i，在后序序列里，下標(biāo)i到最后一個(gè)元素間沒有元素，說明這個(gè)樹只有一個(gè)子樹(可以是左子樹或右子樹);有元素，那這段序列是右子樹，下標(biāo)i往前到post[0]是左子樹。對左子樹和右子樹分別再這樣分出根、左子樹和右子樹。

算法：

def func(pre[],post[]) {

int index = 0;

if(length(pre) == 0) return NULL;

node = BinTnode(pre[0]);

if(length(pre) == 1) return node;

while (pre[1] != post[index]){

index=index+1;

}

node->left = func(pre[1:index+1],post[0:index]);

node->right = func(pre[index+2:n],post[index+1:n-1]);

return node;

}

思考：或者從后序出發(fā)：取后序最后一個(gè)元素做根，倒數(shù)第二個(gè)元素是右子樹的根A，去先序序列里找這個(gè)A的下標(biāo)，這個(gè)下標(biāo)往后的先序序列是右子樹，往前到pre[1]是左子樹，其他思路同上。

以上就是小編整理的“2022考研計(jì)算機(jī)復(fù)習(xí)備考：依據(jù)先序后序生成二叉樹”相關(guān)內(nèi)容，希望對大家有所幫助，預(yù)祝大家能考上理想的院校。