tree_general.cpp

/*
 * ============================================================================
 *  一般樹 (General Tree) — 左子右兄弟表示法 + DFS/BFS 遍歷
 *  File: tree_general.cpp
 *
 *  一般樹的每個節點可以有任意數量的 children。
 *  本程式使用「左子右兄弟 (Left-Child Right-Sibling)」表示法：
 *    - firstChild:  指向第一個 child
 *    - nextSibling: 指向右邊的兄弟
 *  這樣每個節點只需兩個指標，就能表示任意分支度的樹。
 *
 *  涵蓋：
 *    1. 建構一般樹
 *    2. Preorder（前序）遍歷
 *    3. Postorder（後序）遍歷
 *    4. Level-order（層序）遍歷 — 使用 Queue
 *    5. 計算高度、節點數、葉節點數
 *    6. 印出樹的結構（縮排顯示）
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_general tree_general.cpp
 * ============================================================================
 */

#include <iostream>
#include <queue>
#include <string>

using namespace std;

/*
 * 左子右兄弟表示法的節點結構
 *
 * 原始樹:            左子右兄弟:
 *       A                  A
 *     / | \               /
 *    B  C  D             B → C → D
 *   / \    |            /         /
 *  E   F   G          E → F     G
 *  |                  /
 *  H                 H
 */
struct TreeNode {
    int data;                // 節點存的資料
    TreeNode* firstChild;    // 指向第一個 child（最左的 child）
    TreeNode* nextSibling;   // 指向右邊的兄弟

    // 建構子：初始化資料，指標設為 nullptr
    TreeNode(int val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};

/*
 * 幫某個 parent 新增一個 child。
 * 新 child 會加到 children list 的最後面。
 */
void addChild(TreeNode* parent, TreeNode* child) {
    if (parent->firstChild == nullptr) {
        // parent 還沒有任何 child → 直接設為 firstChild
        parent->firstChild = child;
    } else {
        // 找到 children list 的最後一個 sibling
        TreeNode* cur = parent->firstChild;
        while (cur->nextSibling != nullptr) {
            cur = cur->nextSibling;
        }
        // 把新 child 接到最後
        cur->nextSibling = child;
    }
}

/* ============================================================================
 *  Preorder（前序）遍歷：先訪問 root，再依序遞迴訪問所有 children
 *  順序：Root → Child1 → Child2 → ... → ChildK
 * ============================================================================ */
void preorder(TreeNode* node, int depth = 0) {
    if (node == nullptr) return;

    // 印出目前節點（用縮排表示深度）
    for (int i = 0; i < depth; ++i) cout << "  ";
    cout << node->data << endl;

    // 遞迴訪問所有 children（透過 firstChild → nextSibling 鏈）
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        preorder(child, depth + 1);
        child = child->nextSibling;
    }
}

/* ============================================================================
 *  Postorder（後序）遍歷：先遞迴訪問所有 children，最後訪問 root
 *  順序：Child1 → Child2 → ... → ChildK → Root
 * ============================================================================ */
void postorder(TreeNode* node) {
    if (node == nullptr) return;

    // 先遞迴處理所有 children
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        postorder(child);
        child = child->nextSibling;
    }

    // 最後訪問自己
    cout << node->data << " ";
}

/* ============================================================================
 *  Level-order（層序）遍歷：使用 Queue，逐層由左到右
 *  注意：需要把「同一個 parent 的所有 children」都入隊
 * ============================================================================ */
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();

        cout << cur->data << " ";

        // 把 cur 的所有 children 入隊
        TreeNode* child = cur->firstChild;
        while (child != nullptr) {
            q.push(child);
            child = child->nextSibling;
        }
    }
    cout << endl;
}

/* ============================================================================
 *  計算樹的高度 (height)
 *  高度 = 從 root 到最深 leaf 的邊數
 *  空樹高度定義為 -1
 * ============================================================================ */
