二叉树

编程语言的艺术

介绍

最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。除此之外，二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是 O(n)

二叉树的介绍与 C# 实现

1. 二叉树（Binary Tree）简介

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点（Left Child）和右子节点（Right Child）。

基本概念：

根节点（Root）：树的顶层节点，没有父节点。
叶子节点（Leaf）：没有子节点的节点。
深度（Depth）：从根节点到当前节点的路径长度。
高度（Height）：从当前节点到最远叶子节点的路径长度。

常见二叉树类型：

满二叉树（Full Binary Tree）：每个节点都有 0 或 2 个子节点。
完全二叉树（Complete Binary Tree）：除最后一层外，所有层都被填满，且最后一层节点靠左排列。
二叉搜索树（BST, Binary Search Tree）：左子树的所有节点值 ≤ 当前节点值 ≤ 右子树的所有节点值。

2. C# 实现二叉树

(1) 定义二叉树节点类

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

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

(2) 二叉树的遍历（递归方式）

public class BinaryTree
{
    public TreeNode Root { get; set; }

    // 前序遍历（根 → 左 → 右）
    public void PreOrderTraversal(TreeNode node)
    {
        if (node == null) return;
        Console.Write(node.Value + " ");
        PreOrderTraversal(node.Left);
        PreOrderTraversal(node.Right);
    }

    // 中序遍历（左 → 根 → 右）
    public void InOrderTraversal(TreeNode node)
    {
        if (node == null) return;
        InOrderTraversal(node.Left);
        Console.Write(node.Value + " ");
        InOrderTraversal(node.Right);
    }

    // 后序遍历（左 → 右 → 根）
    public void PostOrderTraversal(TreeNode node)
    {
        if (node == null) return;
        PostOrderTraversal(node.Left);
        PostOrderTraversal(node.Right);
        Console.Write(node.Value + " ");
    }

    // 层序遍历（广度优先，使用队列）
    public void LevelOrderTraversal()
    {
        if (Root == null) return;

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(Root);

        while (queue.Count > 0)
        {
            TreeNode current = queue.Dequeue();
            Console.Write(current.Value + " ");

            if (current.Left != null)
                queue.Enqueue(current.Left);
            if (current.Right != null)
                queue.Enqueue(current.Right);
        }
    }
}

(3) 测试代码

class Program
{
    static void Main()
    {
        BinaryTree tree = new BinaryTree();
        tree.Root = new TreeNode(1);
        tree.Root.Left = new TreeNode(2);
        tree.Root.Right = new TreeNode(3);
        tree.Root.Left.Left = new TreeNode(4);
        tree.Root.Left.Right = new TreeNode(5);

        Console.WriteLine("前序遍历:");
        tree.PreOrderTraversal(tree.Root);  // 输出: 1 2 4 5 3

        Console.WriteLine("\n中序遍历:");
        tree.InOrderTraversal(tree.Root);   // 输出: 4 2 5 1 3

        Console.WriteLine("\n后序遍历:");
        tree.PostOrderTraversal(tree.Root); // 输出: 4 5 2 3 1

        Console.WriteLine("\n层序遍历:");
        tree.LevelOrderTraversal();         // 输出: 1 2 3 4 5
    }
}

3. 二叉搜索树（BST）的 C# 实现

public class BinarySearchTree
{
    public TreeNode Root { get; set; }

    // 插入节点
    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private TreeNode InsertRec(TreeNode node, int value)
    {
        if (node == null)
            return new TreeNode(value);

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

        return node;
    }

    // 查找节点
    public bool Search(int value)
    {
        return SearchRec(Root, value);
    }

