C# 資料結構與演算法實戰演示：堆疊、樹、堆、AVL 完整範例

互動式演示架構

主選單驅動多種資料結構演示，展現 C# 實作經典演算法與資料結構。

using System;
using System.Collections.Generic;

namespace DataStructureDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Console.Clear();
                Console.WriteLine("=== C# 資料結構與演算法演示 ===");
                Console.WriteLine("1. 堆疊 - RPN 逆波蘭計算機");
                Console.WriteLine("2. 排序列表 - 多項式加法");
                Console.WriteLine("3. 廣義樹 - 深度/廣度遍歷");
                Console.WriteLine("4. N 元樹 - 插入刪除操作");
                Console.WriteLine("5. 表達式樹 - 後綴轉中綴");
                Console.WriteLine("6. AVL 樹 - 平衡操作演示");
                Console.WriteLine("7. 二元堆 - 優先佇列");
                Console.WriteLine("0. 結束");
                Console.Write("選擇: ");
                
                switch (Console.ReadLine())
                {
                    case "1": DemoStack_RPN(); break;
                    case "2": DemoSortedList_Polynomial(); break;
                    case "3": DemoGeneralTree_Traversal(); break;
                    case "4": DemoNaryTree(); break;
                    case "5": DemoExpressionTree(); break;
                    case "6": DemoAVLTree(); break;
                    case "7": DemoBinaryHeap(); break;
                    case "0": return;
                    default: Console.WriteLine("無效選項"); break;
                }
                Console.WriteLine("\n按任意鍵繼續...");
                Console.ReadKey();
            }
        }
        
        // 以下各演示方法...
    }
}

1. 堆疊應用：RPN 逆波蘭計算機

static void DemoStack_RPN()
{
    Console.WriteLine("輸入 RPN 運算式 (如: 3 4 + 2 * = 14)，空白分隔，q 結束");
    while (true)
    {
        Console.Write("RPN> ");
        string input = Console.ReadLine();
        if (input?.ToLower() == "q") break;
        
        try
        {
            var stack = new Stack();
            foreach (string token in input.Split(' ', StringSplitOptions.RemoveEmptyEntries))
            {
                if (double.TryParse(token, out double num))
                    stack.Push(num);
                else if (token.Length == 1 && "+-*/".Contains(token))
                {
                    if (stack.Count < 2) throw new InvalidOperationException("運算元不足");
                    double b = stack.Pop(), a = stack.Pop();
                    double result = token[0] switch
                    {
                        '+' => a + b, '-' => a - b, '*' => a * b, '/' => a / b,
                        _ => throw new ArgumentException("未知運算子")
                    };
                    stack.Push(result);
                }
                else throw new ArgumentException($"無效 token: {token}");
            }
            Console.WriteLine($"結果: {stack.Pop()} (堆疊剩餘: {stack.Count})");
        }
        catch (Exception ex)
        {
            Console.WriteLine($"錯誤: {ex.Message}");
        }
    }
}

2. SortedList：多項式加法

static void DemoSortedList_Polynomial()
{
    // 多項式：次方為 Key，係數為 Value
    var poly1 = new SortedList { {3, 2}, {1, 5}, {0, -3} };  // 2x³ + 5x - 3
    var poly2 = new SortedList { {2, 4}, {1, -2}, {0, 7} };   // 4x² - 2x + 7
    
    Console.WriteLine($"P1: {FormatPoly(poly1)}");
    Console.WriteLine($"P2: {FormatPoly(poly2)}");
    
    var result = new SortedList();
    foreach (var kvp in poly1) result[kvp.Key] = kvp.Value;
    foreach (var kvp in poly2) 
    {
        if (result.ContainsKey(kvp.Key)) result[kvp.Key] += kvp.Value;
        else result[kvp.Key] = kvp.Value;
    }
    // 移除係數為 0 的項
    var zeroKeys = result.Where(kvp => Math.Abs(kvp.Value) < 1e-10).Select(kvp => kvp.Key).ToList();
    foreach (var k in zeroKeys) result.Remove(k);
    
    Console.WriteLine($"P1+P2: {FormatPoly(result)}");
}

static string FormatPoly(SortedList poly)
{
    if (poly.Count == 0) return "0";
    return string.Join(" + ", poly.Reverse()
        .Select(kvp => kvp.Key switch
        {
            0 => $"{kvp.Value}",
            1 => $"{kvp.Value}x",
            _ => $"{kvp.Value}x^{kvp.Key}"
        })
        .Select(s => s.Replace("+ -", "- ")));
}

3. 廣義樹：多種遍歷

class GeneralTreeNode
{
    public string Value { get; }
    public List Children { get; } = new List();
    public GeneralTreeNode(string v) => Value = v;
}

