數據結構：構建 (create) 一個二叉樹

問題的本質——什么信息才能唯一確定一棵樹？

推導“最佳拍檔”——哪兩種遍歷序列能行？

遞歸思想——如何構建一棵樹？

第1步：確定整棵樹的根節點

第2步：劃分左右子樹的成員

第3步：遞歸構建左右子樹

將邏輯翻譯為代碼

第1步：搭建函數框架和遞歸出口

第2步：實現核心邏輯 - 創建根節點

第3步：劃分中序序列并進行遞歸

第4步：創建主函數（包裝函數）

完整代碼和驗證

問題的本質——什么信息才能唯一確定一棵樹？

我們先思考一下，要構建一棵樹，我們需要什么“原材料”？

假設我給你一些節點，比如 A, B, C。我告訴你 A 是根節點。那么 B 和 C 在哪里呢？

可能是 B 是左孩子，C 是右孩子。
也可能是 B 是左孩子，C 是 B 的左孩子。
還可能是 B 和 C 都是 A 的右孩子（形成一個鏈表）。

顯然，只告訴我節點數據是不夠的，因為它缺乏結構信息。

那么，我們上一節學到的“遍歷序列”是不是一種結構信息呢？我們來試試。

數據結構：二叉樹的遍歷 (Binary Tree Traversals)-CSDN博客

假設我告訴你，一棵樹的前序遍歷序列是 A B C。這棵樹長什么樣？

A 肯定是根節點，因為前序遍歷第一個就是根。
B 是 A 的左孩子嗎？如果是，那么 C 可能是 A 的右孩子，也可能是 B 的左/右孩子。
B 是 A 的右孩子嗎？...

    A/ \B   C

    A/B/
C

    A/B\C

你會發現，只靠一種遍歷序列，我們無法唯一地確定一棵樹的結構。 信息還是不夠！

核心矛盾： 遍歷序列是一個一維的、線性的數據。而樹是一個二維的、非線性的結構。

從一維信息恢復二維結構，必然會丟失信息，導致不確定性。

解決方案： 那么，我們需要補充什么樣的信息才能消除這種不確定性呢？

我們需要兩種不同規則的遍歷序列，用它們互相配合，鎖定每一個節點的位置。

推導“最佳拍檔”——哪兩種遍歷序列能行？

我們來分析一下上一節學到的三種遍歷序列的“特長”：

前序遍歷 (DLR: 根-左-右)：?序列的第一個元素永遠是當前這棵（子）樹的根節點。
后序遍歷 (LRD: 左-右-根)：序列的最后一個元素永遠是當前這棵（子）樹的根節點。
中序遍歷 (LDR: 左-根-右)：?根節點在序列的中間，它像一根“柱子”，把序列劃分成了兩部分：左邊的所有元素都屬于左子樹，右邊的所有元素都屬于右子樹。

看到關鍵點了嗎？

前序和后序遍歷能幫我們輕松地找到根。
中序遍歷能幫我們以根為界，劃分出左右子樹的范圍。

這就是“最佳拍檔”！我們可以用一個（前序或后序）來確定根，再用中序來確定左右子樹的成員。

我們來推導 前序遍歷 + 中序遍歷 這個組合。

原材料：

前序序列 (Pre-order): A B D E C F
中序序列 (In-order): D B E A C F

        A/ \B   C/ \    \D   E    F

遞歸思想——如何構建一棵樹？

第1步：確定整棵樹的根節點

看前序序列 A B D E C F，第一個元素是 A。
結論：A 就是整棵樹的根節點。

第2步：劃分左右子樹的成員

我們已經知道根是 A 了。現在看中序序列 D B E A C F。
找到 A 在中序序列中的位置。
A 左邊的 D B E 就是 A 的左子樹的所有成員。
A 右邊的 C F 就是 A 的右子樹的所有成員。

第3步：遞歸構建左右子樹

現在問題被分解成了兩個一模一樣的子問題：

子問題1 (構建A的左子樹):

