C# 實作二元搜尋樹演算法完整指南

簡介

樹為非線性結構，二元樹限制每節點最多兩個子節點，二元搜尋樹（BST）進一步規定左子樹所有節點值小於父節點，右子樹大於父節點，利於高效搜尋。

節點定義

public class Node {
    public int Data;
    public Node Left;
    public Node Right;
    public void DisplayData() { Console.Write(Data + " "); }
}

建立二元搜尋樹（插入操作）

插入邏輯：小於目前節點往左，大於往右，遞迴至葉節點插入。

public void Insert(int data) {
    Node newNode = new Node { Data = data };
    if (Root == null) { Root = newNode; return; }
    Node current = Root, parent;
    while (true) {
        parent = current;
        if (data < current.Data) {
            current = current.Left;
            if (current == null) { parent.Left = newNode; break; }
        } else {
            current = current.Right;
            if (current == null) { parent.Right = newNode; break; }
        }
    }
}

樹的遍歷

• 中序：左 → 根 → 右（遞增輸出）
• 先序：根 → 左 → 右
• 後序：左 → 右 → 根

public void InOrder(Node root) {
    if (root != null) { InOrder(root.Left); root.DisplayData(); InOrder(root.Right); }
}
public void PreOrder(Node root) {
    if (root != null) { root.DisplayData(); PreOrder(root.Left); PreOrder(root.Right); }
}
public void PostOrder(Node root) {
    if (root != null) { PostOrder(root.Left); PostOrder(root.Right); root.DisplayData(); }
}

尋找最大/最小值

BST 有序特性使查找極值極簡單：最左葉節點為最小值，最右葉節點為最大值。

public void FindMax() {
    Node current = Root;
    while (current.Right != null) current = current.Right;
    Console.WriteLine("\n最大節點: " + current.Data);
}
public void FindMin() {
    Node current = Root;
    while (current.Left != null) current = current.Left;
    Console.WriteLine("\n最小節點: " + current.Data);
}

搜尋節點

public Node Search(int key) {
    Node current = Root;
    while (current != null) {
        if (key < current.Data) current = current.Left;
        else if (key > current.Data) current = current.Right;
        else return current;
    }
    return null;
}

刪除節點（最複雜操作）

需處理四種情況：

1. 葉節點：直接移除。
2. 僅有左子節點：以左子節點取代。
3. 僅有右子節點：以右子節點取代。
4. 雙子節點：找左子樹最大值（或右子樹最小值）取代，再刪除該取代節點。

public Node Delete(int key) {
    Node parent = Root, current = Root;
    // 尋找目標節點與父節點
    while (current != null) {
        if (key < current.Data) { if (current.Left == null) break; parent = current; current = current.Left; }
        else if (key > current.Data) { if (current.Right == null) break; parent = current; current = current.Right; }
        else break;
    }
    if (current == null) return null; // 未找到

    // 四種情況處理
    if (current.Left == null && current.Right == null) { /* 葉節點 */ }
    else if (current.Left != null && current.Right == null) { /* 僅左子節點 */ }
    else if (current.Left == null && current.Right != null) { /* 僅右子節點 */ }
    else { /* 雙子節點：採用左子樹最大值取代 */ }
    return current;
}

完整刪除程式碼請參考原文。

測試驗證

BinarySearchTree bst = new BinarySearchTree();
bst.Insert(5); bst.Insert(7); bst.Insert(1); bst.Insert(12); bst.Insert(32);
bst.Insert(15); bst.Insert(22); bst.Insert(2); bst.Insert(6); bst.Insert(24);
bst.Insert(17); bst.Insert(14);

Console.Write("\n中序遍歷: "); bst.InOrder(bst.Root);
Console.Write("\n先序遍歷: "); bst.PreOrder(bst.Root);
Console.Write("\n後序遍歷: "); bst.PostOrder(bst.Root);

bst.FindMax(); bst.FindMin();
Node found = bst.Search(15);
Console.WriteLine("\n搜尋節點 15: " + found.Data);

bst.Delete(24);
Console.Write("\n刪除 24 後中序: "); bst.InOrder(bst.Root);
bst.Delete(5); // 刪除根節點
Console.Write("\n刪除根節點 5 後中序: "); bst.InOrder(bst.Root);

總結

二元搜尋樹結合有序特性與樹狀結構，提供高效搜尋、插入、刪除與遍歷操作，是資料結構核心基礎。