C# 樹結構核心架構設計（一）：抽象基底類別與訪問者模式遍歷框架

樹的數學定義與核心屬性

• 有限非空節點集合
• 唯一根節點 r
• 其餘節點分割為 n 棵子樹（n ≥ 0）
• 關鍵屬性：度（子樹數）、葉節點（度為 0）、高度

抽象基底類別 Tree 設計

public abstract class Tree : IEnumerable, IComparable {
    protected Queue keyQueue = new Queue();        // 遍歷暫存佇列
    protected TraversalType traversalType = TraversalType.Breadth;
    public enum TraversalType { Breadth=1, PreDepth=2, InDepth=3, PostDepth=4 }
    public abstract Tree this[uint index] { get; set; }
    public abstract object Key { get; }
    public abstract uint Degree { get; }
    public void SetTraversalType(TraversalType type) { traversalType = type; }
    public abstract bool IsEmpty();
    public abstract bool IsLeaf();
    // ... IEnumerable, IComparable, Equals, ==/!= 實作見後續篇章
}

訪問者模式支援多樣遍歷

定義介面分離「演算法」與「資料結構」：

public interface IVisitor { void Visit(object obj); }
public interface IPrePostVisitor : IVisitor {
    void PreVisit(object obj);   // 前序動作
    void PostVisit(object obj);  // 後序動作
}

深度優先遍歷範本方法

public virtual void DepthFirstTraversal(IPrePostVisitor visitor) {
    if (!IsEmpty()) {
        visitor.PreVisit(Key);
        if (Degree >= 1) {
            if (Degree >= 2) {
                for (uint i = 0; i < Degree - 1; i++)
                    this[i].DepthFirstTraversal(visitor); // 遞迴左子樹
                // visitor.Visit(Key); // 中序位置
            }
            this[Degree - 1].DepthFirstTraversal(visitor); // 最右子樹
        }
        visitor.PostVisit(Key);
    }
}

透過不同 IPrePostVisitor 實作（PreOrder、InOrder、PostOrder）即可在同一遞迴骨架下實現三種深度遍歷。

廣度優先遍歷

public virtual void BreadthFirstTraversal(IVisitor visitor) {
    if (!IsEmpty()) {
        Queue q = new Queue(); q.Enqueue(this);
        while (q.Count > 0) {
            Tree node = (Tree)q.Dequeue();
            visitor.Visit(node.Key);
            for (uint i = 0; i < node.Degree; i++)
                q.Enqueue(node[i]);
        }
    }
}

迭代器整合

GetEnumerator() 依 traversalType 選擇遍歷策略，配合 EnumVisitor 將訪問節點入佇列，最後回傳佇列的列舉器，實現 foreach 無縫遍歷。