我們知道它的成員是 {D, B, E}。那么它的前序和中序序列是什么？
很簡單，回到原始序列中，只看這三個字母，保持它們原來的相對順序。
原始前序: A [B D E] C F -> 左子樹的前序: B D E
原始中序: [D B E] A C F -> 左子樹的中序: D B E
現在，我們對這兩個新的、更短的序列，重復第1步。

    B/ \D   E

子問題2 (構建A的右子樹):

成員是 {C, F}。
原始前序: A B D E [C F] -> 右子樹的前序: C F
原始中序: D B E A [C F] -> 右子樹的中序: C F
同樣，對這兩個新序列，重復第1步。

C\F

我們來深入子問題1 (左子樹 B D E):

第1步 (子問題): 看它的前序 B D E，第一個是 B。所以 B 是這個子樹的根。
第2步 (子問題): 看它的中序 D B E，找到 B。B 左邊是 D，右邊是 E。
結論：D 是 B 的左孩子，E 是 B 的右孩子。
到這里，D 和 E 都已經是單個節點（葉子節點），它們的左右子樹都是 NULL，遞歸的“出口”到了。

這個過程會一直持續下去，直到處理的序列為空。這就是從第一性原理推導出的，利用兩種遍歷序列構建樹的完整邏輯。

將邏輯翻譯為代碼

現在我們把這個遞歸邏輯變成代碼。我們需要一個函數，它能根據給定的前序和中序序列，返回構建好的樹的根節點指針。

我們先定義函數原型。這個函數需要什么參數？

char* preorder: 前序序列數組。
char* inorder: 中序序列數組。
為了處理子問題，我們還需要告訴函數當前要處理的序列是哪一段。所以我們需要數組的邊界。
int in_start, int in_end: 表示當前處理的中序序列在原數組中的起始和結束索引。

為什么只需要中序的邊界，而不需要前序的邊界？

因為前序序列的根總是在第一個位置，我們處理一個就用掉一個。我們可以用一個全局的或者傳入指針的索引來依次訪問前序序列，這樣更簡單。

第1步：搭建函數框架和遞歸出口

