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

前言

廣義樹允許節點擁有任意數量的子節點，是表達階層式資料的基礎結構。本文建立 GeneralTree 基礎架構，包含建構子、子樹管理與索引器存取。

核心類別定義

using System;
using System.Collections;

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

        // 建構子：指定節點鍵值
        public GeneralTree(object key)
        {
            _key = key;
            _degree = 0;
        }

        // 掛載子樹：度數自動遞增
        public virtual void AttachSubtree(GeneralTree subtree)
        {
            _treeList.Add(subtree);
            _degree++;
        }

        // 卸載子樹：度數自動遞減
        public virtual GeneralTree DetachSubtree(GeneralTree subtree)
        {
            _treeList.Remove(subtree);
            _degree--;
            return subtree;
        }

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

設計重點

1. 繼承抽象 Tree 基類：統一樹形結構介面 (Key、Degree、IsEmpty、IsLeaf、索引器)。
2. ArrayList 彈性儲存：無需預先指定容量，動態增減子節點。
3. Degree 與子樹同步：掛載/卸載操作自動維護度數，避免不一致。

基礎操作示範

// 建立樹結構
var root = new GeneralTree("A");
var b = new GeneralTree("B");
var c = new GeneralTree("C");
var d = new GeneralTree("D");

root.AttachSubtree(b);
root.AttachSubtree(c);
b.AttachSubtree(d);

// 驗證結構
Console.WriteLine($"Root Key: {root.Key}, Degree: {root.Degree}"); // Degree=2
Console.WriteLine($"B Key: {b.Key}, Degree: {b.Degree}");           // Degree=1
Console.WriteLine($"D IsLeaf: {d.IsLeaf()}");                        // True

下一步

進階篇將補充 IsEmpty、IsLeaf、Equals 等核心方法的完整實作，以及效能優化建議。