本文还有配套的精品资源，点击获取

简介：数据结构与算法是计算机科学的基石，掌握它们对于编写高效、优化的程序至关重要。本文档围绕C#语言，系统讲解了数组、链表、栈、队列、树、图等常用数据结构，以及排序、查找、图算法等核心算法，并结合实际开发场景说明其应用价值。配套代码资源涵盖各类结构与算法的完整实现，是C#开发者提升编程能力、应对复杂问题的重要学习资料。

1. 数据结构基础概念与分类

数据结构是程序设计中不可或缺的核心组成部分，它决定了数据如何被组织、存储和高效操作。本章将从基础概念讲起，逐步展开对数据结构的分类和实现方式的理解。

1.1 数据结构的基本概念

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它不仅包括数据本身，还包含数据之间的关系以及对这些数据的操作方式。简单来说，数据结构 = 数据元素 + 数据关系 + 操作。

例如，在C#中，一个整型数组不仅存储了多个整数，还定义了这些整数在内存中的排列方式，并支持通过索引快速访问。

1.2 数据结构的分类

根据数据元素之间的关系不同，数据结构可以分为以下几类：

分类方式	类型	特点说明
逻辑结构	线性结构、非线性结构	线性结构如数组、链表，非线性如树、图
存储结构	静态结构、动态结构	静态如数组，动态如链表
操作方式	顺序结构、链式结构	顺序结构便于访问，链式结构便于插入删除

本章将重点介绍这些分类的具体含义，并通过C#语言进行示例说明，为后续章节的学习打下坚实基础。

2. 数组结构与操作实现

数组是编程中最基础且最常用的数据结构之一。它以线性结构的形式存储相同类型的数据元素，并通过索引进行快速访问。在C#中，数组的实现灵活且高效，广泛应用于算法处理、图形渲染、游戏开发等多个领域。本章将从数组的基本概念入手，逐步深入到C#中数组的声明、初始化、操作实现，以及其在实际开发中的典型应用场景。

2.1 数组的基本概念

2.1.1 什么是数组

数组（Array）是一种用于存储固定大小、相同类型数据的线性结构。数组中的每个元素通过一个整数索引进行访问，索引从0开始递增。例如，一个包含5个整数的数组可以表示为： int[] arr = new int[5]; 。其中， arr[0] 表示第一个元素， arr[4] 表示第五个元素。

数组在内存中是连续存储的，这意味着访问数组元素的时间复杂度为O(1)，即常数时间复杂度，这使得数组在需要频繁访问元素的场景中非常高效。

2.1.2 数组的优缺点分析

优点	缺点
访问速度快，时间复杂度为O(1)	插入和删除效率低，需移动元素
结构简单，易于理解和实现	容量固定，无法动态扩展
支持多维数组，适合矩阵运算	插入元素时需预先分配足够空间

数组的缺点主要体现在插入和删除操作上。由于数组的大小是固定的，当需要插入一个新元素时，必须移动插入位置之后的所有元素，这在数据量大的情况下会导致性能下降。此外，数组一旦声明，其长度无法更改，除非手动进行扩容。

// 示例：数组的访问与遍历
int[] numbers = { 10, 20, 30, 40, 50 };

// 访问元素
Console.WriteLine("第三个元素：" + numbers[2]); // 输出 30

// 遍历数组
for (int i = 0; i < numbers.Length; i++)
{
    Console.WriteLine($"索引 {i} 的值为：{numbers[i]}");
}

代码逻辑分析：

• int[] numbers = { 10, 20, 30, 40, 50 }; ：声明并初始化一个整型数组。
• numbers[2] ：通过索引访问数组中的第三个元素。
• for 循环：利用数组的 Length 属性遍历数组，逐个输出元素值。
• Console.WriteLine ：输出结果到控制台。

此代码演示了数组的基本访问和遍历方式，体现了数组结构的线性特征和索引访问机制。

2.2 C#中数组的声明与初始化

2.2.1 一维数组的定义与使用

在C#中，一维数组是最基本的数组形式。声明方式如下：

int[] arr; // 声明
arr = new int[5]; // 初始化

也可以在声明的同时初始化数组：

int[] arr = new int[] { 1, 2, 3, 4, 5 };

或更简洁地：

int[] arr = { 1, 2, 3, 4, 5 };

一维数组适用于线性数据的处理，如成绩表、温度记录等。

// 示例：一维数组的赋值与输出
string[] names = new string[3];

names[0] = "Alice";
names[1] = "Bob";
names[2] = "Charlie";

foreach (string name in names)
{
    Console.WriteLine(name);
}

代码逻辑分析：

• string[] names = new string[3]; ：创建一个长度为3的字符串数组。
• 通过索引逐一赋值。
• foreach 循环：遍历数组并输出每个字符串。

2.2.2 多维数组与交错数组的区别

C#支持多维数组（矩形数组）和交错数组（锯齿数组）：

• 多维数组 ：所有行长度一致，声明方式为 int[,] arr = new int[2,3];
• 交错数组 ：每行长度可以不同，声明方式为 int[][] arr = new int[2][];

// 多维数组示例
int[,] matrix = {
    {1, 2, 3},
    {4, 5, 6}
};

// 交错数组示例
int[][] jaggedArray = new int[][]
{
    new int[] {1, 2},
    new int[] {3, 4, 5},
    new int[] {6}
};

区别总结：

特性	多维数组	交错数组
内存布局	连续内存块	多个独立数组
行列长度	固定行列	每行可变长度
初始化方式	使用逗号分隔	分别初始化每一行
访问方式	arr[i,j]	arr[i][j]

graph TD
    A[多维数组] --> B[矩形结构]
    B --> C{访问方式: arr[i,j]}
    A --> D[内存连续]
    E[交错数组] --> F[锯齿结构]
    F --> G{访问方式: arr[i][j]}
    E --> H[内存不连续]

2.2.3 数组的默认值与访问方式

在C#中，数组的默认值取决于其元素类型：

• int[] ：默认值为0
• string[] ：默认值为 null
• bool[] ：默认值为 false
• object[] ：默认值为 null

访问数组时，可以通过索引直接访问，也可以使用 foreach 循环进行遍历：

int[] nums = new int[3]; // 默认值为 0, 0, 0

foreach (int num in nums)
{
    Console.WriteLine(num); // 输出 0 三次
}

参数说明：

• new int[3] ：创建长度为3的整型数组，默认值为0。
• foreach ：遍历数组中的每一个元素并输出。

2.3 数组的基本操作

2.3.1 元素的增删与修改

由于数组的长度固定，无法直接进行增删操作，但可以通过创建新数组来实现。