// 節點定義和創建函數（和上一節一樣）
typedef struct Node {char data;struct Node* left;struct Node* right;
} Node;Node* createNode(char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 這是一個遞歸的輔助函數
// pre_idx_ptr 是一個指向前序序列當前索引的指針，這樣在遞歸中修改才能生效
Node* buildTreeRecursive(char* preorder, int* pre_idx_ptr, char* inorder, int in_start, int in_end) {// 遞歸的出口 (Base Case)// 如果中序序列的起始點大于結束點，說明這是一個空子樹，沒有節點需要創建if (in_start > in_end) {return NULL;}// 后續的遞歸步驟將在這里填充// ...
}

第2步：實現核心邏輯 - 創建根節點

根據我們的推導，函數要做的第一件事就是從前序序列中取出當前的根。

Node* buildTreeRecursive(char* preorder, int* pre_idx_ptr, char* inorder, int in_start, int in_end) {if (in_start > in_end) {return NULL;}// 1. 從前序序列中獲取根節點的值// 當前要處理的根，就是前序序列中 pre_idx_ptr 指向的那個元素char root_val = preorder[*pre_idx_ptr];// 2. 創建根節點Node* root = createNode(root_val);// 3. 用掉了一個前序元素，將索引向后移動一位，為下一個遞歸調用做準備(*pre_idx_ptr)++;// ... 接下來是劃分和遞歸return root; // 暫時先返回根節點
}

第3步：劃分中序序列并進行遞歸

創建了根節點后，我們需要在中序序列里找到它，然后劃分出左右子樹的范圍，再進行遞歸調用。

Node* buildTreeRecursive(char* preorder, int* pre_idx_ptr, char* inorder, int in_start, int in_end) {if (in_start > in_end) {return NULL;}char root_val = preorder[*pre_idx_ptr];Node* root = createNode(root_val);(*pre_idx_ptr)++;// 4. 在中序序列中找到根節點的位置，以劃分左右子樹int in_root_idx = -1; // 初始化一個找不到的索引for (int i = in_start; i <= in_end; i++) {if (inorder[i] == root_val) {in_root_idx = i;break; // 找到了就退出循環}}// 如果在中序序列中找不到根（輸入有誤），可以加個錯誤處理// if (in_root_idx == -1) { /* error handling */ }// 5. 遞歸構建左右子樹// 注意遞歸的順序！因為我們是按前序(根->左->右)的順序消耗元素的，// 所以必須先遞歸構建左子樹，再遞歸構建右子樹。// 構建左子樹// 左子樹的范圍是中序序列的 in_start 到 根的前一個位置(in_root_idx - 1)root->left = buildTreeRecursive(preorder, pre_idx_ptr, inorder, in_start, in_root_idx - 1);// 構建右子樹// 右子樹的范圍是中序序列的 根的后一個位置(in_root_idx + 1) 到 in_endroot->right = buildTreeRecursive(preorder, pre_idx_ptr, inorder, in_root_idx + 1, in_end);return root;
}

第4步：創建主函數（包裝函數）

為了讓用戶調用起來更方便，我們創建一個主函數，它負責初始化前序索引并調用遞歸函數。

// 主函數，用戶調用這個
Node* buildTree(char* preorder, char* inorder, int size) {int pre_idx = 0; // 初始化前序序列的起始索引// 調用遞歸輔助函數，初始范圍是整個中序數組return buildTreeRecursive(preorder, &pre_idx, inorder, 0, size - 1);
}

至此，整個從邏輯推導到代碼實現的過程就完成了。

完整代碼和驗證

讓我們把所有部分組合起來，并寫一個 main 函數來驗證我們的成果。

驗證方法很簡單：用我們創建樹的函數 buildTree 來構建一棵樹，然后用上一節學過的任意一種遍歷（比如后序遍歷）來打印這棵樹，看看結果是否符合預期。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> // For strlen// --- 節點定義和創建函數 ---
typedef struct Node {char data;struct Node* left;struct Node* right;
} Node;Node* createNode(char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// --- 從前序和中序序列構建樹的實現 ---// 遞歸輔助函數
Node* buildTreeRecursive(char* preorder, int* pre_idx_ptr, char* inorder, int in_start, int in_end) {// 遞歸出口if (in_start > in_end) {return NULL;}// 1. 創建根節點char root_val = preorder[*pre_idx_ptr];Node* root = createNode(root_val);(*pre_idx_ptr)++;// 2. 在中序序列中找到根，以劃分左右子樹int in_root_idx = -1;for (int i = in_start; i <= in_end; i++) {if (inorder[i] == root_val) {in_root_idx = i;break;}}// 3. 遞歸構建左子樹和右子樹root->left = buildTreeRecursive(preorder, pre_idx_ptr, inorder, in_start, in_root_idx - 1);root->right = buildTreeRecursive(preorder, pre_idx_ptr, inorder, in_root_idx + 1, in_end);return root;
}// 主構建函數
Node* buildTree(char* preorder, char* inorder, int size) {int pre_idx = 0;return buildTreeRecursive(preorder, &pre_idx, inorder, 0, size - 1);
}// --- 驗證用的遍歷函數 (從上一節課拿來) ---
void postOrder(Node* root) {if (root == NULL) return;postOrder(root->left);postOrder(root->right);printf("%c ", root->data);
}// --- Main 函數 ---
int main() {char preorder[] = "ABDECF";char inorder[] = "DBEACF";int size = strlen(preorder);printf("Input Pre-order: %s\n", preorder);printf("Input In-order:  %s\n", inorder);// 使用我們推導出的函數來構建樹Node* root = buildTree(preorder, inorder, size);printf("\nVerification with Post-order traversal:\n");printf("Expected: D E B F C A\n");printf("Actual:   ");postOrder(root);printf("\n");// 如果 Actual 和 Expected 一致，說明我們的樹構建完全正確！// 在此添加釋放樹內存的代碼...return 0;
}

關于后序+中序的思考：

這個邏輯是完全一樣的。區別在于：