static void DemoGeneralTree_Traversal()
{
    // 建樹: A(B(D,E), C(F))
    var root = new GeneralTreeNode("A");
    var b = new GeneralTreeNode("B");
    var c = new GeneralTreeNode("C");
    b.Children.Add(new GeneralTreeNode("D"));
    b.Children.Add(new GeneralTreeNode("E"));
    c.Children.Add(new GeneralTreeNode("F"));
    root.Children.Add(b);
    root.Children.Add(c);
    
    Console.WriteLine("前序 (Pre-order):");
    TraversePreOrder(root, 0);
    Console.WriteLine("\n後序 (Post-order):");
    TraversePostOrder(root, 0);
    Console.WriteLine("\n層序 (Level-order/BFS):");
    TraverseLevelOrder(root);
}

static void TraversePreOrder(GeneralTreeNode node, int depth)
{
    Console.WriteLine($"{new string(' ', depth * 2)}{node.Value}");
    foreach (var child in node.Children) TraversePreOrder(child, depth + 1);
}

static void TraversePostOrder(GeneralTreeNode node, int depth)
{
    foreach (var child in node.Children) TraversePostOrder(child, depth + 1);
    Console.WriteLine($"{new string(' ', depth * 2)}{node.Value}");
}

static void TraverseLevelOrder(GeneralTreeNode root)
{
    var queue = new Queue();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        Console.Write($"{node.Value} ");
        foreach (var child in node.Children) queue.Enqueue(child);
    }
    Console.WriteLine();
}

4. N 元樹：三元樹插入刪除

class NaryTreeNode
{
    public string Value { get; }
    public NaryTreeNode[] Children { get; }
    public NaryTreeNode(string v, int degree) { Value = v; Children = new NaryTreeNode[degree]; }
    
    public bool AttachChild(int index, NaryTreeNode child)
    {
        if (index < 0 || index >= Children.Length) return false;
        Children[index] = child;
        return true;
    }
    
    public bool DetachChild(int index)
    {
        if (index < 0 || index >= Children.Length) return false;
        Children[index] = null;
        return true;
    }
}

static void DemoNaryTree()
{
    // 建立 3 元樹
    var A = new NaryTreeNode("A", 3);
    var B = new NaryTreeNode("B", 3);
    var C = new NaryTreeNode("C", 3);
    var D = new NaryTreeNode("D", 3);
    var E = new NaryTreeNode("E", 3);
    
    B.AttachChild(0, D);  // B 的第 0 子 = D
    B.AttachChild(1, E);  // B 的第 1 子 = E
    A.AttachChild(0, B);  // A 的第 0 子 = B
    A.AttachChild(2, C);  // A 的第 2 子 = C
    
    Console.WriteLine("前序遍歷:");
    TraverseNaryPreOrder(A, 0);
}

static void TraverseNaryPreOrder(NaryTreeNode node, int depth)
{
    if (node == null) return;
    Console.WriteLine($"{new string(' ', depth * 2)}{node.Value}");
    foreach (var child in node.Children) TraverseNaryPreOrder(child, depth + 1);
}

5. 表達式樹：後綴轉中綴

class ExprNode
{
    public string Value { get; }
    public ExprNode Left { get; set; }
    public ExprNode Right { get; set; }
    public ExprNode(string v) => Value = v;
}

static void DemoExpressionTree()
{
    Console.WriteLine("輸入後綴運算式 (如: ab+cde+** 即 (a+b)*(c*(d+e)))");
    string postfix = Console.ReadLine();
    
    var stack = new Stack();
    foreach (char c in postfix)
    {
        if (char.IsLetterOrDigit(c))
            stack.Push(new ExprNode(c.ToString()));
        else if ("+-*/".Contains(c))
        {
            var right = stack.Pop();
            var left = stack.Pop();
            var op = new ExprNode(c.ToString()) { Left = left, Right = right };
            stack.Push(op);
        }
    }
    
    var root = stack.Pop();
    Console.WriteLine($"中綴: {ToInfix(root)}");
    Console.WriteLine($"前綴: {ToPrefix(root)}");
    Console.WriteLine($"後綴: {ToPostfix(root)} (驗證)");
}

static string ToInfix(ExprNode n) => n.Left == null ? n.Value : $"({ToInfix(n.Left)}{n.Value}{ToInfix(n.Right)})";
static string ToPrefix(ExprNode n) => n.Left == null ? n.Value : $"{n.Value}{ToPrefix(n.Left)}{ToPrefix(n.Right)}";
static string ToPostfix(ExprNode n) => n.Left == null ? n.Value : $"{ToPostfix(n.Left)}{ToPostfix(n.Right)}{n.Value}";

6. AVL 樹：自我平衡二元搜尋樹