// 修改数组元素
int[] arr = { 1, 2, 3, 4 };
arr[2] = 99; // 修改索引2的值为99

// 插入元素（模拟）
int[] newArr = new int[arr.Length + 1];
Array.Copy(arr, newArr, arr.Length);
newArr[arr.Length] = 5;

// 删除元素（模拟）
int[] result = new int[newArr.Length - 1];
Array.Copy(newArr, result, result.Length);

逻辑分析：

• Array.Copy ：复制原数组内容到新数组中。
• 插入操作：通过扩容新数组并在最后添加元素实现。
• 删除操作：创建一个比原数组少一个元素的新数组，并复制前n-1个元素。

2.3.2 数组的排序与查找

C#提供了内置的排序与查找方法：

int[] arr = { 5, 2, 8, 1, 3 };

// 排序
Array.Sort(arr); // 升序排序：1, 2, 3, 5, 8

// 查找
int index = Array.IndexOf(arr, 3); // 返回索引 2

逻辑分析：

• Array.Sort ：对数组进行升序排序。
• Array.IndexOf ：查找指定元素的索引位置，若未找到则返回-1。

2.3.3 数组扩容的实现方式

由于数组长度不可变，扩容通常通过创建新数组实现：

int[] original = { 1, 2, 3 };
int[] expanded = new int[original.Length * 2];
Array.Copy(original, expanded, original.Length);

流程图说明：

graph LR
    A[原始数组] --> B[创建新数组]
    B --> C[复制原数组内容]
    C --> D[释放原数组引用]

逻辑分析：

• 创建新数组，长度为原数组的两倍。
• 使用 Array.Copy 将原数组内容复制到新数组中。
• 原数组引用失效，等待GC回收。

2.4 数组结构在实际开发中的应用场景

2.4.1 数据缓存的存储结构设计

在开发中，数组常用于缓存静态数据，例如配置信息、常量表等。

// 示例：缓存配置信息
string[] configKeys = { "dbHost", "dbName", "dbUser", "dbPass" };
string[] configValues = { "localhost", "mydb", "root", "123456" };

string GetValue(string key)
{
    int index = Array.IndexOf(configKeys, key);
    return index >= 0 ? configValues[index] : null;
}

逻辑分析：

• 使用两个数组分别存储配置键与值。
• 通过 Array.IndexOf 查找键的位置，并返回对应的值。
• 适用于小型、静态配置数据的快速查找。

2.4.2 游戏开发中的地图数据表示

在游戏开发中，地图通常用二维数组表示：

int[,] map = {
    { 0, 1, 0, 0 },
    { 0, 1, 1, 0 },
    { 0, 0, 1, 0 }
};

// 0 表示可行走区域，1 表示障碍物

应用场景：

• 地图数据可直接映射到游戏引擎中的网格系统。
• 可用于路径查找（如A*算法）。
• 支持碰撞检测与地形渲染。

graph TD
    A[地图数组] --> B[路径查找算法]
    A --> C[渲染引擎]
    A --> D[碰撞检测模块]

逻辑分析：

• 二维数组 map 表示游戏地图。
• 0 表示可行走区域， 1 表示障碍。
• 各模块根据数组内容进行相应处理，如AI寻路、角色移动判断等。

本章详细讲解了数组的基本概念、C#中的实现方式及其在实际开发中的应用场景。数组作为最基础的数据结构，虽然在插入和删除方面存在局限，但其高效的访问特性使其在缓存、地图表示等场景中具有不可替代的作用。下一章将深入探讨链表结构，比较其与数组的异同，并展示其动态扩展的优势。

3. 链表结构与增删查改实现

3.1 链表的基本原理

链表是一种非常基础但极其重要的线性数据结构。与数组不同，链表通过节点之间的链接来组织数据，而不是依赖连续的内存空间。这种特性使得链表在动态内存管理中表现出色，尤其是在需要频繁插入和删除元素的场景中。

3.1.1 链表与数组的对比

链表和数组是两种最常见的线性数据结构，它们各有优劣。以下是对它们的详细对比：

对比维度	数组	链表
内存分配	连续内存空间	非连续内存空间
访问方式	支持随机访问（O(1)）	顺序访问（O(n)）
插入/删除	需要移动大量元素（O(n)）	插入/删除效率高（O(1)，前提是已知节点位置）
扩容机制	需要重新分配空间并复制数据	动态增长，无需整体复制
空间开销	小，仅存储数据	大，每个节点需存储指针信息
适用场景	数据量固定、频繁访问	数据量不确定、频繁修改

从上表可以看出，数组适合静态数据处理，而链表更适合动态数据管理。在C#中，数组的实现是固定长度的，而链表可以通过类来模拟动态结构。

3.1.2 单链表、双链表与循环链表的概念

链表根据节点之间的连接方式可以分为以下几种类型：

• 单链表（Singly Linked List） ：每个节点只包含一个指向下一个节点的指针。结构简单，适用于单向操作。
• 双链表（Doubly Linked List） ：每个节点包含两个指针，分别指向前一个节点和后一个节点。支持双向遍历，插入和删除操作更灵活。
• 循环链表（Circular Linked List） ：链表的尾节点指向头节点，形成一个环。适用于需要循环遍历的场景，如任务调度等。

mermaid
graph TD
A[Singly Linked List] –> B[One-way traversal]
A –> C[Node contains data + next pointer]
D[Doubly Linked List] –> E[Two-way traversal]
D –> F[Node contains data + prev + next pointers]
G[Circular Linked List] –> H[Tail node points to head]
G –> I[Useful for round-robin algorithms]
通过这种分类，开发者可以根据实际需求选择最适合的链表结构。

3.2 单链表的实现

单链表是最基础的链表结构，适用于很多简单的数据管理场景。我们可以通过C#来手动实现一个基本的单链表结构。

3.2.1 节点类的设计与实现

单链表的基本单位是节点（Node）。每个节点应包含数据和指向下一个节点的引用。下面是一个简单的C#实现：

public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

逻辑分析：

• Data 属性用于存储节点的数据，泛型 T 使其具有通用性。
• Next 属性指向下一个节点，初始为 null 。
• 构造函数接收一个数据值并初始化 Next 。

这个类可以作为链表中每个节点的基础结构。

3.2.2 插入与删除操作的具体实现

单链表的核心操作包括插入和删除。我们来实现一个简单的链表类，并实现插入和删除功能：

public class SinglyLinkedList<T>
{
    private Node<T> head;

    // 插入到链表头部
    public void InsertAtHead(T data)
    {
        Node<T> newNode = new Node<T>(data);
        newNode.Next = head;
        head = newNode;
    }