    private bool SearchRec(TreeNode node, int value)
    {
        if (node == null)
            return false;

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

测试 BST

BinarySearchTree bst = new BinarySearchTree();
bst.Insert(5);
bst.Insert(3);
bst.Insert(7);
bst.Insert(2);
bst.Insert(4);

Console.WriteLine(bst.Search(4)); // 输出: True
Console.WriteLine(bst.Search(6)); // 输出: False

总结

二叉树是每个节点最多有两个子节点的树结构。
C# 实现包括节点定义、遍历（前序、中序、后序、层序）、BST 的插入和查找。
应用场景：数据库索引、文件系统、表达式解析、AI 决策树等。

二叉树的其他

二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。不过，这只是针对没有重复数据的情况。对于存在重复数据的二叉查找树，我介绍了两种构建方法，一种是让每个节点存储多个值相同的数据；另一种是，每个节点中存储一个数据。针对这种情况，我们只需要稍加改造原来的插入、删除、查找操作即可。
在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。

红黑树

红黑树（Red-Black Tree）简介

红黑树是一种自平衡的二叉搜索树（BST），它通过特定的规则确保树的高度近似平衡，从而保证查找、插入、删除等操作的时间复杂度为 O(log n)。

它是由 Rudolf Bayer 和 Volker Strassen 在1972年提出，并由 Leo J. Guibas 和 Robert Sedgewick 在1978年完善。

1. 红黑树的特性

红黑树必须满足以下五个性质：

节点是红色或黑色：每个节点存储一个颜色标记（Red/Black）。
根节点是黑色：树的顶层节点必须是黑色。
叶子节点（NIL节点）是黑色：红黑树的叶子节点是空节点（NIL），视为黑色。
红色节点的子节点必须是黑色（即不能有连续的红色节点）。
从任一节点到其所有叶子节点的路径上，黑色节点的数量相同（称为“黑高”）。

2. 红黑树 vs AVL树

特性	红黑树	AVL树
平衡严格性	较宽松（允许一定不平衡）	更严格（完全平衡）
插入/删除	更快（旋转次数较少）	较慢（可能需要多次旋转）
查找效率	稍慢（树可能稍高）	更快（树更平衡）
适用场景	Java `TreeMap`、C++ `std::map`	数据库索引、高频查找场景

3. 红黑树的操作

(1) 插入（Insertion）

按BST规则插入新节点（初始为红色）。
检查是否违反红黑树性质：
- 如果父节点是黑色，无需调整。
- 如果父节点是红色，需调整（通过旋转+变色）。
调整策略（取决于叔父节点颜色）：
- Case 1：叔父节点是红色 → 重新着色（父、叔变黑，祖父变红）。
- Case 2/3：叔父节点是黑色 → 旋转（左旋/右旋）+ 重新着色。

(2) 删除（Deletion）

按BST规则删除节点。
如果删除的是红色节点，直接移除（不影响黑高）。
如果删除的是黑色节点，需调整（通过旋转+变色）以保持黑高。

4. C# 实现红黑树（简化版）

public enum NodeColor { Red, Black }

public class RedBlackNode<T> where T : IComparable<T>
{
    public T Value { get; set; }
    public NodeColor Color { get; set; }
    public RedBlackNode<T> Left { get; set; }
    public RedBlackNode<T> Right { get; set; }
    public RedBlackNode<T> Parent { get; set; }

    public RedBlackNode(T value, NodeColor color)
    {
        Value = value;
        Color = color;
    }
}

public class RedBlackTree<T> where T : IComparable<T>
{
    private RedBlackNode<T> _root;
    private RedBlackNode<T> _nil; // 表示叶子节点（NIL）

    public RedBlackTree()
    {
        _nil = new RedBlackNode<T>(default, NodeColor.Black);
        _root = _nil;
    }

    // 插入操作
    public void Insert(T value)
    {
        var newNode = new RedBlackNode<T>(value, NodeColor.Red)
        {
            Left = _nil,
            Right = _nil,
            Parent = _nil
        };

        // BST插入逻辑
        RedBlackNode<T> parent = _nil;
        RedBlackNode<T> current = _root;
        while (current != _nil)
        {
            parent = current;
            if (newNode.Value.CompareTo(current.Value) < 0)
                current = current.Left;
            else
                current = current.Right;
        }

        newNode.Parent = parent;
        if (parent == _nil)
            _root = newNode;
        else if (newNode.Value.CompareTo(parent.Value) < 0)
            parent.Left = newNode;
        else
            parent.Right = newNode;

        // 调整红黑树性质
        FixInsert(newNode);
    }

    private void FixInsert(RedBlackNode<T> node)
    {
        while (node.Parent.Color == NodeColor.Red)
        {
            if (node.Parent == node.Parent.Parent.Left)
            {
                var uncle = node.Parent.Parent.Right;
                if (uncle.Color == NodeColor.Red) // Case 1
                {
                    node.Parent.Color = NodeColor.Black;
                    uncle.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    node = node.Parent.Parent;
                }
                else
                {
                    if (node == node.Parent.Right) // Case 2
                    {
                        node = node.Parent;
                        LeftRotate(node);
                    }
                    // Case 3
                    node.Parent.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    RightRotate(node.Parent.Parent);
                }
            }
            else // 对称逻辑（父节点是右孩子）
            {
                // 类似上述逻辑，方向相反
            }
        }
        _root.Color = NodeColor.Black;
    }

    // 左旋（辅助调整）
    private void LeftRotate(RedBlackNode<T> x)
    {
        var y = x.Right;
        x.Right = y.Left;
        if (y.Left != _nil)
            y.Left.Parent = x;
        y.Parent = x.Parent;
        if (x.Parent == _nil)
            _root = y;
        else if (x == x.Parent.Left)
            x.Parent.Left = y;
        else
            x.Parent.Right = y;
        y.Left = x;
        x.Parent = y;
    }

    // 右旋（辅助调整）
    private void RightRotate(RedBlackNode<T> y)
    {
        // 对称于左旋
    }
}

5. 红黑树的应用

C++ STL：std::map、std::set基于红黑树实现。
Java：TreeMap、TreeSet使用红黑树。
数据库索引：如 MySQL 的某些索引结构。
Linux内核：进程调度、内存管理等。

6. 为什么选择红黑树？

插入/删除比AVL树更快（旋转次数更少）。
查找效率仍接近O(log n)，适合动态数据。
广泛应用于工业级代码（如Java/C++标准库）。

红黑树是平衡二叉搜索树的经典实现，适合需要高效动态操作的场景！ 🌟

如果觉得文章对你有用，请随意赞赏

算法数据结构

二叉树

https://xuer.fun/archives/BinaryTree

作者

XUER

发布于

2025-08-19

更新于

2025-08-19

许可协议

CC BY 4.0

二叉树

介绍

​​二叉树的介绍与 C# 实现​​

​​1. 二叉树（Binary Tree）简介​​

​​2. C# 实现二叉树​​

​​(1) 定义二叉树节点类​​

​​(2) 二叉树的遍历（递归方式）​​

​​(3) 测试代码​​

​​3. 二叉搜索树（BST）的 C# 实现​​

​​总结​​

二叉树的其他

红黑树

​​红黑树（Red-Black Tree）简介​​

​​1. 红黑树的特性​​

​​2. 红黑树 vs AVL树​​

​​3. 红黑树的操作​​

​​(1) 插入（Insertion）​​

​​(2) 删除（Deletion）​​

​​4. C# 实现红黑树（简化版）​​

​​5. 红黑树的应用​​

​​6. 为什么选择红黑树？​​

作者

发布于

更新于