class AvlNode
{
    public int Key { get; }
    public AvlNode Left { get; set; }
    public AvlNode Right { get; set; }
    public int Height { get; set; } = 1;
    public AvlNode(int k) => Key = k;
}

class AvlTree
{
    private AvlNode root;
    
    public void Insert(int key) => root = Insert(root, key);
    
    private AvlNode Insert(AvlNode node, int key)
    {
        if (node == null) return new AvlNode(key);
        
        if (key < node.Key) node.Left = Insert(node.Left, key);
        else if (key > node.Key) node.Right = Insert(node.Right, key);
        else return node;  // 重複鍵不插入
        
        UpdateHeight(node);
        return Balance(node);
    }
    
    private int Height(AvlNode n) => n?.Height ?? 0;
    private void UpdateHeight(AvlNode n) => n.Height = 1 + Math.Max(Height(n.Left), Height(n.Right));
    private int BalanceFactor(AvlNode n) => Height(n.Left) - Height(n.Right);
    
    private AvlNode Balance(AvlNode n)
    {
        int bf = BalanceFactor(n);
        // LL
        if (bf > 1 && BalanceFactor(n.Left) >= 0) return RotateRight(n);
        // LR
        if (bf > 1 && BalanceFactor(n.Left) < 0) { n.Left = RotateLeft(n.Left); return RotateRight(n); }
        // RR
        if (bf < -1 && BalanceFactor(n.Right) <= 0) return RotateLeft(n);
        // RL
        if (bf < -1 && BalanceFactor(n.Right) > 0) { n.Right = RotateRight(n.Right); return RotateLeft(n); }
        return n;
    }
    
    private AvlNode RotateRight(AvlNode y)
    {
        var x = y.Left; y.Left = x.Right; x.Right = y;
        UpdateHeight(y); UpdateHeight(x); return x;
    }
    private AvlNode RotateLeft(AvlNode x)
    {
        var y = x.Right; x.Right = y.Left; y.Left = x;
        UpdateHeight(x); UpdateHeight(y); return y;
    }
    
    public void InOrderTraversal(Action visit) => InOrder(root, visit);
    private void InOrder(AvlNode n, Action visit) { if (n==null) return; InOrder(n.Left, visit); visit(n.Key); InOrder(n.Right, visit); }
}

static void DemoAVLTree()
{
    var tree = new AvlTree();
    int[] keys = {5, 1, 3, 7, 8, 9, 10, 11};
    foreach (var k in keys) tree.Insert(k);
    
    Console.WriteLine("中序遍歷 (應為排序順序):");
    tree.InOrderTraversal(k => Console.Write($"{k} "));
    Console.WriteLine();
}

7. 二元堆：優先佇列

class MinHeap
{
    private List heap = new List();
    
    public int Count => heap.Count;
    
    public void Enqueue(int item)
    {
        heap.Add(item);
        SiftUp(heap.Count - 1);
    }
    
    public int DequeueMin()
    {
        if (heap.Count == 0) throw new InvalidOperationException("堆為空");
        int min = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        SiftDown(0);
        return min;
    }
    
    private void SiftUp(int i)
    {
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (heap[i] >= heap[parent]) break;
            Swap(i, parent);
            i = parent;
        }
    }
    
    private void SiftDown(int i)
    {
        while (true)
        {
            int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
            if (left < heap.Count && heap[left] < heap[smallest]) smallest = left;
            if (right < heap.Count && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            Swap(i, smallest);
            i = smallest;
        }
    }
    
    private void Swap(int i, int j) => (heap[i], heap[j]) = (heap[j], heap[i]);
}

static void DemoBinaryHeap()
{
    var heap = new MinHeap();
    foreach (var v in new[] {12, 10, 8, 6, 4, 2}) heap.Enqueue(v);
    
    Console.WriteLine("依序取出最小值:");
    while (heap.Count > 0) Console.Write($"{heap.DequeueMin()} ");
    Console.WriteLine();
}

本章小結

• 堆疊：LIFO，RPN 計算機、運算式求值、遞迴轉迭代
• SortedList：鍵值自動排序，多項式稀疏表示、範圍查詢
• 樹結構：遞迴遍歷 (前/中/後序)、迭代層序 (BFS/Queue)
• N 元樹：固定度數陣列儲存子節點，適合決策樹、檔案系統
• 表達式樹：運算元為葉節點、運算子為內部節點，編譯器核心資料結構
• AVL 樹：插入後透過旋轉維持平衡，保證 O(log n) 查詢/插入/刪除
• 二元堆：完全二元樹陣列實作，優先佇列、堆積排序、Dijkstra/A* 核心
• 所有演示均為教學用途，生產環境建議使用 System.Collections.Generic 內建類別或成熟函式庫