    // 删除指定值的节点
    public bool Delete(T data)
    {
        Node<T> current = head;
        Node<T> previous = null;

        while (current != null)
        {
            if (current.Data.Equals(data))
            {
                if (previous == null)
                {
                    head = current.Next; // 删除头节点
                }
                else
                {
                    previous.Next = current.Next; // 删除中间或尾节点
                }
                return true;
            }
            previous = current;
            current = current.Next;
        }
        return false;
    }
}

逻辑分析：

• InsertAtHead 方法创建一个新节点，并将其 Next 指向当前头节点，然后更新头节点为新节点，实现头部插入。
• Delete 方法通过遍历链表查找指定值的节点。若找到则调整前后节点的链接关系，实现删除。

3.2.3 查找与遍历操作的实现逻辑

查找和遍历是链表的两个基本操作。我们继续扩展 SinglyLinkedList 类：

public class SinglyLinkedList<T>
{
    // ... 上面的代码保持不变

    // 查找是否存在指定值
    public bool Contains(T data)
    {
        Node<T> current = head;
        while (current != null)
        {
            if (current.Data.Equals(data))
                return true;
            current = current.Next;
        }
        return false;
    }

    // 打印整个链表
    public void PrintList()
    {
        Node<T> current = head;
        while (current != null)
        {
            Console.Write(current.Data + " -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

逻辑分析：

• Contains 方法遍历链表，检查是否存在指定值，时间复杂度为 O(n)。
• PrintList 方法从头节点开始逐个输出数据，直到遇到 null ，用于调试和可视化链表结构。

3.3 双链表与循环链表的进阶实现

双链表和循环链表是对单链表的扩展，提供了更高的灵活性和更丰富的操作能力。

3.3.1 双链表的节点结构与操作实现

双链表的节点比单链表多了一个指向前一个节点的引用。我们来实现一个双链表结构：

public class DoublyNode<T>
{
    public T Data { get; set; }
    public DoublyNode<T> Prev { get; set; }
    public DoublyNode<T> Next { get; set; }

    public DoublyNode(T data)
    {
        Data = data;
        Prev = null;
        Next = null;
    }
}

public class DoublyLinkedList<T>
{
    private DoublyNode<T> head;
    private DoublyNode<T> tail;

    // 插入到尾部
    public void InsertAtTail(T data)
    {
        DoublyNode<T> newNode = new DoublyNode<T>(data);
        if (tail == null)
        {
            head = tail = newNode;
        }
        else
        {
            tail.Next = newNode;
            newNode.Prev = tail;
            tail = newNode;
        }
    }

    // 删除指定节点
    public void Delete(DoublyNode<T> node)
    {
        if (node.Prev != null)
        {
            node.Prev.Next = node.Next;
        }
        else
        {
            head = node.Next; // 删除头节点
        }

        if (node.Next != null)
        {
            node.Next.Prev = node.Prev;
        }
        else
        {
            tail = node.Prev; // 删除尾节点
        }
    }
}

逻辑分析：

• DoublyNode 类包含 Prev 和 Next 两个引用，实现双向链接。
• InsertAtTail 方法在链表尾部插入新节点，同时维护 Prev 指针。
• Delete 方法通过修改前后节点的引用关系来删除指定节点，考虑了头尾节点的特殊情况。

3.3.2 循环链表的特殊应用场景

循环链表是一种首尾相连的链表结构，常用于需要循环处理的场景，例如操作系统中的任务调度、轮询机制等。

public class CircularLinkedList<T>
{
    private Node<T> head;

    public void Insert(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
            newNode.Next = head;
        }
        else
        {
            Node<T> current = head;
            while (current.Next != head)
            {
                current = current.Next;
            }
            current.Next = newNode;
            newNode.Next = head;
        }
    }

    public void PrintList()
    {
        if (head == null) return;
        Node<T> current = head;
        do
        {
            Console.Write(current.Data + " -> ");
            current = current.Next;
        } while (current != head);
        Console.WriteLine("...");
    }
}

逻辑分析：

• Insert 方法将新节点插入到循环链表中，并确保尾节点始终指向头节点。
• PrintList 方法通过循环打印所有节点，直到回到头节点为止。

mermaid
graph LR
A[Insert new node] –> B[Check if head is null]
B –>|Yes| C[Set head to new node and point to itself]
B –>|No| D[Traverse to tail node]
D –> E[Link new node to tail and head]

循环链表非常适合需要不断重复处理数据的场景，如轮询系统、游戏中的角色轮次控制等。

3.4 链表在C#中的实际应用案例

链表不仅在理论层面具有重要价值，也在实际开发中被广泛应用。

3.4.1 实现一个通用链表类

C#中虽然有 LinkedList<T> 类，但为了深入理解其内部机制，我们可以自己实现一个轻量级的通用链表类：

public class MyLinkedList<T>
{
    private Node<T> head;

    public void AddFirst(T data)
    {
        Node<T> newNode = new Node<T>(data);
        newNode.Next = head;
        head = newNode;
    }

    public void AddLast(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            Node<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Remove(T data)
    {
        Node<T> current = head;
        Node<T> previous = null;
        while (current != null)
        {
            if (current.Data.Equals(data))
            {
                if (previous == null)
                {
                    head = current.Next;
                }
                else
                {
                    previous.Next = current.Next;
                }
                return;
            }
            previous = current;
            current = current.Next;
        }
    }
}

逻辑分析：

• AddFirst 和 AddLast 分别在链表头和尾插入新节点。
• Remove 方法遍历链表删除指定值的节点。

该类可用于模拟 LinkedList<T> 的部分功能，帮助开发者理解其底层实现。

3.4.2 在数据缓存与动态内存管理中的使用

链表在动态内存管理和数据缓存中具有天然优势。例如，在实现一个LRU（Least Recently Used）缓存时，链表可以高效地进行节点的插入和删除操作。

以下是一个简化版的LRU缓存实现思路：

public class LRUCache<TKey, TValue>
{
    private Dictionary<TKey, DoublyNode<KeyValuePair<TKey, TValue>>> cache;
    private DoublyLinkedList<KeyValuePair<TKey, TValue>> list;
    private int capacity;

    public LRUCache(int capacity)
    {
        this.capacity = capacity;
        cache = new Dictionary<TKey, DoublyNode<KeyValuePair<TKey, TValue>>>();
        list = new DoublyLinkedList<KeyValuePair<TKey, TValue>>();
    }

    public TValue Get(TKey key)
    {
        if (cache.TryGetValue(key, out DoublyNode<KeyValuePair<TKey, TValue>> node))
        {
            // 将节点移到链表头部，表示最近使用
            list.Delete(node);
            list.InsertAtHead(node.Data);
            return node.Data.Value;
        }
        return default(TValue);
    }

    public void Put(TKey key, TValue value)
    {
        if (cache.TryGetValue(key, out DoublyNode<KeyValuePair<TKey, TValue>> node))
        {
            list.Delete(node);
        }
        else if (cache.Count >= capacity)
        {
            // 删除尾节点
            var lastNode = list.GetTail();
            cache.Remove(lastNode.Data.Key);
            list.Delete(lastNode);
        }
        var newNode = new DoublyNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value));
        list.InsertAtHead(newNode);
        cache[key] = newNode;
    }
}

逻辑分析：

• 使用字典 cache 快速查找节点。
• 使用双链表 list 维护最近使用顺序。
• Get 和 Put 操作会调整节点位置，实现LRU机制。

这种结构在Web服务器、数据库连接池等高性能系统中非常常见。

4. 栈结构实现与LIFO原理

4.1 栈的基本概念与原理

4.1.1 LIFO（后进先出）机制解析

栈（Stack）是一种线性数据结构，其操作遵循后进先出（Last In First Out，LIFO）的原则。这意味着最后被压入（Push）栈的数据项将最先被弹出（Pop）。栈的操作方式可以类比为一叠盘子，我们只能在最上面添加或取出盘子，不能从中层或底层操作。

在程序设计中，栈结构广泛应用于函数调用、表达式求值、括号匹配等场景。例如，在C#中，程序运行时的调用栈（Call Stack）用于管理函数调用的顺序，确保函数执行完毕后能正确返回到调用点。

LIFO机制的本质在于限制数据的访问方式。栈只能通过栈顶进行操作，其他元素无法被直接访问或修改。这种限制虽然减少了灵活性，但却带来了高效性和可预测性，尤其适用于需要“撤销”或“回溯”操作的场景。

4.1.2 栈的基本操作：Push、Pop、Peek

栈的核心操作包括：

• Push（压栈） ：将元素添加到栈顶。
• Pop（出栈） ：移除并返回栈顶元素。
• Peek（查看栈顶） ：返回栈顶元素但不移除它。

这些操作的实现必须确保栈的LIFO特性。以下是一个基于数组的简单栈操作示例（使用C#）：

public class SimpleStack<T>
{
    private T[] items;
    private int top;
    private const int DefaultCapacity = 4;

    public SimpleStack()
    {
        items = new T[DefaultCapacity];
        top = -1;
    }

    public void Push(T item)
    {
        if (top == items.Length - 1)
            Resize(items.Length * 2); // 扩容
        items[++top] = item;
    }

    public T Pop()
    {
        if (IsEmpty())
            throw new InvalidOperationException("栈为空");
        T item = items[top--];
        if (top > 0 && top < items.Length / 4)
            Resize(items.Length / 2); // 缩容
        return item;
    }

    public T Peek()
    {
        if (IsEmpty())
            throw new InvalidOperationException("栈为空");
        return items[top];
    }

    public bool IsEmpty()
    {
        return top == -1;
    }

    private void Resize(int newSize)
    {
        T[] newItems = new T[newSize];
        for (int i = 0; i <= top; i++)
            newItems[i] = items[i];
        items = newItems;
    }
}

逐行分析与逻辑说明：

• items ：内部数组用于存储栈元素。
• top ：表示栈顶索引，初始为-1。
• Push ：先检查是否需要扩容，然后将元素添加到栈顶。
• Pop ：移除栈顶元素，若元素较少则缩容以节省空间。
• Peek ：返回栈顶元素但不删除。
• Resize ：动态调整数组大小以适应栈的变化。

参数说明：

• T ：泛型参数，允许栈存储任意类型数据。
• top ：控制栈顶位置，确保LIFO逻辑。
• Resize ：通过复制数组实现容量的动态调整。

流程图：

graph TD
    A[Push操作] --> B{栈满?}
    B -->|是| C[扩容]
    B -->|否| D[添加元素到top+1]
    D --> E[top++]
    C --> D

    F[Pop操作] --> G{栈空?}
    G -->|是| H[抛出异常]
    G -->|否| I[取出top元素]
    I --> J[top--]
    J --> K{是否缩容?}
    K -->|是| L[缩容]

该流程图清晰地展示了栈操作的控制逻辑，帮助理解栈的LIFO机制。

4.2 使用数组和链表实现栈

4.2.1 基于数组的栈实现

使用数组实现栈是最直观的方式。由于数组具有连续的内存空间，访问效率高，适合需要频繁进行 Peek 操作的场景。然而，数组的大小是固定的，因此在实现栈时必须处理扩容与缩容的问题。

以下是一个完整的数组栈实现：

public class ArrayStack<T>
{
    private T[] _array;
    private int _topIndex;

    public ArrayStack(int capacity = 4)
    {
        _array = new T[capacity];
        _topIndex = -1;
    }

    public void Push(T item)
    {
        if (_topIndex == _array.Length - 1)
            ResizeArray();
        _array[++_topIndex] = item;
    }

    public T Pop()
    {
        if (IsEmpty())
            throw new InvalidOperationException("栈为空");
        return _array[_topIndex--];
    }

    public T Peek()
    {
        if (IsEmpty())
            throw new InvalidOperationException("栈为空");
        return _array[_topIndex];
    }

    public bool IsEmpty()
    {
        return _topIndex == -1;
    }

    private void ResizeArray()
    {
        T[] newArray = new T[_array.Length * 2];
        for (int i = 0; i <= _topIndex; i++)
        {
            newArray[i] = _array[i];
        }
        _array = newArray;
    }
}

逐行分析与逻辑说明：

• _array ：用于存储栈数据的数组。
• _topIndex ：记录当前栈顶位置。
• Push ：检查是否需要扩容后，将元素放入栈顶。
• Pop ：弹出栈顶元素并更新栈顶索引。
• ResizeArray ：当栈满时，创建新数组并复制数据。

表格对比数组栈的性能特点：

操作	时间复杂度	说明
Push	O(1)（均摊）	扩容时为O(n)，均摊后为O(1)
Pop	O(1)	直接操作栈顶
Peek	O(1)	仅访问栈顶元素
Resize	O(n)	数组复制导致的时间开销

4.2.2 基于链表的栈实现

相比数组实现，链表实现的栈在空间管理上更为灵活。每个节点动态分配内存，避免了扩容问题。链表栈的核心在于头插法，即每次插入新节点都在链表头部（栈顶）。

以下是一个基于单链表实现的栈类：

public class Node<T>
{
    public T Data;
    public Node<T> Next;

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

public class LinkedListStack<T>
{
    private Node<T> _top;

    public void Push(T item)
    {
        Node<T> newNode = new Node<T>(item);
        newNode.Next = _top;
        _top = newNode;
    }

    public T Pop()
    {
        if (_top == null)
            throw new InvalidOperationException("栈为空");
        T data = _top.Data;
        _top = _top.Next;
        return data;
    }

    public T Peek()
    {
        if (_top == null)
            throw new InvalidOperationException("栈为空");
        return _top.Data;
    }

    public bool IsEmpty()
    {
        return _top == null;
    }
}

逐行分析与逻辑说明：

• Node<T> ：定义链表节点结构。
• Push ：创建新节点，并将其插入到链表头部。
• Pop ：删除头节点并返回其数据。
• Peek ：查看头节点数据但不删除。

表格对比链表栈的性能特点：

操作	时间复杂度	说明
Push	O(1)	插入头部，无需遍历
Pop	O(1)	删除头部
Peek	O(1)	仅访问头部节点
Resize	无	动态节点分配，无需扩容缩容

性能比较分析：

实现方式	优点	缺点
数组栈	访问速度快，缓存友好	需要扩容缩容，空间利用率低
链表栈	动态内存管理，无需扩容	指针操作开销大，缓存不友好

4.3 栈在实际开发中的典型应用

4.3.1 函数调用栈的模拟实现

函数调用栈（Call Stack）是程序运行时用于管理函数调用的机制。每次调用一个函数，程序会将其上下文压入调用栈；函数返回后，从栈中弹出上下文并恢复执行。

我们可以用栈结构来模拟函数调用栈的执行过程：

public class CallStackSimulator
{
    private Stack<string> _callStack = new Stack<string>();

    public void CallFunction(string funcName)
    {
        Console.WriteLine($"调用函数: {funcName}");
        _callStack.Push(funcName);
        PrintStack();
    }

    public void ReturnFunction()
    {
        if (_callStack.Count == 0)
        {
            Console.WriteLine("调用栈为空");
            return;
        }
        string funcName = _callStack.Pop();
        Console.WriteLine($"函数返回: {funcName}");
        PrintStack();
    }

    private void PrintStack()
    {
        Console.WriteLine("当前调用栈: " + string.Join(" -> ", _callStack.Reverse()));
    }
}

示例调用：

CallStackSimulator simulator = new CallStackSimulator();
simulator.CallFunction("Main");
simulator.CallFunction("Calculate");
simulator.ReturnFunction();
simulator.CallFunction("Render");

输出结果：

调用函数: Main
当前调用栈: Main
调用函数: Calculate
当前调用栈: Main -> Calculate
函数返回: Calculate
当前调用栈: Main
调用函数: Render
当前调用栈: Main -> Render

表格展示调用栈状态变化：

步骤	操作	栈内容
1	Call Main	[Main]
2	Call Calculate	[Main, Calculate]
3	Return	[Main]
4	Call Render	[Main, Render]

4.3.2 表达式求值与括号匹配算法

栈在表达式求值和括号匹配中也具有重要应用。例如，我们可以使用栈来判断括号是否匹配：

public bool AreParenthesesBalanced(string expression)
{
    Stack<char> stack = new Stack<char>();

    foreach (char ch in expression)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.Push(ch);
        }
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (stack.Count == 0)
                return false;

            char top = stack.Pop();
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{'))
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

逐行分析与逻辑说明：

• stack ：用于保存左括号。
• 遇到左括号就压栈，遇到右括号就弹栈并判断是否匹配。
• 最终栈为空则括号匹配成功。

表格测试案例：

表达式	是否匹配	说明
()[]{}{}	✅	所有括号正确闭合
([)]	❌	不符合匹配顺序
{([])}	✅	多层嵌套，匹配正确
(([]))	✅	简单嵌套结构

4.4 C#标准库中的Stack类使用技巧

4.4.1 Stack 的基本操作

C#标准库提供了泛型 Stack<T> 类，位于 System.Collections.Generic 命名空间中。它提供了与我们自定义栈相似的操作接口，但具有更高的性能和安全性。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();

        stack.Push(10);
        stack.Push(20);
        stack.Push(30);

        Console.WriteLine("栈顶元素: " + stack.Peek()); // 输出30

        while (stack.Count > 0)
        {
            Console.WriteLine("弹出元素: " + stack.Pop());
        }
    }
}

逐行分析与逻辑说明：

• Push ：将元素压入栈。
• Peek ：查看栈顶元素。
• Pop ：弹出栈顶元素并返回。
• Count ：获取栈中元素数量。

4.4.2 性能优化与线程安全处理

Stack<T> 在单线程环境下性能良好，但在多线程环境中存在线程安全问题。为了避免竞态条件，可以使用以下方式：

• 使用 lock 锁机制进行同步：

private static Stack<int> sharedStack = new Stack<int>();
private static object lockObj = new object();

public static void ThreadSafePush(int value)
{
    lock (lockObj)
    {
        sharedStack.Push(value);
    }
}

• 使用 ConcurrentStack<T> （线程安全栈）：

using System.Collections.Concurrent;

ConcurrentStack<int> threadSafeStack = new ConcurrentStack<int>();
threadSafeStack.Push(10);
threadSafeStack.TryPop(out int result);

表格对比不同栈的线程安全特性：

类型	线程安全	性能	适用场景
Stack	❌	高	单线程环境
lock + Stack	✅	中	小规模并发控制
ConcurrentStack	✅	中	高并发环境

总结：

• Stack<T> 是C#标准库中高效的栈实现。
• 在多线程环境下应考虑线程安全机制。
• 可根据需求选择锁机制或使用 ConcurrentStack<T> 。

5. 队列结构实现与FIFO原理

队列（Queue）是程序设计中最基础的数据结构之一，广泛应用于任务调度、消息传递、系统缓存等场景。其核心原理是先进先出（FIFO, First In First Out），即最先进入队列的元素最先被取出。本章将从队列的基本概念入手，深入探讨其在C#中的实现方式，并通过数组和链表两种结构构建队列，同时介绍优先队列、双端队列等扩展结构，以及C#标准库中的 Queue<T> 类在实际项目中的应用。

5.1 队列的基本概念与原理

5.1.1 FIFO（先进先出）机制解析

FIFO是队列结构的核心特性。与栈结构的LIFO不同，队列中数据元素的添加操作（Enqueue）发生在队列尾部（rear），而数据的取出操作（Dequeue）则发生在队列头部（front）。这种特性保证了队列中元素的顺序性，也使得它非常适合处理需要保持顺序的任务流。

在操作系统中，线程调度常使用队列结构管理就绪线程；在Web开发中，请求队列用于管理客户端的请求；在任务调度系统中，如消息队列系统RabbitMQ、Kafka等，也大量依赖队列结构。

5.1.2 队列的基本操作：Enqueue、Dequeue、Peek

队列的基本操作包括：

• Enqueue ：将元素插入队列尾部。
• Dequeue ：移除并返回队列头部的元素。
• Peek ：返回队列头部元素但不移除。
• IsEmpty ：判断队列是否为空。
• Count ：获取队列中元素的数量。

这些操作的时间复杂度应尽量控制在 O(1)，以保证队列的高效性。

以下是一个简单的队列操作示意图：

graph LR
A[Enqueue(10)] --> B[Enqueue(20)]
B --> C[Enqueue(30)]
C --> D[Dequeue() => 10]
D --> E[Peek() => 20]

5.2 使用数组和链表实现队列

5.2.1 基于数组的循环队列实现

使用数组实现队列时，最简单的方式是使用一个固定大小的数组，并维护两个指针： front （队头）和 rear （队尾）。但由于每次Dequeue后 front 前移，数组前面的空间将无法复用，造成“假溢出”现象。

为了解决这个问题，可以使用 循环队列（Circular Queue） 结构。

实现思路：

• 使用数组 T[] data 存储元素。
• 用 int front 和 int rear 表示队头和队尾索引。
• int count 记录当前元素个数。
• 当 rear == capacity 时， rear 回到0（循环逻辑）。

代码实现：

public class CircularQueue<T>
{
    private T[] data;
    private int front;  // 队头索引
    private int rear;   // 队尾索引
    private int count;  // 当前元素数量
    private int capacity; // 容量

    public CircularQueue(int capacity)
    {
        this.capacity = capacity;
        data = new T[capacity];
        front = 0;
        rear = 0;
        count = 0;
    }

    public void Enqueue(T item)
    {
        if (count == capacity)
            throw new InvalidOperationException("队列已满");

        data[rear] = item;
        rear = (rear + 1) % capacity;
        count++;
    }

    public T Dequeue()
    {
        if (IsEmpty())
            throw new InvalidOperationException("队列为空");

        T item = data[front];
        front = (front + 1) % capacity;
        count--;
        return item;
    }

    public T Peek()
    {
        if (IsEmpty())
            throw new InvalidOperationException("队列为空");

        return data[front];
    }

    public bool IsEmpty()
    {
        return count == 0;
    }

    public int Count()
    {
        return count;
    }
}

逻辑分析与参数说明：

• 构造函数 接收一个 capacity 参数，初始化数组和指针。
• Enqueue 方法将元素添加到 rear 位置， rear 自增后模容量，形成循环。
• Dequeue 方法取出 front 位置的元素， front 自增后模容量。
• 检查队列是否满/空通过 count 判断，而不是直接比较 front 和 rear ，避免逻辑错误。

优缺点分析：

特性	优点	缺点
空间利用率	数组空间复用，无内存浪费	容量固定，扩容成本高
操作效率	Enqueue和Dequeue时间复杂度O(1)	扩容时需复制数组，效率降低
实现难度	逻辑清晰，易于理解	需处理循环索引逻辑

5.2.2 基于链表的队列实现

链表实现的队列不需要预分配容量，可以动态增长，适用于元素数量不确定的场景。

实现思路：

• 使用单链表或双链表结构。
• 维护两个引用： head （队头）和 tail （队尾）。
• 插入操作在 tail 后添加新节点，删除操作从 head 移除节点。

代码实现：

public class LinkedListQueue<T>
{
    private class Node
    {
        public T Data;
        public Node Next;

        public Node(T data)
        {
            Data = data;
            Next = null;
        }
    }

    private Node head;
    private Node tail;
    private int count;

    public void Enqueue(T item)
    {
        Node newNode = new Node(item);

        if (tail != null)
        {
            tail.Next = newNode;
        }

        tail = newNode;

        if (head == null)
        {
            head = tail;
        }

        count++;
    }

    public T Dequeue()
    {
        if (head == null)
            throw new InvalidOperationException("队列为空");

        T data = head.Data;
        head = head.Next;

        if (head == null)
        {
            tail = null;
        }

        count--;
        return data;
    }

    public T Peek()
    {
        if (head == null)
            throw new InvalidOperationException("队列为空");

        return head.Data;
    }

    public bool IsEmpty()
    {
        return head == null;
    }

    public int Count()
    {
        return count;
    }
}

逻辑分析与参数说明：

• Node类 是链表节点，包含数据和指向下一个节点的引用。
• Enqueue 方法创建新节点，并将 tail.Next 指向它，更新 tail 。
• Dequeue 方法取出 head 节点的数据，并将 head 指向下一个节点。
• 当 head 为null时，表示队列为空；当 head == tail 时，删除后需将 tail 置为null。

优缺点分析：

特性	优点	缺点
动态扩展	无需预分配容量，支持无限增长	需要额外内存存储引用
操作效率	插入和删除时间复杂度均为O(1)	无法直接访问中间元素
实现难度	较为直观	需维护head和tail指针

5.3 队列的扩展类型与实现

5.3.1 优先队列的实现原理

优先队列是一种特殊的队列结构，其中每个元素都有一个“优先级”，出队时总是取出优先级最高的元素。常见的实现方式是使用 堆（Heap）结构 ，尤其是 二叉堆 。

实现思路：

• 使用最小堆或最大堆来管理元素。
• 插入元素时，按优先级调整堆结构。
• 取出元素时，取堆顶元素（优先级最高）。

C#中使用 SortedSet<T> 或自定义堆结构实现：

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap = new List<T>();

    public void Enqueue(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T Dequeue()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("队列为空");

        T root = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        if (heap.Count > 0)
        {
            HeapifyDown(0);
        }

        return root;
    }

    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (heap[index].CompareTo(heap[parentIndex]) >= 0)
                break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void HeapifyDown(int index)
    {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallestIndex = index;

        if (leftChildIndex < heap.Count && heap[leftChildIndex].CompareTo(heap[smallestIndex]) < 0)
            smallestIndex = leftChildIndex;

        if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[smallestIndex]) < 0)
            smallestIndex = rightChildIndex;

