資料結構與演算法 C# 實作系列：演示篇（三）─ 訪問者模式實作樹遍歷與列舉器

前言

承接上篇，本文展示如何使用 訪問者模式 將遍歷邏輯 (前序/中序/後序/廣度) 與節點操作解耦，並實作 IEnumerable 讓樹支援 foreach。

一、訪問者介面定義

public interface IVisitor
{
    void Visit(object obj);
}

public interface IPrePostVisitor : IVisitor
{
    void PreVisit(object obj);
    void PostVisit(object obj);
}

二、具體訪問者：對應遍歷順序

public class PreOrder : IPrePostVisitor
{
    private IVisitor _visitor;
    public PreOrder(IVisitor v) => _visitor = v;
    public void PreVisit(object o) => _visitor.Visit(o);
    public void Visit(object o) { } // 不使用
    public void PostVisit(object o) { }
}

public class InOrder : IPrePostVisitor
{
    private IVisitor _visitor;
    public InOrder(IVisitor v) => _visitor = v;
    public void PreVisit(object o) { }
    public void Visit(object o) => _visitor.Visit(o); // 中序：訪問節點
    public void PostVisit(object o) { }
}

public class PostOrder : IPrePostVisitor
{
    private IVisitor _visitor;
    public PostOrder(IVisitor v) => _visitor = v;
    public void PreVisit(object o) { }
    public void Visit(object o) { }
    public void PostVisit(object o) => _visitor.Visit(o); // 後序：訪問節點
}

三、列舉器訪問者：收集結果到 Queue

internal class EnumVisitor : IVisitor
{
    private Queue _queue;
    public EnumVisitor(Queue q) => _queue = q;
    public void Visit(object o) => _queue.Enqueue(o);
}

四、Tree 類別實作 IEnumerable

public class Tree : IEnumerable
{
    private TraversalType _traversalType;
    private Queue _keyQueue = new Queue();

    public void SetTraversalType(TraversalType t) => _traversalType = t;

    public IEnumerator GetEnumerator()
    {
        var visitor = new EnumVisitor(_keyQueue);
        switch (_traversalType)
        {
            case TraversalType.Breadth:
                BreadthFirstTraversal(visitor);
                break;
            case TraversalType.PreDepth:
                DepthFirstTraversal(new PreOrder(visitor));
                break;
            case TraversalType.InDepth:
                DepthFirstTraversal(new InOrder(visitor));
                break;
            case TraversalType.PostDepth:
                DepthFirstTraversal(new PostOrder(visitor));
                break;
            default:
                Console.WriteLine("請先呼叫 SetTraversalType");
                break;
        }
        return _keyQueue.GetEnumerator();
    }

    // 遞迴遍歷實作略...
    private void BreadthFirstTraversal(IVisitor v) { /* 使用 Queue 逐層 */ }
    private void DepthFirstTraversal(IPrePostVisitor v) { /* 遞迴 Pre/Visit/Post */ }
}

五、使用範例

var tree = BuildSampleTree();
tree.SetTraversalType(TraversalType.InDepth);
foreach (var node in tree)
    Console.WriteLine(node); // 自動依中序輸出

結語

訪問者模式將「如何遍歷」與「遍歷時做什麼」分離，配合 IEnumerable 介面，讓樹結構同時支援多種遍歷策略與標準 foreach 列舉，極大提升複用性與擴充性。