C# 實作 N 元樹 (N-ary Tree) 資料結構 - 基礎篇

前言

N 元樹 (N-ary Tree) 是每個節點度數固定為 N 的樹形結構。本文建立基礎架構：空節點/葉節點建構、空樹/葉節點判斷、索引器存取。

核心類別定義

using System;
using System.Collections;

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

        // 空樹建構子：僅指定度數
        public NaryTree(uint degree)
        {
            _degree = degree;
            _key = null;
            _treeList = null;
        }

        // 葉節點建構子：建立 N 個空子節點
        public NaryTree(uint degree, object key) : this(degree)
        {
            _key = key;
            _treeList = new ArrayList { Capacity = (int)degree };
            for (int i = 0; i < degree; i++)
                _treeList.Add(GetEmptyInstance(degree));
        }

        // 工廠方法：建立空節點實例
        protected virtual object GetEmptyInstance(uint degree) => new NaryTree(degree);

        // 空樹判斷
        public override bool IsEmpty() => _key == null;

        // 葉節點判斷：非空且所有子樹皆為空
        public override bool IsLeaf()
        {
            if (IsEmpty()) return false;
            for (uint i = 0; i < _degree; i++)
                if (!this[i].IsEmpty()) return false;
            return true;
        }

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

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

設計要點

1. 度數不可變：_degree 為 readonly，樹建立後結構固定。
2. 空節點延遲初始化：空樹不分配子樹陣列，葉節點才建立 N 個空子節點。
3. 虛擬工廠方法：GetEmptyInstance 允許衍生類別自訂節點型別 (如加入額外欄位)。

基本使用

// 建立 2-ary Tree (二元樹)
var root = new NaryTree(2, "Root");
var left = new NaryTree(2, "Left");
var right = new NaryTree(2, "Right");

root[0] = left;  // 索引器設定子節點
root[1] = right;

Console.WriteLine($"Root Key: {root.Key}, Degree: {root.Degree}");
Console.WriteLine($"Left IsLeaf: {left.IsLeaf()}"); // True
Console.WriteLine($"Root[0] Key: {root[0].Key}");   // Left

進階篇預告

下一篇將實作 AttachKey/DetachKey (動態轉換空節點與葉節點)、AttachSubtree/DetachSubtree (子樹遷移) 等進階操作。