c#平衡二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了c#平衡二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在 C# 中实现平衡二叉树可以使用 AVL 树或红黑树等算法。下面我将展示一个简单的 AVL 树的实现。

首先，我们需要定义一个节点类 AVLNode 用于表示 AVL 树的节点：

class AVLNode
{
    public int data;
    public int height;
    public AVLNode left;
    public AVLNode right;

    public AVLNode(int value)
    {
        data = value;
        height = 1;
        left = null;
        right = null;
    }
}

然后，我们创建一个 AVL 树类 AVLTree，实现插入、删除和平衡等操作：

class AVLTree
{
    private AVLNode root;

    public AVLTree()
    {
        root = null;
    }

    public int Height(AVLNode node)
    {
        if (node == null)
        {
            return 0;
        }
        return node.height;
    }

    public int GetBalanceFactor(AVLNode node)
    {
        if (node == null)
        {
            return 0;
        }
        return Height(node.left) - Height(node.right);
    }

    public AVLNode RotateRight(AVLNode y)
    {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = 1 + Math.Max(Height(y.left), Height(y.right));
        x.height = 1 + Math.Max(Height(x.left), Height(x.right));

        return x;
    }

    public AVLNode RotateLeft(AVLNode x)
    {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = 1 + Math.Max(Height(x.left), Height(x.right));
        y.height = 1 + Math.Max(Height(y.left), Height(y.right));

        return y;
    }

    public AVLNode Insert(AVLNode node, int value)
    {
        if (node == null)
        {
            return new AVLNode(value);
        }

        if (value < node.data)
        {
            node.left = Insert(node.left, value);
        }
        else if (value > node.data)
        {
            node.right = Insert(node.right, value);
        }
        else
        {
            // Duplicate values are not allowed in AVL tree
            return node;
        }

        node.height = 1 + Math.Max(Height(node.left), Height(node.right));

        int balance = GetBalanceFactor(node);

        if (balance > 1 && value < node.left.data)
        {
            return RotateRight(node);
        }

        if (balance < -1 && value > node.right.data)
        {
            return RotateLeft(node);
        }

        if (balance > 1 && value > node.left.data)
        {
            node.left = RotateLeft(node.left);
            return RotateRight(node);
        }

        if (balance < -1 && value < node.right.data)
        {
            node.right = RotateRight(node.right);
            return RotateLeft(node);
        }

        return node;
    }

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

    public void InOrderTraversal(AVLNode node)
    {
        if (node != null)
        {
            InOrderTraversal(node.left);
            Console.Write(node.data + " ");
            InOrderTraversal(node.right);
        }
    }
}