資料結構與演算法 C# 實作系列：廣義樹（二）─ 節點屬性、比較與樹狀操作

前言

承接上篇廣義樹結構定義，本文補充 GeneralTree 節點的屬性實作、空樹/葉子判斷、物件相等比較與 Equals/GetHashCode 覆寫細節。

核心屬性實作

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

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

    public override object Key => _key;

    public override uint Degree => _degree;

    // public override uint Height => _height; // 暫不實作

    public override bool IsEmpty() => false; // GeneralTree 實例化即非空

    public override bool IsLeaf() => _degree == 0; // 無子樹即為葉子

    public void AttachSubtree(GeneralTree sub)
    {
        _subTrees.Add(sub);
        _degree++;
    }

    public 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;
    }
}

Equals 與 GetHashCode 正確覆寫

public override bool Equals(object obj)
{
    if (!base.Equals(obj)) return false; // 基類型別檢查

    var other = (GeneralTree)obj; // 安全轉型

    // 比較參考型別成員 (子樹列表)
    if (!Object.Equals(_subTrees, other._subTrees)) return false;

    // 比較值型別成員 (Key, Degree 等)
    // 此處假設 Key 已正確實作 Equals
    return true;
}

public override int GetHashCode()
{
    // 結合 Key 與子樹雜湊碼
    int hash = 17;
    hash = hash * 23 + (_key?.GetHashCode() ?? 0);
    hash = hash * 23 + _subTrees.GetHashCode();
    return hash;
}

設計重點提醒

• IsEmpty() 恆為 false：廣義樹節點本身即存在，空樹概念通常由 null 參考或專用 EmptyTree 單例表示。
• Degree 同步更新：Attach/Detach 必須同步修改 _degree，確保索引器邊界檢查正確。
• Equals 深度比較：遞迴比較子樹結構時需注意循環參考，必要時引入 HashSet 追蹤已比較節點。

結語

廣義樹節點屬性與比較邏輯的正確實作，是樹狀演算法 (遍歷、搜尋、序列化) 穩定運作的基石。下篇將展示遍歷器與列舉器的實作細節。