C# 實作廣義樹 (General Tree) 資料結構 - 進階篇

前言

廣義樹與二元樹最大不同在於「節點度數不固定」，每個節點可擁有 0 到 N 個子節點。本文延續基礎篇，完善 GeneralTree 類別的核心功能：索引器、相等比較、葉節點判斷等。

完整類別實作

using System;
using System.Collections;

namespace DataStructure
{
    public class GeneralTree : Tree
    {
        private object _key;
        private uint _degree;
        private readonly ArrayList _treeList = new ArrayList();

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

        // 核心屬性
        public override object Key => _key;
        public override uint Degree => _degree;

        // 空樹判斷：廣義樹一旦建立即非空
        public override bool IsEmpty() => false;

        // 葉節點判斷：度數為 0 即為葉節點
        public override bool IsLeaf() => _degree == 0;

        // 索引器：存取子樹
        public override Tree this[uint index]
        {
            get
            {
                if (index >= _degree) throw new ArgumentOutOfRangeException(nameof(index));
                return (Tree)_treeList[(int)index];
            }
            set => _treeList[(int)index] = value;
        }

        // 掛載子樹
        public virtual void AttachSubtree(GeneralTree subtree)
        {
            _treeList.Add(subtree);
            _degree++;
        }

        // 卸載子樹
        public virtual GeneralTree DetachSubtree(GeneralTree subtree)
        {
            _treeList.Remove(subtree);
            _degree--;
            return subtree;
        }

        // 相等比較：比較 Key、Degree 以及子樹結構
        public override bool Equals(object obj)
        {
            if (!base.Equals(obj)) return false;
            var other = (GeneralTree)obj;
            return Equals(_key, other._key) && 
                   _degree == other._degree && 
                   Equals(_treeList, other._treeList);
        }

        public override int GetHashCode() => HashCode.Combine(_key, _degree, _treeList);
    }
}

關鍵設計說明

1. ArrayList 儲存子樹：動態陣列支援任意數量子節點，索引器提供 O(1) 存取。
2. Degree 動態維護：每次掛載/卸載子樹自動更新度數，確保一致性。
3. IsEmpty 固定回傳 false：廣義樹建構子要求傳入 Key，因此永不為空 (空樹概念由 N-ary Tree 的空節點實現)。
4. Equals 深度比較：遞迴比較子樹結構，適用於樹形結構的單元測試驗證。

使用範例

var root = new GeneralTree("Root");
var child1 = new GeneralTree("Child1");
var child2 = new GeneralTree("Child2");
var grandChild = new GeneralTree("GrandChild");

child1.AttachSubtree(grandChild);
root.AttachSubtree(child1);
root.AttachSubtree(child2);

// 遍歷
Console.WriteLine($"Root: {root.Key}, Degree: {root.Degree}");
for (uint i = 0; i < root.Degree; i++)
{
    var child = (GeneralTree)root[i];
    Console.WriteLine($"  Child: {child.Key}, IsLeaf: {child.IsLeaf()}");
}

效能考量

• 記憶體：ArrayList 為非泛型，涉及裝箱/拆箱。.NET 2.0+ 建議改用 List<GeneralTree>。
• 遞迴深度：深度遍歷 (如 Equals、序列化) 可能導致堆疊溢位，極深樹結構建議改用迭代器模式。

結語

廣義樹是表達層級資料 (如組織架構、檔案系統、AST) 的自然模型。掌握其 C# 實作細節，有助於建構靈活的樹形資料處理元件。