二叉樹節點與類設計

template <typename T>
struct BTNode {
    T data;
    BTNode* lchild;
    BTNode* rchild;
    BTNode(const T& val) : data(val), lchild(nullptr), rchild(nullptr) {}
};

template <typename T>
class BinaryTree {
    BTNode<T>* root;
    // 內部遞歸輔助函數...
public:
    BinaryTree();           // 從標準輸入構建（# 表示空）
    ~BinaryTree();          // 後序釋放

    // 遍歷接口
    void PreOrder()  const { PreOrder(root); }
    void InOrder()   const { InOrder(root); }
    void PostOrder() const { PostOrder(root); }
    void PreOrderIter()  const; // 非遞歸
    void InOrderIter()   const;
    void PostOrderIter() const;
    void LevelOrder()    const; // 層序

    // 查找與統計
    BTNode<T>* FindNode(const T& val) const;
    int Height() const;
    int NodeCount() const;
    void PrintLeaves() const;
    void PrintLeafDepths() const; // 葉子深度
    bool PrintAncestors(const T& val) const; // 祖先路徑
};

樹的構建與銷毀

template <typename T>
BTNode<T>* BinaryTree<T>::CreateTree() {
    T ch; std::cin >> ch;
    if (ch == '#') return nullptr;
    auto* node = new BTNode<T>(ch);
    node->lchild = CreateTree();
    node->rchild = CreateTree();
    return node;
}

template <typename T>
BinaryTree<T>::BinaryTree() : root(CreateTree()) {}

template <typename T>
void BinaryTree<T>::DestroyTree(BTNode<T>* node) {
    if (node) {
        DestroyTree(node->lchild);
        DestroyTree(node->rchild);
        delete node;
    }
}
BinaryTree<T>::~BinaryTree() { DestroyTree(root); }

遞歸遍歷（核心模式）

// 前序：根→左→右
void PreOrder(BTNode<T>* node) {
    if (node) {
        visit(node);
        PreOrder(node->lchild);
        PreOrder(node->rchild);
    }
}

// 中序：左→根→右
void InOrder(BTNode<T>* node) {
    if (node) {
        InOrder(node->lchild);
        visit(node);
        InOrder(node->rchild);
    }
}

// 後序：左→右→根
void PostOrder(BTNode<T>* node) {
    if (node) {
        PostOrder(node->lchild);
        PostOrder(node->rchild);
        visit(node);
    }
}

非遞歸遍歷（顯式棧）

前序：根右左入棧，出棧訪問

void PreOrderIter() const {
    std::stack<BTNode<T>*> st;
    if (root) st.push(root);
    while (!st.empty()) {
        auto* node = st.top(); st.pop();
        visit(node);
        if (node->rchild) st.push(node->rchild);
        if (node->lchild) st.push(node->lchild);
    }
}

中序：沿左鏈入棧，出棧訪問轉右

void InOrderIter() const {
    std::stack<BTNode<T>*> st;
    auto* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->lchild; }
        cur = st.top(); st.pop();
        visit(cur);
        cur = cur->rchild;
    }
}

後序：雙棧法或單棧+前驅標記

void PostOrderIter() const {
    std::stack<BTNode<T>*> st;
    BTNode<T>* cur = root;
    BTNode<T>* prev = nullptr;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->lchild; }
        cur = st.top();
        if (!cur->rchild || cur->rchild == prev) {
            visit(cur);
            st.pop();
            prev = cur;
            cur = nullptr;
        } else {
            cur = cur->rchild;
        }
    }
}

層序遍歷（隊列）

void LevelOrder() const {
    std::queue<BTNode<T>*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        auto* node = q.front(); q.pop();
        visit(node);
        if (node->lchild) q.push(node->lchild);
        if (node->rchild) q.push(node->rchild);
    }
}

查找與統計操作

BTNode<T>* FindNode(BTNode<T>* node, const T& val) const {
    if (!node) return nullptr;
    if (node->data == val) return node;
    if (auto* p = FindNode(node->lchild, val)) return p;
    return FindNode(node->rchild, val);
}

int Height(BTNode<T>* node) const {
    if (!node) return 0;
    return 1 + std::max(Height(node->lchild), Height(node->rchild));
}

int NodeCount(BTNode<T>* node) const {
    if (!node) return 0;
    return 1 + NodeCount(node->lchild) + NodeCount(node->rchild);
}

葉子節點與路徑深度

void PrintLeaves(BTNode<T>* node) const {
    if (node) {
        if (!node->lchild && !node->rchild) visit(node);
        PrintLeaves(node->lchild);
        PrintLeaves(node->rchild);
    }
}

void PrintLeafDepths(BTNode<T>* node, int depth) const {
    if (!node) return;
    if (!node->lchild && !node->rchild) {
        std::cout << node->data << ": " << depth << '\n';
    }
    PrintLeafDepths(node->lchild, depth+1);
    PrintLeafDepths(node->rchild, depth+1);
}

祖先路徑查詢

bool PrintAncestors(BTNode<T>* node, const T& val) const {
    if (!node) return false;
    if ((node->lchild && node->lchild->data == val) ||
        (node->rchild && node->rchild->data == val) ||
        PrintAncestors(node->lchild, val) ||
        PrintAncestors(node->rchild, val)) {
        visit(node); // 回溯時打印
        return true;
    }
    return false;
}

測試主程序

int main() {
    BinaryTree<char> tree; // 輸入示例：A B D # # E # # C # F # #
    std::cout << "PreOrder: "; tree.PreOrder();
    std::cout << "\nInOrder:  "; tree.InOrder();
    std::cout << "\nPostOrder:"; tree.PostOrder();
    std::cout << "\nLevelOrder:"; tree.LevelOrder();
    std::cout << "\nHeight: " << tree.Height();
    std::cout << "\nNodeCount: " << tree.NodeCount();
    std::cout << "\nLeaves: "; tree.PrintLeaves();
    std::cout << "\nLeafDepths:\n"; tree.PrintLeafDepths();
    std::cout << "Ancestors of E: "; tree.PrintAncestors('E');
    return 0;
}