C/C++ 實作二叉搜尋樹的建立與前序遍歷

C/C++ 實作二叉搜尋樹的建立與前序遍歷

本文提供一個完整的 C/C++ 範例，示範如何從零開始建立一棵二叉搜尋樹（BST），並透過前序遍歷輸出節點資料。程式碼包含節點定義、插入邏輯、樹的建立以及遍歷輸出，適合初學者理解 BST 的核心操作。

核心資料結構

首先定義樹節點結構，包含資料欄位與左右子節點指標：

struct BiNode {
    int data;
    BiNode *lchild;
    BiNode *rchild;
};

節點插入函式

InsertBST 遞迴地將新值插入正確位置，維持 BST 性質：左子樹值小於根節點，右子樹值大於根節點。

BiNode* InsertBST(BiNode* root, int data) {
    if (root == NULL) {
        root = new BiNode;
        root->data = data;
        root->lchild = root->rchild = NULL;
    }
    if (root->data > data)
        root->lchild = InsertBST(root->lchild, data);
    else if (root->data < data)
        root->rchild = InsertBST(root->rchild, data);
    return root;
}

建立完整樹結構

CreateBST 遍歷輸入陣列，依序呼叫插入函式建構整棵樹。

BiNode* CreateBST(BiNode* root, int data[], int n) {
    for (int i = 0; i < n; i++)
        root = InsertBST(root, data[i]);
    return root;
}

前序遍歷輸出

PrintBST 採用「根→左→右」順序遞迴列印節點值，方便驗證樹的結構。

void PrintBST(BiNode* root) {
    if (root != NULL) {
        cout << root->data << "->";
        PrintBST(root->lchild);
        PrintBST(root->rchild);
    }
}

主程式測試

使用包含 10 個整數的陣列建立樹，並輸出前序遍歷結果。

int main() {
    BiNode* root = NULL;
    int data[10] = {5,9,4,7,3,6,1,8,2,10};
    root = CreateBST(root, data, 10);
    PrintBST(root);
    cout << endl;
    return 0;
}

執行結果

程式在 VS2010 環境下編譯執行，輸出前序遍歷序列：

此範例清晰展示了 BST 的基本操作流程，是理解樹形資料結構的良好起點。