資料結構與演算法 C# 實作系列：N 元樹（一）─ 固定度數樹狀結構與空節點處理

前言

N 元樹 要求每個節點度數固定為 N (如二元樹 N=2)。本文實作 NaryTree，以 ArrayList 預先配置 N 個空節點位置，並處理空樹判斷與葉子節點識別。

類別設計

public class NaryTree : Tree
{
    private object _key;
    private uint _degree;
    private ArrayList _subTrees;

    // 空樹建構式 (僅設定度數)
    public NaryTree(uint degree)
    {
        _key = null;
        _degree = degree;
        _subTrees = null;
    }

    // 葉子節點建構式 (含鍵值，預設 N 個空子樹)
    public NaryTree(uint degree, object key)
    {
        _key = key;
        _degree = degree;
        _subTrees = new ArrayList();
        _subTrees.Capacity = (int)degree;
        for (int i = 0; i < degree; i++)
            _subTrees.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 Tree this[uint index]
    {
        get
        {
            if (index >= _degree) throw new Exception("Index out of range");
            if (IsEmpty()) return null;
            return (Tree)_subTrees[(int)index];
        }
        set => _subTrees[(int)index] = value;
    }

    public override object Key => _key;
}

關鍵設計解析

虛擬工廠方法

GetEmptyInstance 允許衍生類別 (如二元樹) 自訂空節點建立邏輯，支援多型擴充。

結語

N 元樹透過預配固定大小陣列與空樹佔位模式，確保結構嚴謹度，適合編譯器語法樹、固定階層資料模型等場景。後續將實作遍歷與搜尋演算法。