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

前言

N 元樹要求所有節點度數固定為 N。本文完善 NaryTree 的關鍵操作：鍵值掛載/卸載、子樹連接/分離、空節點初始化等。

完整類別實作

using System;
using System.Collections;

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

        // 空樹建構子：指定度數
        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;
        }

        // 掛載鍵值：僅限空節點，初始化子樹陣列
        public virtual void AttachKey(object key)
        {
            if (!IsEmpty()) throw new Exception("Node must be empty");
            _key = key;
            _treeList = new ArrayList { Capacity = (int)_degree };
            for (int i = 0; i < _degree; i++)
                _treeList.Add(new NaryTree(_degree));
        }

        // 卸載鍵值：僅限葉節點，轉為空節點
        public virtual object DetachKey()
        {
            if (!IsLeaf()) throw new Exception("Node must be leaf");
            var result = _key;
            _key = null;
            _treeList = null;
            return result;
        }

        // 掛載子樹：指定位置必須為空節點且度數相同
        public virtual void AttachSubtree(uint index, NaryTree subtree)
        {
            if (IsEmpty()) throw new Exception("Cannot attach to empty tree");
            if (!this[index - 1].IsEmpty() || _degree != subtree.Degree)
                throw new Exception("Target must be empty and degree must match");
            this[index - 1] = subtree;
        }

        // 卸載子樹：移除指定位置子樹並替換為空節點
        public virtual NaryTree DetachSubtree(uint index)
        {
            if (IsEmpty()) throw new Exception("Tree is empty");
            var removed = (NaryTree)this[index - 1];
            this[index - 1] = new NaryTree(_degree); // 替換為空節點
            return removed;
        }
    }
}

關鍵設計模式

1. 統一度數約束：建構子鎖定 _degree，所有操作強制度數一致。
2. 空節點模式：以 _key == null 表示空節點，子樹陣列為 null，節省記憶體。
3. 工廠方法 GetEmptyInstance：支援衍生類別自訂空節點建立邏輯 (Template Method 模式)。
4. 1-based 索引對應：公開 API 使用 1-based 索引 (符合樹理論習慣)，內部轉為 0-based 存取。

操作範例

// 建立 3-ary Tree
var root = new NaryTree(3, "Root");
var child1 = new NaryTree(3, "Child1");
var child2 = new NaryTree(3, "Child2");

root.AttachSubtree(1, child1); // 掛載至第 1 個位置
root.AttachSubtree(2, child2); // 掛載至第 2 個位置

// 驗證
Console.WriteLine($"Root Degree: {root.Degree}"); // 3
Console.WriteLine($"Child1 IsLeaf: {child1.IsLeaf()}"); // True

結語

N 元樹的固定度數特性使其適合表示決策樹、遊戲狀態樹、字典樹 等結構。嚴格的度數約束簡化了遍歷與序列化邏輯，但也限制了彈性，實務上常以廣義樹或左子右兄表示法替代。