資料結構與演算法 C# 實作系列：N 元樹（N-ary Tree）完整程式碼

編輯：關於C語言

N 元樹節點類別設計

using System;
using System.Collections;

public class NaryTree {
    private object key;
    private ArrayList treeList;
    private uint degree;

    // 建構子：指定度數（子節點最大數）
    public NaryTree(uint degree) {
        this.degree = degree;
        this.key = null;
        this.treeList = null;
    }

    public uint Degree {
        get { return degree; }
    }

    // 判斷是否為空樹
    public bool IsEmpty() {
        return key == null;
    }

    // 判斷是否為葉節點
    public bool IsLeaf() {
        return !IsEmpty() && treeList != null && 
               treeList.Count == degree && 
               treeList.Cast<NaryTree>().All(t => t.IsEmpty());
    }

    // 索引器：存取第 i 棵子樹 (1-based)
    public NaryTree this[uint index] {
        get {
            if (index < 1 || index > degree || treeList == null)
                throw new ArgumentOutOfRangeException();
            return (NaryTree)treeList[(int)index - 1];
        }
        set {
            if (index < 1 || index > degree || treeList == null)
                throw new ArgumentOutOfRangeException();
            treeList[(int)index - 1] = value;
        }
    }

    // 將鍵值附加到空節點，並初始化子節點陣列
    public virtual void AttachKey(object obj) {
        if (!IsEmpty())
            throw new InvalidOperationException("節點必須為空樹");
        key = obj;
        treeList = new ArrayList();
        treeList.Capacity = (int)degree;
        for (int i = 0; i < degree; i++)
            treeList.Add(new NaryTree(degree));
    }

    // 移除葉節點鍵值，回傳原鍵值
    public virtual object DetachKey() {
        if (!IsLeaf())
            throw new InvalidOperationException("節點必須為葉節點");
        object result = key;
        key = null;
        treeList = null;
        return result;
    }

    // 連接子樹到指定位置
    public virtual void AttachSubtree(uint index, NaryTree subTree) {
        if (IsEmpty())
            throw new InvalidOperationException("父節點不能為空樹");
        if (!this[index].IsEmpty() || degree != subTree.Degree)
            throw new ArgumentException("目標位置必須為空且度數相同");
        this[index] = subTree;
    }

    // 斷開並回傳第 index 棵子樹
    public virtual NaryTree DetachSubtree(uint index) {
        if (IsEmpty())
            throw new InvalidOperationException("樹不能為空");
        NaryTree removed = this[index];
        // 以空樹取代
        this[index] = new NaryTree(degree);
        return removed;
    }
}

設計重點解析

度數固定：建構時指定，所有節點共享相同度數
ArrayList 儲存子節點：1-based 索引對應樹理論慣例
空樹表示法：key == null 且 treeList == null
葉節點定義：非空且所有子節點皆為空樹
防禦性程式設計：前置條件檢查拋出具體例外

使用範例

// 建立 3 元樹
var root = new NaryTree(3);
root.AttachKey("Root");

// 建立子節點
var child1 = new NaryTree(3); child1.AttachKey("Child1");
var child2 = new NaryTree(3); child2.AttachKey("Child2");
var child3 = new NaryTree(3); child3.AttachKey("Child3");

root.AttachSubtree(1, child1);
root.AttachSubtree(2, child2);
root.AttachSubtree(3, child3);

// 走訪
void Traverse(NaryTree node, int depth = 0) {
    if (node.IsEmpty()) return;
    Console.WriteLine(new string(' ', depth * 2) + node.key);
    for (uint i = 1; i <= node.Degree; i++)
        Traverse(node[i], depth + 1);
}

Traverse(root);