今天解決了人生導(dǎo)師留給我的第一個問題——通過前序遍歷和中序遍歷序列，求解后序遍歷序列。
思路：D&C
對于二叉樹，前/后序遍歷+中序遍歷是可以求解二叉樹的結(jié)構(gòu)的。原理很簡單，上圖（圖片均來自學(xué)堂在線 “30240184X 數(shù)據(jù)結(jié)構(gòu)” 課程視頻）：
對于這樣的一棵樹，前序遍歷的結(jié)構(gòu)必然是根+左子樹+右子樹，而中序遍歷是左子樹+根+右子樹。在
inorder中查找r（前序遍歷的第一），就可以將inorder劃分成左子樹部分和右子樹部分，在preorder中也根據(jù)長度找到了劃分位置。在postorder中，r肯定在結(jié)尾，左右子樹部分的位置也可以確定。確定好了各部分的位置，遞歸到左右子樹就可以。
用數(shù)組
void preIn_Post(int pre[], int in[], int post[], int len){
if(len == 1) {
post[0] = pre[0];
return;
}
int v = pre[0], i;
for(i = 1; i < len; i ++) if(v == in[i]) break;
post[len - 1] = v;
preIn_Post(pre + 1, in, post, i); //左子樹
preIn_Post(pre + 1 + i, in + 1 + i, post + i, len - 1 - i); //右子樹
}
只要看清楚下一步遞歸的三個數(shù)組位置和長度就好了。
重建二叉樹
不過我還想把二叉樹建出來，感覺只有一部之遙了。
void preIn_rebuild(int pre[], int in[], int len, BinNode* pos, int mode){
if(len == 0) {return;}
int v = pre[0], i = 0;
if(len > 1) for(i = 1; i < len; i ++) if(v == in[i]) break;
if(mode == AS_LC){
pos = insertAsLc(v, pos);
}else{
pos = insertAsRc(v, pos);
}
preIn_rebuild(pre + 1, in, i, pos, AS_LC); //左子樹
preIn_rebuild(pre + 1 + i, in + 1 + i, len - 1 - i, pos, AS_RC); //右子樹
}
和前面差不多，只不過要在上次生長的位置上添加孩子。（寫著寫著發(fā)現(xiàn)，之前寫的insertAsxx都忘了把新插入節(jié)點(diǎn)的指針return回來，修了一下。）
但這段代碼的問題是，只能在已有一個節(jié)點(diǎn)的樹上開始。本來我希望將空樹也納入進(jìn)來，多一個mode為AS_ROOT的條件，結(jié)果發(fā)現(xiàn)，盡管insertAsRoot里面?zhèn)鞯氖侵羔樀囊?，這段里面?zhèn)鞯氖侵羔?，所以?code>main拿到的樹根指針會被丟掉，新的樹根指針我找不到?？墒沁@段代碼也并不方便改為傳指針的引用。算了，第一步特殊對待吧。
下面還是用那個滿二叉樹，測試下：
int pre[50] = {0, 1, 3, 7, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14},
in[50] = {7, 3, 8, 1, 9, 4, 10, 0, 11, 5, 12, 2, 13, 6, 14},
post[50] = {0}, travLen = 15;
BinNode* re_root = NULL;
int v = pre[0], i = 0;
for(i = 1; i < travLen; i ++) if(v == in[i]) break;
insertAsRoot(v, re_root);
preIn_rebuild(pre + 1, in, i, re_root, AS_LC); //左子樹
preIn_rebuild(pre + 1 + i, in + 1 + i, travLen - 1 - i, re_root, AS_RC); //右子樹
travPostR(re_root); printf("\n");
travLevel(re_root); printf("\n");
用遍歷函數(shù)走一遍，沒問題。
其它
后序遍歷+中序遍歷生成前序遍歷幾乎完全相同。
前序 + 后序在一般情況下是不能確定一棵樹的。然而在完全二叉樹（出度為0或2）的情況下可以，貼圖：
preorder中左子樹部分一定是以l節(jié)點(diǎn)起始的，可以在postorder中找到l，也就是左右子樹的劃分位置；同理，postorder中右子樹部分一定是以r節(jié)點(diǎn)結(jié)束的，可以在postorder中找到左右子樹的劃分位置。遞歸就可以了。
如果是一般的二叉樹，如果這里左或右節(jié)點(diǎn)為空，那僅有的一段子樹部分，沒辦法搞清楚是左子樹還是右子樹。
感謝學(xué)堂在線這個課程竟然講了這么多。要是人生導(dǎo)師知道我是從視頻里看來的而不是自己死摳出來的，估計要?dú)獾檬帐拔伊恕?/p>
溜。
