使用 C# 从二叉树中删除元素

一、介绍

二叉树是一种数据结构，每个节点最多有两个子节点。由于节点的限制，子节点通常被称为左子节点和右子节点。本文将探讨如何构建二叉树，并实现节点的删除操作，以增强对数据结构的理解。最顶层的节点称为树的根。

二、二叉树示例

在这个示例中，我们将创建一棵简单的二叉树，根节点为 50，左子节点为 30，右子节点为 70。节点 30 的左子节点为 20，右子节点为 40。没有任何子节点的节点称为叶节点，因此 20、40、60 和 80 是叶节点。

三、主要功能

3.1 节点类定义

我们首先定义一个节点类，其中包含数据和左右子节点的引用。

class Node
{
    public int data; // 节点存储的数据
    public Node left, right; // 左右子节点

    public Node(int i)
    {
        data = i; // 初始化节点的数据
        left = right = null; // 初始化左右子节点为空
    }
}

3.2 创建树

我们创建一个树类，并在其中设置根节点及其子节点。

class Tree
{
    Node root; // 定义树的根节点

    public Tree()
    {
        root = null; // 初始化树为空
    }
}

3.3 删除节点

要从二叉树中删除节点，需要遵循以下算法：

1. 从根节点开始查找要删除的节点。
2. 找到树中最深的节点。
3. 用最深节点的数据替换要删除的节点。
4. 删除最深的节点。

以下是删除操作的具体实现：

// 删除指定的最深节点
void DeleteDeepest(ref Node root, Node toDelete)
{
    Node temp;
    Queue<Node> q1 = new Queue<Node>(); // 创建队列用于层序遍历
    q1.Enqueue(root); // 将根节点加入队列

    while (q1.Count != 0) // 当队列不为空
    {
        temp = q1.Dequeue(); // 取出队首元素

        // 如果当前节点是要删除的节点
        if (temp == toDelete) 
        {
            root = null; // 如果只有一个元素，直接置空
            break;
        }

        // 如果左子节点不为空，加入队列
        if (temp.left != null) 
        {
            if (temp.left == toDelete) // 如果找到了要删除的左子节点
            {
                temp.left = null; // 删除左子节点
                return;
            }
            q1.Enqueue(temp.left); // 否则加入队列
        }

        // 如果右子节点不为空，加入队列
        if (temp.right != null) 
        {
            if (temp.right == toDelete) // 如果找到了要删除的右子节点
            {
                temp.right = null; // 删除右子节点
                return;
            }
            q1.Enqueue(temp.right); // 否则加入队列
        }
    }
}

// 删除指定节点的主函数
void Delete(ref Node root, int key)
{
    Node temp, nodeToChange; // temp存储当前节点，nodeToChange存储要删除的节点
    temp = nodeToChange = null; // 初始化为空

    Queue<Node> q1 = new Queue<Node>(); // 创建队列进行层序遍历
    q1.Enqueue(root); // 将根节点加入队列

    while (q1.Count != 0) // 当队列不为空
    {
        temp = q1.Dequeue(); // 取出队首元素

        // 如果找到要删除的节点
        if (temp.data == key)
        {
            nodeToChange = temp; // 标记要删除的节点
        }

        // 如果左子节点不为空，加入队列
        if (temp.left != null)
            q1.Enqueue(temp.left);

        // 如果右子节点不为空，加入队列
        if (temp.right != null)
            q1.Enqueue(temp.right);
    }

    if (nodeToChange != null) // 如果找到了要删除的节点
    {
        // temp指向树中最深的节点
        nodeToChange.data = temp.data; // 用最深节点的数据替换要删除的节点
        DeleteDeepest(ref root, temp); // 删除最深节点
    }
}

3.4 主函数

以下是主函数，展示如何使用以上定义的类和方法：

public static void Main()
{
    Tree t1 = new Tree(); // 创建树实例
    t1.root = new Node(50); // 设置根节点为50
    t1.root.left = new Node(30); // 左子节点为30
    t1.root.right = new Node(70); // 右子节点为70
    t1.root.left.left = new Node(20); // 30的左子节点
    t1.root.left.right = new Node(40); // 30的右子节点
    t1.root.right.left = new Node(60); // 70的左子节点
    t1.root.right.right = new Node(80); // 70的右子节点

    t1.PrintPre(t1.root); // 打印删除前的元素
    t1.Delete(ref t1.root, 20); // 删除元素20

    Console.WriteLine(); // 打印换行
    t1.PrintPre(t1.root); // 打印删除后的元素
}

四、控制台输出

运行上述代码后，控制台将输出删除操作前后的二叉树节点值。

五、结论

通过本文的介绍，我们了解了如何构建一个简单的二叉树以及如何实现节点的删除操作。二叉树作为一种重要的数据结构，广泛应用于各种算法和数据处理任务中。掌握二叉树的基本操作将为进一步学习数据结构和算法奠定基础。