        if (smallestIndex != index)
        {
            Swap(index, smallestIndex);
            HeapifyDown(smallestIndex);
        }
    }

    private void Swap(int i, int j)
    {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public bool IsEmpty()
    {
        return heap.Count == 0;
    }
}

逻辑分析与参数说明：

• 使用 List<T> 模拟堆结构。
• Enqueue 将元素插入堆尾并向上调整。
• Dequeue 取出堆顶元素并向下调整。
• 时间复杂度：插入和删除均为O(log n)，优于线性查找。

5.3.2 双端队列的结构设计

双端队列（Deque, Double-Ended Queue）允许在队列的两端进行插入和删除操作，适用于需要双向操作的场景，如回文检测、滑动窗口问题等。

实现方式：

• 使用数组或双向链表实现。
• 支持 AddFirst 、 AddLast 、 RemoveFirst 、 RemoveLast 等操作。

C#中使用 LinkedList<T> 实现：

public class Deque<T>
{
    private LinkedList<T> list = new LinkedList<T>();

    public void AddFirst(T item)
    {
        list.AddFirst(item);
    }

    public void AddLast(T item)
    {
        list.AddLast(item);
    }

    public T RemoveFirst()
    {
        if (list.Count == 0)
            throw new InvalidOperationException("队列为空");

        T value = list.First.Value;
        list.RemoveFirst();
        return value;
    }

