C語言二叉樹的遍歷方法怎么實現

# C語言二叉樹的遍歷方法怎么實現

二叉樹是數據結構中最基礎且重要的非線性結構，其遍歷操作是算法設計的核心內容。本文將詳細講解C語言中實現二叉樹前序、中序、后序及層次遍歷的完整方法，包含代碼實現、算法原理和實際應用場景。

## 一、二叉樹的基本結構與創建

### 1.1 二叉樹節點定義
```c
typedef struct TreeNode {
    int data;               // 節點數據域
    struct TreeNode *left;  // 左子樹指針
    struct TreeNode *right; // 右子樹指針
} TreeNode;

1.2 創建二叉樹節點

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("內存分配失敗\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

二、遞歸遍歷實現

2.1 前序遍歷（Preorder）

順序：根節點 → 左子樹 → 右子樹
應用場景：復制二叉樹、表達式樹的前綴表示

void preOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);  // 訪問根節點
    preOrderRecursive(root->left);
    preOrderRecursive(root->right);
}

2.2 中序遍歷（Inorder）

順序：左子樹 → 根節點 → 右子樹
應用場景：二叉搜索樹的有序輸出

void inOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    inOrderRecursive(root->left);
    printf("%d ", root->data);  // 訪問根節點
    inOrderRecursive(root->right);
}

2.3 后序遍歷（Postorder）

順序：左子樹 → 右子樹 → 根節點
應用場景：釋放二叉樹內存、表達式樹的后綴表示

void postOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    postOrderRecursive(root->left);
    postOrderRecursive(root->right);
    printf("%d ", root->data);  // 最后訪問根節點
}

三、非遞歸遍歷實現（使用棧）

3.1 前序遍歷非遞歸版

#include <stdlib.h>
#define MAX_SIZE 100

void preOrderIterative(TreeNode* root) {
    if (root == NULL) return;
    
    TreeNode* stack[MAX_SIZE];
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->data);
        
        // 右子節點先入棧（后出）
        if (node->right != NULL)
            stack[++top] = node->right;
        // 左子節點后入棧（先出）
        if (node->left != NULL)
            stack[++top] = node->left;
    }
}

3.2 中序遍歷非遞歸版

void inOrderIterative(TreeNode* root) {
    TreeNode* stack[MAX_SIZE];
    int top = -1;
    TreeNode* curr = root;
    
    while (curr != NULL || top >= 0) {
        // 遍歷到最左節點
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        curr = stack[top--];
        printf("%d ", curr->data);
        curr = curr->right;
    }
}

3.3 后序遍歷非遞歸版（雙棧法）

void postOrderIterative(TreeNode* root) {
    if (root == NULL) return;
    
    TreeNode* stack1[MAX_SIZE];
    TreeNode* stack2[MAX_SIZE];
    int top1 = -1, top2 = -1;
    
    stack1[++top1] = root;
    while (top1 >= 0) {
        TreeNode* node = stack1[top1--];
        stack2[++top2] = node;
        
        if (node->left != NULL)
            stack1[++top1] = node->left;
        if (node->right != NULL)
            stack1[++top1] = node->right;
    }
    
    // 輸出stack2中的逆序結果
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->data);
    }
}

四、層次遍歷（隊列實現）

特點：按層級從上到下、從左到右訪問
應用場景：計算樹的高度、查找某層節點

#include <stdbool.h>
#define QUEUE_SIZE 100

typedef struct {
    TreeNode* data[QUEUE_SIZE];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

bool enqueue(Queue* q, TreeNode* node) {
    if ((q->rear + 1) % QUEUE_SIZE == q->front)
        return false; // 隊列滿
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % QUEUE_SIZE;
    return true;
}

TreeNode* dequeue(Queue* q) {
    if (isEmpty(q)) return NULL;
    TreeNode* node = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    return node;
}

void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    while (!isEmpty(&q)) {
        TreeNode* node = dequeue(&q);
        printf("%d ", node->data);
        
        if (node->left != NULL)
            enqueue(&q, node->left);
        if (node->right != NULL)
            enqueue(&q, node->right);
    }
}

五、完整示例代碼

#include <stdio.h>
#include <stdlib.h>

// （此處插入前述所有代碼片段）

int main() {
    /* 構建測試二叉樹：
          1
        /   \
       2     3
      / \   /
     4   5 6
    */
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    
    printf("遞歸前序遍歷: ");
    preOrderRecursive(root);
    
    printf("\n非遞歸中序遍歷: ");
    inOrderIterative(root);
    
    printf("\n棧實現后序遍歷: ");
    postOrderIterative(root);
    
    printf("\n層次遍歷結果: ");
    levelOrder(root);
    
    return 0;
}

六、遍歷方法對比

七、常見問題解答

Q1：如何選擇遞歸還是非遞歸實現？
- 遞歸代碼簡潔但可能棧溢出
- 非遞歸效率更高，適合深度大的樹

Q2：Morris遍歷如何實現？
Morris遍歷通過修改樹結構實現O(1)空間復雜度：

// 中序Morris遍歷示例
void inOrderMorris(TreeNode* root) {
    TreeNode *curr = root, *pre;
    while (curr != NULL) {
        if (curr->left == NULL) {
            printf("%d ", curr->data);
            curr = curr->right;
        } else {
            pre = curr->left;
            while (pre->right != NULL && pre->right != curr)
                pre = pre->right;
                
            if (pre->right == NULL) {
                pre->right = curr;
                curr = curr->left;
            } else {
                pre->right = NULL;
                printf("%d ", curr->data);
                curr = curr->right;
            }
        }
    }
}

通過掌握這些遍歷方法，您將能夠高效處理二叉樹相關問題。建議讀者手動模擬各算法執行過程以加深理解。 “`

（全文約2350字，包含代碼示例、復雜度分析和實際應用說明）