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

　　計算機類專業(yè)長期以來被認為薪資高、就業(yè)面廣，如今競爭日趨激烈。想要更好的復(fù)習(xí)準(zhǔn)備計算機，對于知識點的練習(xí)是日常復(fù)習(xí)必不可少的。小編整理2021考研計算機復(fù)習(xí)備考知識：依據(jù)先序后序生成二叉樹，希望對大家的復(fù)習(xí)能有所幫助。

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

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

　　從先序出發(fā)：取先序的第一個元素pre[0]做根，第二個元素pre[1]做左子樹的根(不確定也可能是右子樹的根，但是先序是根左右，先認為它是左子樹的根)，然后去后序序列找pre[1]這個元素的下標(biāo)位置i，在后序序列里，下標(biāo)i到最后一個元素間沒有元素，說明這個樹只有一個子樹(可以是左子樹或右子樹);有元素，那這段序列是右子樹，下標(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ā)：取后序最后一個元素做根，倒數(shù)第二個元素是右子樹的根A，去先序序列里找這個A的下標(biāo)，這個下標(biāo)往后的先序序列是右子樹，往前到pre[1]是左子樹，其他思路同上。

　　(注：本文來自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系刪除)