int height(TreeNode* node) {
    if (node == nullptr) return -1;

    int maxChildHeight = -1;

    // 找所有 children 中最高的
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        int h = height(child);
        if (h > maxChildHeight) {
            maxChildHeight = h;
        }
        child = child->nextSibling;
    }

    // 自己的高度 = 最高 child 的高度 + 1
    return maxChildHeight + 1;
}

/* ============================================================================
 *  計算節點總數
 * ============================================================================ */
int countNodes(TreeNode* node) {
    if (node == nullptr) return 0;

    int count = 1;  // 算自己

    // 加上所有 children 的節點數
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        count += countNodes(child);
        child = child->nextSibling;
    }

    return count;
}

/* ============================================================================
 *  計算葉節點數（leaf = 沒有 child 的節點）
 * ============================================================================ */
int countLeaves(TreeNode* node) {
    if (node == nullptr) return 0;

    // 如果沒有 child → 是 leaf
    if (node->firstChild == nullptr) return 1;

    int leaves = 0;
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        leaves += countLeaves(child);
        child = child->nextSibling;
    }

    return leaves;
}

/* ============================================================================
 *  印出樹的結構（樹狀縮排 + 連線）
 * ============================================================================ */
void printTree(TreeNode* node, const string& prefix = "", bool isLast = true) {
    if (node == nullptr) return;

    cout << prefix;
    cout << (isLast ? "└── " : "├── ");
    cout << node->data << endl;

    // 收集所有 children 到 vector 以便知道誰是最後一個
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        TreeNode* next = child->nextSibling;
        bool last = (next == nullptr);
        printTree(child, prefix + (isLast ? "    " : "│   "), last);
        child = next;
    }
}

/* ============================================================================
 *  釋放整棵樹的記憶體
 * ============================================================================ */
void deleteTree(TreeNode* node) {
    if (node == nullptr) return;

    // 先刪除所有 children
    TreeNode* child = node->firstChild;
    while (child != nullptr) {
        TreeNode* next = child->nextSibling;
        deleteTree(child);
        child = next;
    }

    delete node;
}

/* ============================================================================
 *  主程式 — 建構範例樹並示範所有操作
 * ============================================================================ */
int main() {
    cout << "============================================" << endl;
    cout << "  General Tree (Left-Child Right-Sibling)" << endl;
    cout << "============================================\n" << endl;

    /*
     * 建構以下樹:
     *
     *          1
     *        / | \
     *       2  3  4
     *      / \    |
     *     5   6   7
     *     |
     *     8
     */
    TreeNode* root = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);
    TreeNode* n6 = new TreeNode(6);
    TreeNode* n7 = new TreeNode(7);
    TreeNode* n8 = new TreeNode(8);

    // 1 的 children: 2, 3, 4
    addChild(root, n2);
    addChild(root, n3);
    addChild(root, n4);

    // 2 的 children: 5, 6
    addChild(n2, n5);
    addChild(n2, n6);

    // 4 的 child: 7
    addChild(n4, n7);

    // 5 的 child: 8
    addChild(n5, n8);

    // 印出樹結構
    cout << "--- Tree Structure ---" << endl;
    printTree(root);
    cout << endl;

    // Preorder
    cout << "--- Preorder Traversal ---" << endl;
    preorder(root);
    cout << endl;

    // Postorder
    cout << "--- Postorder Traversal ---" << endl;
    postorder(root);
    cout << "\n" << endl;

    // Level-order
    cout << "--- Level-order Traversal ---" << endl;
    levelOrder(root);
    cout << endl;

    // 統計
    cout << "--- Statistics ---" << endl;
    cout << "Height:      " << height(root) << endl;
    cout << "Total nodes: " << countNodes(root) << endl;
    cout << "Leaf nodes:  " << countLeaves(root) << endl;

    // 清理記憶體
    deleteTree(root);

    return 0;
}