    public T RemoveLast()
    {
        if (list.Count == 0)
            throw new InvalidOperationException("队列为空");

        T value = list.Last.Value;
        list.RemoveLast();
        return value;
    }

    public T PeekFirst()
    {
        return list.First.Value;
    }

    public T PeekLast()
    {
        return list.Last.Value;
    }

    public bool IsEmpty()
    {
        return list.Count == 0;
    }
}

逻辑分析与参数说明：

• 使用C#内置的 LinkedList<T> 实现双向操作。
• 提供 AddFirst/Last 和 RemoveFirst/Last 方法，支持双向操作。
• 时间复杂度：插入和删除均为O(1)，查找也为O(1)。

5.4 C#标准库中的Queue类应用

5.4.1 Queue 的基本操作

C#标准库提供了泛型队列类 Queue<T> ，封装了队列的基本操作，开发者无需手动实现。

常用方法：

方法名	描述
Enqueue(T)	添加元素到队列尾部
Dequeue()	移除并返回队列头部元素
Peek()	返回队列头部元素但不移除
Clear()	清空队列
Contains(T)	判断队列是否包含某元素
ToArray()	将队列转换为数组

示例代码：

Queue<int> queue = new Queue<int>();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);

Console.WriteLine(queue.Dequeue()); // 输出10
Console.WriteLine(queue.Peek());    // 输出20
Console.WriteLine(queue.Count);     // 输出2

