C# 資料結構與演算法實作系列：樹的遍歷與訪問者模式

樹的定義與基本性質

樹 是一個有限且非空的節點集合 T，滿足：

1. 存在唯一根節點 r。
2. 其餘節點可分為 n (n ≥ 0) 個互不相交的子集 T1, T2, ..., Tn，每個子集本身也是一棵樹 (遞迴定義)。

常見術語：度、葉節點、高度、層級等此處不贅述。

核心操作：遍歷

遍歷分為 深度優先 (DFS) 與 廣度優先 (BFS)。DFS 又細分為前序、中序、後序。本實作採用 訪問者模式 將遍歷邏輯與節點操作解耦。

介面設計

// 基礎訪問介面
public interface IVisitor { void Visit(object obj); }

// 支援前/後序的擴充介面
public interface IPrePostVisitor : IVisitor
{
    void PreVisit(object obj);
    void PostVisit(object obj);
}

抽象樹基類 Tree

public abstract class Tree : IEnumerable, IComparable
{
    protected Queue _enumQueue = new Queue(); // 僅用於 IEnumerable 實作
    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 abstract bool IsEmpty();
    public abstract bool IsLeaf();

    public void SetTraversalType(TraversalType type) { _traversalType = type; }

    // 深度優先遍歷 (中序核心，透過 IPrePostVisitor 控制前/中/後序)
    public virtual void DepthFirstTraversal(IPrePostVisitor visitor)
    {
        if (IsEmpty()) return;

        visitor.PreVisit(Key);

        if (Degree >= 1)
        {
            for (uint i = 0; i < Degree - 1; i++)
                this[i].DepthFirstTraversal(visitor); // 左子樹 (中序語意)

            this[Degree - 1].DepthFirstTraversal(visitor); // 右子樹
        }

        visitor.PostVisit(Key);
    }

    // 廣度優先遍歷
    public virtual void BreadthFirstTraversal(IVisitor visitor)
    {
        var queue = new Queue();
        if (!IsEmpty()) queue.Enqueue(this);

        while (queue.Count > 0)
        {
            Tree node = (Tree)queue.Dequeue();
            visitor.Visit(node.Key);
            for (uint i = 0; i < node.Degree; i++)
            {
                Tree child = node[i];
                if (!child.IsEmpty()) queue.Enqueue(child);
            }
        }
    }

    // IEnumerable 實作：依 _traversalType 選擇遍歷策略
    public IEnumerator GetEnumerator()
    {
        _enumQueue.Clear();
        var enumVisitor = new EnumVisitor(_enumQueue);

        switch (_traversalType)
        {
            case TraversalType.Breadth: BreadthFirstTraversal(enumVisitor); break;
            case TraversalType.PreDepth: DepthFirstTraversal(new PreOrder(enumVisitor)); break;
            case TraversalType.InDepth: DepthFirstTraversal(new InOrder(enumVisitor)); break;
            case TraversalType.PostDepth: DepthFirstTraversal(new PostOrder(enumVisitor)); break;
            default: Console.WriteLine("警告：請先呼叫 SetTraversalType 設定遍歷類型"); break;
        }
        return _enumQueue.GetEnumerator();
    }

    // 內部訪問者實作
    protected class EnumVisitor : IVisitor { /* 將 Key 入隊列 */ }
    private class PreOrder : IPrePostVisitor { /* PreVisit 呼叫 visitor.Visit */ }
    private class InOrder : IPrePostVisitor { /* Visit 呼叫 visitor.Visit */ }
    private class PostOrder : IPrePostVisitor { /* PostVisit 呼叫 visitor.Visit */ }

    // 物件相等性比較 (依 Key 與 Degree)
    public override bool Equals(object obj) { /* ... */ }
    public static bool operator ==(Tree a, Tree b) { return Equals(a, b); }
    public static bool operator !=(Tree a, Tree b) { return !(a == b); }

    public virtual int CompareTo(object obj) { return 0; } // 留待衍生類實作
}

設計亮點

• 策略模式：TraversalType 枚舉 + SetTraversalType 讓同一樹實例動態切換遍歷行為。
• 訪問者模式：IVisitor/IPrePostVisitor 將節點操作 (如列印、計算、序列化) 與遍歷控制流分離，符合開閉原則。
• 遞迴與迭代並存：DFS 用遞迴 (簡潔)，BFS 用佇列 (避免堆疊溢位)。
• IEnumerable 整合：樹可直接用於 foreach，語法糖提升易用性。

擴充建議

1. 實作具體節點類別 (如 BinaryTreeNode, GeneralTreeNode) 繼承 Tree，提供建構子與子節點管理。
2. 補充 Height、Depth 屬性並快取計算結果。
3. 提供非遞迴 DFS 實作 (顯式堆疊) 以應對極深樹結構。