C#实现二叉查找树

什么是二叉查找树

二叉查找树（Binary Search Tree）也称为二叉搜索树，简称BST。它是一种基于二分查找思想的非线性数据结构，由多个节点组成，每个节点包含一个键值，同时有两个指针分别指向左右子节点，满足以下性质：

1. 左子树上所有节点的键值小于它的根节点的键值。
2. 右子树上所有节点的键值大于它的根节点的键值。
3. 左右子树也必须是二叉查找树。

因此，二叉查找树在查找、插入、删除等操作上具有高效性。

C#实现二叉查找树

定义节点

首先，我们需要定义二叉查找树的节点类，其中包括三个字段：节点的键值、左子节点、右子节点。

class BSTNode<T>
{
    public T Key { get; set; }
    public BSTNode<T> Left { get; set; }
    public BSTNode<T> Right { get; set; }
}

插入节点

插入节点分两种情况：树为空或树不为空。当树为空时，只需要新建一个节点，并将该节点作为二叉查找树的根节点；当树不为空时，需要在树中找到插入位置。具体操作如下：

1. 从根节点开始查找（初始化为根节点）。
2. 如果插入节点的键值小于当前节点的键值，则继续在当前节点的左子树上查找，否则在右子树上查找。
3. 重复上述操作，直到找到插入位置（左子树或右子树为空）。
4. 将新节点插入到该位置。

class BST<T> where T : IComparable<T>
{
    private BSTNode<T> root;

    public void Insert(T key)
    {
        BSTNode<T> node = new BSTNode<T> { Key = key };

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

        BSTNode<T> current = root;
        while (true)
        {
            if (node.Key.CompareTo(current.Key) < 0)
            {
                if (current.Left == null)
                {
                    current.Left = node;
                    return;
                }

                current = current.Left;
            }
            else
            {
                if (current.Right == null)
                {
                    current.Right = node;
                    return;
                }

                current = current.Right;
            }
        }
    }
}

查找节点

查找节点同样分两种情况：树为空或树不为空。当树为空时，节点不存在；当树不为空时，需要在树中查找。具体操作如下：

1. 从根节点开始查找（初始化为根节点）。
2. 如果查找键值小于当前节点的键值，则继续在当前节点的左子树上查找，否则在右子树上查找。
3. 重复上述操作，直到找到对应节点或到达叶节点。

class BST<T> where T : IComparable<T>
{
    // ...

    public bool Search(T key)
    {
        BSTNode<T> current = root;
        while (current != null)
        {
            if (key.CompareTo(current.Key) == 0)
            {
                return true;
            }
            else if (key.CompareTo(current.Key) < 0)
            {
                current = current.Left;
            }
            else
            {
                current = current.Right;
            }
        }

        return false;
    }
}

示例说明

下面给出两个插入操作的示例：

BST<int> bst = new BST<int>();
bst.Insert(5);
bst.Insert(3);
bst.Insert(7);
bst.Insert(1);
bst.Insert(9);

插入后的二叉查找树如下：

          5
       /     \
      3       7
     /       / \
    1       9   null
   / \
null null

下面给出一个查找操作的示例：

bool exist = bst.Search(3);
if (exist)
{
    Console.WriteLine("Node 3 exists.");
}
else
{
    Console.WriteLine("Node 3 does not exist.");
}

输出结果是Node 3 exists.。