5.4.2 在任务调度与消息队列系统中的应用

在实际开发中，队列结构被广泛用于任务调度系统和消息队列系统中。例如：

• 多线程任务调度 ：线程池中的任务队列用于管理待执行任务。
• 异步消息处理 ：如RabbitMQ、Kafka等消息中间件中使用队列实现消息的生产与消费。
• 事件驱动系统 ：UI事件、日志事件等按顺序处理。

示例：多线程任务队列实现

class TaskQueue
{
    private Queue<Action> tasks = new Queue<Action>();
    private object lockObj = new object();
    private bool isRunning = true;

    public void EnqueueTask(Action task)
    {
        lock (lockObj)
        {
            tasks.Enqueue(task);
        }
    }

    public void Start()
    {
        Task.Run(() =>
        {
            while (isRunning)
            {
                Action task = null;
                lock (lockObj)
                {
                    if (tasks.Count > 0)
                    {
                        task = tasks.Dequeue();
                    }
                }

                task?.Invoke();
            }
        });
    }

    public void Stop()
    {
        isRunning = false;
    }
}

逻辑分析与参数说明：

• 使用 Queue<Action> 存储任务。
• 多线程访问时通过 lock 保证线程安全。
• 使用 Task.Run 创建后台线程不断取出任务执行。
• Stop() 方法用于停止任务调度。

