二叉樹四種遍歷算法完整實現（遞歸與非遞歸）

節點定義

struct LNode {
    char data;
    LNode *lchild;
    LNode *rchild;
};

遞歸實現（前序、中序、後序）

// 前序：根 → 左 → 右
void preorder(LNode *root) {
    if (root) {
        cout << root->data << " ";
        preorder(root->lchild);
        preorder(root->rchild);
    }
}

// 中序：左 → 根 → 右
void inorder(LNode *root) {
    if (root) {
        inorder(root->lchild);
        cout << root->data << " ";
        inorder(root->rchild);
    }
}

// 後序：左 → 右 → 根
void postorder(LNode *root) {
    if (root) {
        postorder(root->lchild);
        postorder(root->rchild);
        cout << root->data << " ";
    }
}

層次遍歷（廣度優先，非遞歸）

void levelorder(LNode *root) {
    queue q;
    q.push(root);
    while (!q.empty()) {
        LNode *p = q.front(); q.pop();
        cout << p->data << " ";
        if (p->lchild) q.push(p->lchild);
        if (p->rchild) q.push(p->rchild);
    }
}

主函數：從輸入構建樹並測試

程序讀取字符串構建二叉樹（具體構建邏輯見原碼），依次調用四種遍歷並輸出結果。

本文出自「菜鳥的進階之路」博客，轉載請保留出處：原文鏈接