1.問題定義

對于二叉樹的3中遍歷方法，相信大家耳熟能詳。那么如果我們知道了其中的兩種遍歷結果，能不能把一棵二叉樹重新建立起來？給定一棵二叉樹，假設每個節點都用唯一的字符來表示，沒有重復。結構如下：

struct _Node {_Node* Lchild;_Node* Rchild;char data; };

假設已有了前序遍歷和中序遍歷的結果，希望通過一個算法來重建這棵樹。

前序遍歷：a, b, d, c, e, f??? 顯然a是根節點

中序遍歷：d, b, a, e, c, f??? a前面的d, b是a的左子樹中的節點，a后面的e, c, f是a右子樹中的節點

重建后的圖如下：

2.分析與解法

不難發現a是前序遍歷中的第一個節點，把中序遍歷分成前后兩個部分，分別是a的左右子樹中的節點，長度分別為2,3，前序遍歷中的第二個節點b又把d, b分成了前后兩部分(后一部分沒有節點)，分別是b的左右子樹中的節點，長度分別為1,0……這樣遞歸下去，能找出每一個節點的左右子樹中的節點，當節點沒有左右子樹的時候即為葉節點，當一個節點它的左右子樹長度為1時，此節點的左右子樹就一個節點，為0時，表示此節點沒有左子樹或右子樹。編程之美上的算法如下：

#include <iostream>using namespace std; #define TREELEN 6 struct _Node {_Node* Lchild;_Node* Rchild;char data; }; void ReBulid(char* pPreOrder,//當前節點的前序遍歷結果 char* pInOrder, //當前節點的中序遍歷結果int nTreeLen, //當前節點為根的樹長度_Node**pRoot) //當前根節點 {if (pPreOrder == NULL || pInOrder == NULL)//邊界檢查{return;}_Node* pTemp = new _Node;pTemp->data = *pPreOrder;pTemp->Lchild = NULL;pTemp->Rchild = NULL;if (*pRoot == NULL)//如果當前根節點為空，把前序遍歷的第一個節點賦給它{*pRoot = pTemp;}if (nTreeLen == 1)//如果當前樹長度為1，表明此節點是最后一個節點{return;}//尋找子樹長度char* pOrgInOrder = pInOrder;char* pLeftEnd = pInOrder;int nTempLen = 0;//找到左子樹的結尾while(*pPreOrder != *pLeftEnd){if (pPreOrder == NULL || pLeftEnd == NULL){return;}nTempLen++;if (nTempLen > nTreeLen){break;}pLeftEnd++;}//尋找左子樹長度int nLeftLen = 0;nLeftLen = (int)(pLeftEnd - pOrgInOrder);//尋找右子樹長度int nRightLen = 0;nRightLen = nTreeLen - nLeftLen - 1;//重建左子樹if (nLeftLen > 0){ReBulid(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->Lchild));}//重建右子樹if (nRightLen > 0){ReBulid(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1, nRightLen, &((*pRoot)->Rchild));} }; void main() {char PerO[6] = {'a', 'b', 'd', 'c', 'e', 'f'};char InO[6] = {'d', 'b', 'a', 'e', 'c', 'f'};_Node * pRoot = NULL;ReBulid(PerO, InO, TREELEN, &pRoot); }

這里可能引起內存泄露。_Node * pRoot = NULL;并沒有釋放空間，詳見：http://blog.csdn.net/flyinghearts/archive/2010/05/31/5638123.aspx

另這里給幾個內存思考問題(有點膚淺，見笑)：

void GetMemory(char *p) {p = (char *)malloc(100); } void Test(void) {char *str = NULL;GetMemory(str);strcpy(str, "hello world");printf(str); } 請問運行Test 函數會有什么樣的結果？ 答：程序崩潰。 因為 GetMemory 并不能傳遞動態內存，Test 函數中的 str 一直都是 NULL。 strcpy(str, "hello world");將使程序崩潰 char *GetMemory(void) {char p[] = "hello world";return p; } void Test(void) {char *str = NULL;str = GetMemory();printf(str); } 請問運行Test 函數會有什么樣的結果？ 答：可能是亂碼。 因為 GetMemory 返回的是指向“棧內存”的指針，該指針的地址不是 NULL，但其原 現的內容已經被清除，新內容不可知。 void GetMemory2(char **p, int num) {*p = (char *)malloc(num); } void Test(void) {char *str = NULL;GetMemory(&str, 100);strcpy(str, "hello");printf(str); } 請問運行Test 函數會有什么樣的結果？ 答： （1）能夠輸出hello （2）內存泄漏 void Test(void) {char *str = (char *) malloc(100);strcpy(str, “hello”);free(str);if(str != NULL){strcpy(str, “world”);printf(str);} } 請問運行Test 函數會有什么樣的結果？ 答：篡改動態內存區的內容，后果難以預 料，非常危險。因為 free(str);之后，str 成為野指針，if(str != NULL)語句不起作用。 //關于重建二叉樹的方法，還有很多。我覺得有一種方法也可行：假如前序遍歷的為a,b,c，那么中序遍歷的結果只有5種：c,b,a | a,b,c | b,c,a | c,b,a | b,a,c。 當然前提是前序遍歷的頭兩個節點，即a,b不能有共同的父親。用a,b,c找出中序遍歷中a,b,c分別的位置，就對應出a,b,c的樹型結構。 還有一點，a是根節點，這沒問題，一定要用a先找完a的左子樹，然后再用a找完a的右子樹，如前序：a,b,d,e,x,g,c,k,h,z , 中序為：d,b,x,g,e, (a) ,k,c,h,z 要這樣操作：先a,b,d,e,x,g ->(a,b,d) ->(b,d,e)->(d,e,x)->(e,x,g)->(x,g)。然后a,c,k,h,z->(a,c,k)->(,c,k,h)->(k,h,z)->(h,z)。 *還要注意：(a,b,d)中前兩個節點a,b不能有共同的父親，否則這步操作不作！那么最后只有兩個節點怎么辦呢？ 如：(x,g)，如果在中序遍歷中g在a的前面則說明g是a的右孩子，即中序中x,g反序了。否則g為a的左孩子。

轉載于:https://www.cnblogs.com/cluster/archive/2011/05/29/2062127.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Programe_Of_Beauty :3.9 重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。