通过本章内容，我们系统性地学习了队列的基本原理、数组和链表实现方式、优先队列和双端队列的结构设计，以及C#标准库中 Queue<T> 类的使用场景与实际应用。下一章我们将进入树结构的学习，探索其在数据组织与遍历中的强大能力。

6. 树结构详解与二叉搜索树实现

6.1 树的基本概念与术语

6.1.1 树的定义与基本结构

树（Tree）是一种非线性的数据结构，它由一组节点组成，其中有一个称为“根（Root）”的特殊节点，其余节点通过边连接，形成层次分明的结构。树结构具有以下基本特征：

• 每个节点最多只有一个父节点。
• 根节点没有父节点。
• 除根节点外，每个节点都有一个父节点。
• 树中没有环路。

树结构广泛应用于文件系统、数据库索引、决策系统、编译器语法分析等多个领域。

6.1.2 子树、节点、叶子与度的概念

以下是树结构中的常用术语：

术语	含义说明
根节点	树的最顶层节点
子树	某个节点及其所有后代构成的结构
叶子节点	没有子节点的节点
内部节点	至少有一个子节点的节点
节点的度	该节点拥有的子节点数目
树的深度	从根节点到最远叶子节点的最长路径长度

例如，以下是一个树结构的示意图：

graph TD
    A[Root] --> B
    A --> C
    A --> D
    B --> E
    B --> F
    D --> G
    G --> H

其中：

• 根节点是 A。
• E、F、H 是叶子节点。
• B 的子树包括 E、F。
• G 的度为 1，H 的度为 0。
• 树的最大深度为 3（A → G → H）。

6.2 二叉树的基本结构与遍历方式

6.2.1 二叉树的定义与存储结构

二叉树（Binary Tree）是一种每个节点最多有两个子节点的树结构，通常称为“左子节点”和“右子节点”。

在 C# 中，二叉树的节点可以用类来表示：

public class BinaryTreeNode
{
    public int Value { get; set; }
    public BinaryTreeNode Left { get; set; }
    public BinaryTreeNode Right { get; set; }

    public BinaryTreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

6.2.2 先序、中序、后序遍历的递归与非递归实现

二叉树的三种基本遍历方式如下：

• 先序遍历（Pre-order） ：访问根节点 → 遍历左子树 → 遍历右子树
• 中序遍历（In-order） ：遍历左子树 → 访问根节点 → 遍历右子树
• 后序遍历（Post-order） ：遍历左子树 → 遍历右子树 → 访问根节点

递归实现：

public void PreOrderTraversal(BinaryTreeNode node)
{
    if (node == null) return;
    Console.Write(node.Value + " "); // 访问根节点
    PreOrderTraversal(node.Left);    // 左子树
    PreOrderTraversal(node.Right);   // 右子树
}

public void InOrderTraversal(BinaryTreeNode node)
{
    if (node == null) return;
    InOrderTraversal(node.Left);
    Console.Write(node.Value + " ");
    InOrderTraversal(node.Right);
}

public void PostOrderTraversal(BinaryTreeNode node)
{
    if (node == null) return;
    PostOrderTraversal(node.Left);
    PostOrderTraversal(node.Right);
    Console.Write(node.Value + " ");
}

非递归实现（使用栈）：

public void PreOrderTraversalIterative(BinaryTreeNode root)
{
    if (root == null) return;
    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        BinaryTreeNode node = stack.Pop();
        Console.Write(node.Value + " ");

        if (node.Right != null)
            stack.Push(node.Right);
        if (node.Left != null)
            stack.Push(node.Left);
    }
}

