二叉樹建立與遍歷 C++ 模板實現

目標

實現二叉樹的建立（先序輸入，'#' 代表空節點）及三種遞歸遍歷：前序、中序、後序。

類設計

• TreeNode<T>：數據域、左右子節點指針
• BinaryTree<T>：根節點、建樹、三種遍歷的公有/私有方法對

核心代碼

template <class T>
class TreeNode {
    friend class BinaryTree<T>;
    T data;
    TreeNode *lchild, *rchild;
};

template <class T>
class BinaryTree {
    TreeNode<T> *root;
public:
    BinaryTree() : root(nullptr) {}

    void create() { create(root); }
    void preorder()  { cout << "Preorder: ";  preorder(root);  cout << endl; }
    void inorder()   { cout << "Inorder: ";   inorder(root);   cout << endl; }
    void postorder() { cout << "Postorder: "; postorder(root); cout << endl; }

private:
    void create(TreeNode<T> *&node) {
        char ch; cin >> ch;
        if (ch == '#') { node = nullptr; return; }
        node = new TreeNode<T>();
        node->data = ch;
        create(node->lchild);
        create(node->rchild);
    }

    void preorder(TreeNode<T> *node) {
        if (!node) return;
        cout << node->data << ' ';
        preorder(node->lchild);
        preorder(node->rchild);
    }
    void inorder(TreeNode<T> *node) {
        if (!node) return;
        inorder(node->lchild);
        cout << node->data << ' ';
        inorder(node->rchild);
    }
    void postorder(TreeNode<T> *node) {
        if (!node) return;
        postorder(node->lchild);
        postorder(node->rchild);
        cout << node->data << ' ';
    }
};

測試主程序

int main() {
    BinaryTree<char> tree;
    // 輸入範例: A B D # # E # # C # F # #
    tree.create();
    tree.preorder();  // A B D E C F
    tree.inorder();   // D B E A C F
    tree.postorder(); // D E B F C A
    return 0;
}

遍歷順序總結

模板優勢

• 類型通用，支援任意數據類型
• 封裝良好，內部節點不暴露
• 引用參數 TreeNode*& 實現指針修改