tree_bst.cpp

/*
 * ============================================================================
 *  Binary Search Tree (BST) — 完整實作
 *  File: tree_bst.cpp
 *
 *  BST 性質：左子樹所有值 < root < 右子樹所有值
 *
 *  涵蓋操作：
 *    1.  Insert（插入）
 *    2.  Search / Contains（搜尋）
 *    3.  FindMin / FindMax
 *    4.  Delete（刪除）— 三種情況
 *    5.  Inorder Traversal（中序遍歷 → 排序輸出）
 *    6.  Preorder / Postorder Traversal
 *    7.  Level-order Traversal（BFS）
 *    8.  Height / Size / IsBalanced
 *    9.  由 Preorder + Inorder 重建二元樹
 *   10.  印出樹的結構
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_bst tree_bst.cpp
 * ============================================================================
 */

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

/* ============================================================================
 *  節點結構
 * ============================================================================ */
struct BSTNode {
    int data;
    BSTNode* left;
    BSTNode* right;

    BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

/* ============================================================================
 *  1. Insert（插入）
 *
 *  遞迴地找到正確位置，新節點一定插入為 leaf。
 *  - 如果 key < node->data → 往左走
 *  - 如果 key > node->data → 往右走
 *  - 如果 key == node->data → 不插入（不允許重複）
 *
 *  時間：平均 O(log N)，最壞 O(N)（退化成 linked list）
 * ============================================================================ */
BSTNode* insert(BSTNode* node, int key) {
    // 找到空位置 → 建立新節點
    if (node == nullptr) {
        return new BSTNode(key);
    }

    if (key < node->data) {
        // key 比當前節點小 → 插入左子樹
        node->left = insert(node->left, key);
    } else if (key > node->data) {
        // key 比當前節點大 → 插入右子樹
        node->right = insert(node->right, key);
    }
    // key == node->data → 已存在，不插入

    return node;
}

/* ============================================================================
 *  2. Search / Contains（搜尋）
 *
 *  類似 binary search：
 *  - 比當前小 → 往左找
 *  - 比當前大 → 往右找
 *  - 相等 → 找到了
 *
 *  時間：平均 O(log N)，最壞 O(N)
 * ============================================================================ */
BSTNode* search(BSTNode* node, int key) {
    if (node == nullptr) return nullptr;      // 沒找到
    if (key == node->data) return node;       // 找到了
    if (key < node->data) return search(node->left, key);   // 往左
    return search(node->right, key);                         // 往右
}

// 回傳 bool 的版本
bool contains(BSTNode* node, int key) {
    return search(node, key) != nullptr;
}

/* ============================================================================
 *  3. FindMin / FindMax
 *
 *  FindMin: BST 中最小值 = 一路往左走到底
 *  FindMax: BST 中最大值 = 一路往右走到底
 *
 *  時間：O(h)，h = 樹的高度
 * ============================================================================ */
BSTNode* findMin(BSTNode* node) {
    if (node == nullptr) return nullptr;

    // 一路往左走到底
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

BSTNode* findMax(BSTNode* node) {
    if (node == nullptr) return nullptr;

    // 一路往右走到底
    while (node->right != nullptr) {
        node = node->right;
    }
    return node;
}

/* ============================================================================
 *  4. Delete（刪除）— 三種情況
 *
 *  Case 1: 要刪除的節點是 leaf（無子節點）→ 直接移除
 *  Case 2: 要刪除的節點有一個 child → 用 child 取代自己
 *  Case 3: 要刪除的節點有兩個 children →
 *           找中序後繼（右子樹的最小值），用其值取代自己，
 *           再遞迴刪除右子樹中的那個後繼節點
 *
 *  時間：平均 O(log N)，最壞 O(N)
 * ============================================================================ */
BSTNode* deleteNode(BSTNode* node, int key) {
    if (node == nullptr) return nullptr;  // 沒找到要刪的節點

    if (key < node->data) {
        // 要刪的在左子樹
        node->left = deleteNode(node->left, key);
    } else if (key > node->data) {
        // 要刪的在右子樹
        node->right = deleteNode(node->right, key);
    } else {
        // 找到了！node->data == key

        // Case 1 & 2: 沒有左子 或 沒有右子（包含 leaf 的情況）
        if (node->left == nullptr) {
            BSTNode* rightChild = node->right;
            delete node;
            return rightChild;  // 可能是 nullptr (leaf case)
        }
        if (node->right == nullptr) {
            BSTNode* leftChild = node->left;
            delete node;
            return leftChild;
        }

        // Case 3: 有兩個 children
        // 找右子樹的最小值（中序後繼）
        BSTNode* successor = findMin(node->right);

        // 用後繼的值取代自己
        node->data = successor->data;

        // 遞迴刪除右子樹中的那個後繼（它最多只有一個 right child）
        node->right = deleteNode(node->right, successor->data);
    }

    return node;
}

/* ============================================================================
 *  5. Inorder Traversal（中序遍歷）
 *
 *  順序：Left → Root → Right
 *  對 BST 來說，inorder 輸出的是排序後的遞增序列。
 * ============================================================================ */
void inorder(BSTNode* node) {
    if (node == nullptr) return;
    inorder(node->left);       // 先走左子樹
    cout << node->data << " "; // 訪問自己
    inorder(node->right);      // 再走右子樹
}

// 把 inorder 結果存到 vector
void inorderToVector(BSTNode* node, vector<int>& result) {
    if (node == nullptr) return;
    inorderToVector(node->left, result);
    result.push_back(node->data);
    inorderToVector(node->right, result);
}

/* ============================================================================
 *  6. Preorder / Postorder Traversal
 * ============================================================================ */
void preorder(BSTNode* node) {
    if (node == nullptr) return;
    cout << node->data << " "; // Root
    preorder(node->left);       // Left
    preorder(node->right);      // Right
}

void postorder(BSTNode* node) {
    if (node == nullptr) return;
    postorder(node->left);      // Left
    postorder(node->right);     // Right
    cout << node->data << " "; // Root
}

/* ============================================================================
 *  7. Level-order Traversal（BFS 層序遍歷）
 *
 *  使用 Queue，逐層由左到右輸出。
 * ============================================================================ */
void levelOrder(BSTNode* root) {
    if (root == nullptr) return;

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

    while (!q.empty()) {
        // 每次處理一層
        int levelSize = (int)q.size();
        for (int i = 0; i < levelSize; ++i) {
            BSTNode* cur = q.front();
            q.pop();

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

            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << "| ";  // 層與層之間的分隔
    }
    cout << endl;
}

/* ============================================================================
 *  8. Height / Size / IsBalanced
 * ============================================================================ */

// 高度：空樹 = -1，只有 root = 0
int height(BSTNode* node) {
    if (node == nullptr) return -1;
    return 1 + max(height(node->left), height(node->right));
}

// 節點總數
int size(BSTNode* node) {
    if (node == nullptr) return 0;
    return 1 + size(node->left) + size(node->right);
}

// 檢查是否為平衡二元樹（每個節點的左右高度差 ≤ 1）
// 回傳 -1 表示不平衡，否則回傳高度
int checkBalance(BSTNode* node) {
    if (node == nullptr) return 0;

    int leftH = checkBalance(node->left);
    if (leftH == -1) return -1;  // 左子樹已不平衡

    int rightH = checkBalance(node->right);
    if (rightH == -1) return -1; // 右子樹已不平衡

    if (abs(leftH - rightH) > 1) return -1;  // 當前節點不平衡

    return 1 + max(leftH, rightH);
}

bool isBalanced(BSTNode* root) {
    return checkBalance(root) != -1;
}

/* ============================================================================
 *  9. 由 Preorder + Inorder 重建二元樹
 *
 *  原理：
 *    - Preorder 的第一個元素 = root
 *    - 在 Inorder 中找到 root → 左邊 = 左子樹，右邊 = 右子樹
 *    - 遞迴處理
 * ============================================================================ */
BSTNode* buildTree(const vector<int>& preorder, int preStart, int preEnd,
                   const vector<int>& inorder,  int inStart,  int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return nullptr;

    // Preorder 的第一個元素 = 當前子樹的 root
    int rootVal = preorder[preStart];
    BSTNode* root = new BSTNode(rootVal);

    // 在 Inorder 中找到 root 的位置
    int rootIdx = inStart;
    while (rootIdx <= inEnd && inorder[rootIdx] != rootVal) {
        ++rootIdx;
    }

    // 左子樹的節點數
    int leftSize = rootIdx - inStart;

    // 遞迴建立左子樹和右子樹
    root->left  = buildTree(preorder, preStart + 1, preStart + leftSize,
                            inorder,  inStart,      rootIdx - 1);
    root->right = buildTree(preorder, preStart + leftSize + 1, preEnd,
                            inorder,  rootIdx + 1,             inEnd);

    return root;
}

/* ============================================================================
 *  10. 印出樹的結構（ASCII 視覺化）
 * ============================================================================ */
void printTree(BSTNode* node, const string& prefix = "", bool isLeft = true) {
    if (node == nullptr) return;

    // 先印右子樹（在上方）
    if (node->right) {
        printTree(node->right, prefix + (isLeft ? "│   " : "    "), false);
    }

    // 印自己
    cout << prefix;
    cout << (isLeft ? "└── " : "┌── ");
    cout << node->data << endl;

    // 再印左子樹（在下方）
    if (node->left) {
        printTree(node->left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

/* ============================================================================
 *  釋放記憶體
 * ============================================================================ */
void deleteTree(BSTNode* node) {
    if (node == nullptr) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

/* ============================================================================
 *  主程式
 * ============================================================================ */
int main() {
    cout << "============================================" << endl;
    cout << "  Binary Search Tree (BST) Complete Demo" << endl;
    cout << "============================================\n" << endl;

    BSTNode* root = nullptr;

    // ── 插入 ──
    cout << "--- Insert: 50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45 ---\n" << endl;
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};
    for (int k : keys) {
        root = insert(root, k);
    }

    /*
     * 建構出的 BST:
     *
     *              50
     *            /    \
     *          30      70
     *         /  \    /  \
     *       20   40  60   80
     *      / \  / \
     *    10 25 35 45
     */

    cout << "Tree structure:" << endl;
    printTree(root);
    cout << endl;

    // ── 遍歷 ──
    cout << "--- Traversals ---\n" << endl;

    cout << "Inorder  (sorted): ";
    inorder(root);
    cout << endl;

    cout << "Preorder:          ";
    preorder(root);
    cout << endl;

    cout << "Postorder:         ";
    postorder(root);
    cout << endl;

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

    // ── 搜尋 ──
    cout << "--- Search ---\n" << endl;

    cout << "contains(40) = " << (contains(root, 40) ? "true" : "false") << endl;
    cout << "contains(99) = " << (contains(root, 99) ? "true" : "false") << endl;
    cout << endl;

    // ── FindMin / FindMax ──
    cout << "--- FindMin / FindMax ---\n" << endl;
    cout << "Min = " << findMin(root)->data << endl;
    cout << "Max = " << findMax(root)->data << endl;
    cout << endl;

    // ── 統計 ──
    cout << "--- Statistics ---\n" << endl;
    cout << "Height:     " << height(root) << endl;
    cout << "Size:       " << size(root) << endl;
    cout << "IsBalanced: " << (isBalanced(root) ? "true" : "false") << endl;
    cout << endl;

    // ── 刪除 ──
    cout << "--- Delete ---\n" << endl;

    // Case 1: 刪除 leaf (10)
    cout << "Delete 10 (leaf):" << endl;
    root = deleteNode(root, 10);
    printTree(root);
    cout << endl;

    // Case 2: 刪除有一個 child 的節點 (20, 只有 right child 25)
    cout << "Delete 20 (one child):" << endl;
    root = deleteNode(root, 20);
    printTree(root);
    cout << endl;

    // Case 3: 刪除有兩個 children 的節點 (30)
    cout << "Delete 30 (two children):" << endl;
    root = deleteNode(root, 30);
    printTree(root);
    cout << endl;

    cout << "Inorder after deletions: ";
    inorder(root);
    cout << endl;
    cout << endl;

    // ── 退化情況示範 ──
    cout << "--- Skewed BST (degenerate case) ---\n" << endl;

    BSTNode* skewed = nullptr;
    // 按順序插入 → 退化成 linked list
    for (int i = 1; i <= 5; ++i) {
        skewed = insert(skewed, i);
    }
    cout << "Insert 1,2,3,4,5 in order:" << endl;
    printTree(skewed);
    cout << "Height = " << height(skewed) << " (worst case: N-1 = 4)" << endl;
    cout << "IsBalanced = " << (isBalanced(skewed) ? "true" : "false") << endl;
    cout << endl;
    deleteTree(skewed);

    // ── 由 Preorder + Inorder 重建 ──
    cout << "--- Rebuild from Preorder + Inorder ---\n" << endl;

    vector<int> pre = {1, 2, 4, 5, 3, 6};
    vector<int> ino = {4, 2, 5, 1, 3, 6};

    cout << "Preorder: ";
    for (int x : pre) cout << x << " ";
    cout << endl;
    cout << "Inorder:  ";
    for (int x : ino) cout << x << " ";
    cout << endl;

    BSTNode* rebuilt = buildTree(pre, 0, (int)pre.size() - 1,
                                 ino, 0, (int)ino.size() - 1);
    cout << "\nRebuilt tree:" << endl;
    printTree(rebuilt);

    cout << "Verify inorder: ";
    inorder(rebuilt);
    cout << endl;

    // 清理
    deleteTree(root);
    deleteTree(rebuilt);

    return 0;
}