資料結構與演算法 C# 實作系列：廣義樹（一）─ 任意度數樹狀結構設計與子樹掛接

前言

廣義樹 允許每個節點擁有任意數量的子節點 (度數不固定)，是表達階層資料 (如檔案系統、組織架構) 的自然模型。本文設計 C# GeneralTree 類別，支援子樹掛接/卸離、索引存取與基本屬性。

類別結構

public class GeneralTree : Tree
{
    private object _key;
    private uint _degree;
    private ArrayList _subTrees = new ArrayList();

    public GeneralTree(object key)
    {
        _key = key;
        _degree = 0;
    }

    // 掛接子樹
    public virtual void AttachSubtree(GeneralTree sub)
    {
        _subTrees.Add(sub);
        _degree++;
    }

    // 卸離子樹
    public virtual GeneralTree DetachSubtree(GeneralTree sub)
    {
        _subTrees.Remove(sub);
        _degree--;
        return sub;
    }

    // 索引器存取子樹
    public override Tree this[uint index]
    {
        get
        {
            if (index >= _degree) throw new Exception("Index out of range");
            return (Tree)_subTrees[(int)index];
        }
        set => _subTrees[(int)index] = value;
    }

    // 基本屬性
    public override object Key => _key;
    public override uint Degree => _degree;
    public override bool IsEmpty() => false;
    public override bool IsLeaf() => _degree == 0;
}

設計要點

• ArrayList 替代連結串列：簡化子樹集合管理，自動處理動態擴容。
• Degree 同步：每次增減子樹即時更新 _degree，索引器邊界檢查才正確。
• 虛擬方法：Attach/Detach 標記 virtual，允許衍生類別 (如 N-ary Tree) 覆寫驗證邏輯。
• 基類 Tree：定義 Key、Degree、IsEmpty、IsLeaf、索引器等抽象/虛擬成員，建立統一介面。

使用範例

var root = new GeneralTree("Root");
var child1 = new GeneralTree("Child1");
var child2 = new GeneralTree("Child2");
root.AttachSubtree(child1);
root.AttachSubtree(child2);

Console.WriteLine(root.Degree); // 2
Console.WriteLine(root[0].Key); // Child1
root.DetachSubtree(child1);
Console.WriteLine(root.Degree); // 1

結語

廣義樹以 ArrayList 維護子樹集合，提供直觀的 Attach/Detach 與索引器操作，是實作複雜階層資料結構的靈活基礎。後續將補充遍歷器、比較邏輯與具體應用範例。