C#实现二叉排序树代码实例

下面我将详细讲解如何用C#语言实现一个二叉排序树以及代码实现的具体步骤。

什么是二叉排序树？

二叉排序树（Binary Search Tree）是一种二叉树，其中树的每个节点都包含一个关键字，左子树的所有节点的关键字小于当前节点的关键字，而右子树的所有节点的关键字大于当前节点的关键字。

实现步骤

下面是实现二叉排序树的具体步骤：

1. 创建一个树节点类，定义节点的数据类型、左右子树指针和构造函数。

public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data)
    {
        this.data = data;
    }
}

1. 编写二叉排序树类。定义一个根节点来存储整个树，以及实现插入节点、查找节点和删除节点等方法。

public class BinarySearchTree
{
    public TreeNode root;

    public BinarySearchTree()
    {
        root = null;
    }

    public void Insert(int data)
    {
        TreeNode newNode = new TreeNode(data);

        if (root == null)
        {
            root = newNode;
            return;
        }

        TreeNode current = root;
        TreeNode parent = null;

        while (true)
        {
            parent = current;

            if (data < current.data)
            {
                current = current.left;

                if (current == null)
                {
                    parent.left = newNode;
                    break;
                }
            }
            else
            {
                current = current.right;

                if (current == null)
                {
                    parent.right = newNode;
                    break;
                }
            }
        }
    }

    public TreeNode Find(int data)
    {
        if (root == null)
        {
            return null;
        }

        TreeNode current = root;

        while (current != null)
        {
            if (data == current.data)
            {
                return current;
            }

            if (data < current.data)
            {
                current = current.left;
            }
            else
            {
                current = current.right;
            }
        }

        return null;
    }

    public void Delete(int data)
    {
        root = DeleteNode(root, data);
    }

    private TreeNode DeleteNode(TreeNode root, int data)
    {
        if (root == null)
        {
            return null;
        }

        if (data < root.data)
        {
            root.left = DeleteNode(root.left, data);
        }
        else if (data > root.data)
        {
            root.right = DeleteNode(root.right, data);
        }
        else
        {
            if (root.left == null)
            {
                return root.right;
            }
            else if (root.right == null)
            {
                return root.left;
            }

            root.data = FindMin(root.right).data;
            root.right = DeleteNode(root.right, root.data);
        }

        return root;
    }

    private TreeNode FindMin(TreeNode node)
    {
        while (node.left != null)
        {
            node = node.left;
        }

        return node;
    }
}

1. 测试代码。

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

TreeNode node1 = bst.Find(3);
Console.WriteLine(node1.data);    // 3

TreeNode node2 = bst.Find(6);
Console.WriteLine(node2 == null);    // True

bst.Delete(3);
TreeNode node3 = bst.Find(3);
Console.WriteLine(node3 == null);    // True

示例说明

以下是两个示例来说明二叉排序树的使用。

示例1

假设你需要在一个未排序的整数数组中查找最小的数字。你可以将整个数组构造成一个二叉排序树，然后取左子树的最后一个节点作为结果。以下是实现代码：

public int FindMin(int[] arr)
{
    BinarySearchTree bst = new BinarySearchTree();

    foreach (int num in arr)
    {
        bst.Insert(num);
    }

    TreeNode node = bst.root;
    while (node.left != null)
    {
        node = node.left;
    }

    return node.data;
}

示例2

假设你需要检查一个字符串是否是回文。你可以将这个字符串的字符构造成一个二叉排序树，并使用中序遍历来检查是否是回文。以下是实现代码：

public bool IsPalindrome(string str)
{
    BinarySearchTree bst = new BinarySearchTree();

    foreach (char ch in str)
    {
        bst.Insert((int)ch);
    }

    return CheckPalindrome(bst.root, new List<int>());
}

private bool CheckPalindrome(TreeNode node, List<int> list)
{
    if (node != null)
    {
        if (!CheckPalindrome(node.left, list))
        {
            return false;
        }

        list.Add(node.data);

        if (list.Count % 2 == 0 && list[list.Count / 2 - 1] != list[list.Count / 2])
        {
            return false;
        }

        if (!CheckPalindrome(node.right, list))
        {
            return false;
        }
    }

    return true;
}

以上就是用C#实现二叉排序树的攻略，包含了构造节点、定义类、实现方法和两个示例说明。希望对你有帮助。