该实现通过栈模拟递归调用顺序，保证先访问根节点，再左子树，最后右子树。

6.3 二叉搜索树（BST）的实现

6.3.1 BST的性质与插入操作

二叉搜索树（Binary Search Tree, BST） 是一种特殊的二叉树，具有以下性质：

• 对于任意节点，其左子树中所有节点的值均小于该节点的值；
• 其右子树中所有节点的值均大于该节点的值；
• 左右子树也必须是二叉搜索树。

BST 的插入操作遵循以下规则：

1. 若插入值小于当前节点值，则进入左子树；
2. 若插入值大于当前节点值，则进入右子树；
3. 找到空位后插入新节点。

代码实现如下：

public class BST
{
    public BinaryTreeNode Root { get; private set; }

    public void Insert(int value)
    {
        Root = InsertNode(Root, value);
    }

    private BinaryTreeNode InsertNode(BinaryTreeNode node, int value)
    {
        if (node == null)
            return new BinaryTreeNode(value);

        if (value < node.Value)
            node.Left = InsertNode(node.Left, value);
        else if (value > node.Value)
            node.Right = InsertNode(node.Right, value);

        return node;
    }
}

6.3.2 BST的查找与删除操作

查找操作 非常直观：从根节点开始，根据目标值与当前节点比较决定进入左或右子树，直到找到目标或为空。

public bool Search(int value)
{
    return SearchNode(Root, value);
}

private bool SearchNode(BinaryTreeNode node, int value)
{
    if (node == null)
        return false;

    if (value == node.Value)
        return true;
    else if (value < node.Value)
        return SearchNode(node.Left, value);
    else
        return SearchNode(node.Right, value);
}

删除操作 较为复杂，分为三种情况：

1. 叶子节点 ：直接删除；
2. 只有一个子节点 ：用子节点替代被删除节点；
3. 有两个子节点 ：找到右子树中的最小节点（或左子树中的最大节点），用其值替换被删除节点，并删除该最小节点。

public void Delete(int value)
{
    Root = DeleteNode(Root, value);
}

private BinaryTreeNode DeleteNode(BinaryTreeNode node, int value)
{
    if (node == null)
        return null;

    if (value < node.Value)
        node.Left = DeleteNode(node.Left, value);
    else if (value > node.Value)
        node.Right = DeleteNode(node.Right, value);
    else
    {
        // 单个或无子节点
        if (node.Left == null)
            return node.Right;
        else if (node.Right == null)
            return node.Left;

        // 两个子节点：找到右子树最小节点
        node.Value = MinValue(node.Right);
        node.Right = DeleteNode(node.Right, node.Value);
    }
    return node;
}

private int MinValue(BinaryTreeNode node)
{
    int minValue = node.Value;
    while (node.Left != null)
    {
        minValue = node.Left.Value;
        node = node.Left;
    }
    return minValue;
}

6.3.3 BST的平衡问题与优化思路

BST 的性能取决于树的高度。在最坏情况下（如数据有序插入），BST 会退化为链表，导致查找、插入、删除操作的时间复杂度上升到 O(n)。为了解决这一问题，引入了 平衡二叉搜索树 ，如 AVL 树、红黑树等。

常见的优化思路包括：

• 插入或删除时自动调整树的结构，保持左右子树高度差不超过1（AVL树）；
• 通过颜色标记节点，确保路径长度差异在可控范围内（红黑树）；
• 使用 B 树、B+ 树来适应大规模数据和磁盘读写需求。

6.4 树结构在C#中的实际应用

6.4.1 文件系统结构的模拟实现

树结构非常适合用于模拟文件系统的层级结构。每个节点代表一个文件夹或文件，子节点代表该文件夹下的内容。

public class FileSystemNode
{
    public string Name { get; set; }
    public List<FileSystemNode> Children { get; set; }

    public FileSystemNode(string name)
    {
        Name = name;
        Children = new List<FileSystemNode>();
    }

    public void AddChild(FileSystemNode child)
    {
        Children.Add(child);
    }
}

示例使用：

var root = new FileSystemNode("C:");
var programFiles = new FileSystemNode("Program Files");
var windows = new FileSystemNode("Windows");

root.AddChild(programFiles);
root.AddChild(windows);

var notepad = new FileSystemNode("notepad.exe");
programFiles.AddChild(notepad);

// 遍历文件系统结构
void Traverse(FileSystemNode node, int depth = 0)
{
    Console.WriteLine(new string('-', depth) + " " + node.Name);
    foreach (var child in node.Children)
    {
        Traverse(child, depth + 2);
    }
}

Traverse(root);

输出结果如下：

 C:
  -- Program Files
    ---- notepad.exe
  -- Windows

6.4.2 决策树与表达式树的应用示例

决策树常用于分类与预测任务，例如判断贷款申请是否通过：

graph TD
    A[收入 > 10k?] -->|是| B[信用评级?]
    A -->|否| C[拒绝]
    B -->|高| D[通过]
    B -->|低| E[拒绝]

在 C# 中，可以使用树结构来构建表达式树，用于动态生成代码逻辑：

ParameterExpression param = Expression.Parameter(typeof(int), "x");
ConstantExpression five = Expression.Constant(5);
BinaryExpression body = Expression.GreaterThan(param, five);
Expression<Func<int, bool>> lambda = Expression.Lambda<Func<int, bool>>(body, param);
Func<int, bool> func = lambda.Compile();

Console.WriteLine(func(10));  // 输出 True

表达式树可用于构建动态查询、LINQ 表达式解析、规则引擎等高级功能。

本文还有配套的精品资源，点击获取

简介：数据结构与算法是计算机科学的基石，掌握它们对于编写高效、优化的程序至关重要。本文档围绕C#语言，系统讲解了数组、链表、栈、队列、树、图等常用数据结构，以及排序、查找、图算法等核心算法，并结合实际开发场景说明其应用价值。配套代码资源涵盖各类结构与算法的完整实现，是C#开发者提升编程能力、应对复杂问题的重要学习资料。

本文还有配套的精品资源，点击获取