来一份C#版的四叉树源码

在C#中，我们可以创建一个简单的四叉树（Quadtrees）数据结构。下面是一个基本的四叉树类的实现，包括节点添加、划分和查询等操作：

public class QuadTree<T> where T : IComparable<T>
{
    private Node root;
    private int width, height;

    public QuadTree(int width, int height)
    {
        this.width = width;
        this.height = height;
        root = new Node(null);
    }

    // 节点类
    private class Node
    {
        public T Data { get; set; }
        public Node[] Children { get; } = new Node[4];

        public Node(T data)
        {
            Data = data;
        }

        public void Split()
        {
            if (Children.Any(n => n == null))
            {
                for (int i = 0; i < 4; i++)
                {
                    if (Children[i] == null)
                    {
                        var splitData = SplitData(Data);
                        Children[i] = new Node(splitData[i]);
                    }
                }
            }
        }

        // 数据划分策略，这里简单地按中心点将数据分为四个部分
        private static T[] SplitData(T data)
        {
            return new[] { data / 2, data * 3 / 2, data - data / 2, data + data / 2 };
        }
    }

    // 添加元素到树
    public void Insert(T value)
    {
        root.Split();
        root.Data = value;
        InsertRecursively(root, value);
    }

    // 递归插入函数
    private void InsertRecursively(Node node, T value)
    {
        if (value.CompareTo(node.Data) < 0)
        {
            if (node.Children[0] != null)
                InsertRecursively(node.Children[0], value);
            else
                node.Children[0] = new Node(value);
        }
        else if (value.CompareTo(node.Data) > 0)
        {
            if (node.Children[2] != null)
                InsertRecursively(node.Children[2], value);
            else
                node.Children[2] = new Node(value);
        }
        else
            return; // 如果值相等，不做处理

        // 划分节点
        node.Split();
    }

    // 查询节点是否存在特定值
    public bool Contains(T value)
    {
        return FindNode(root, value) != null;
    }

    // 递归查找节点
    private Node FindNode(Node node, T value)
    {
        if (node == null || node.Data.Equals(value))
            return node;

        for (int i = 0; i < 4; i++)
        {
            if (node.Children[i] != null && value.CompareTo(node.Children[i].Data) >= 0)
                return FindNode(node.Children[i], value);
        }

        return null;
    }
}

// 示例：创建并使用四叉树
QuadTree<int> quadTree = new QuadTree(10, 10); // 宽度和高度设为10
quadTree.Insert(50);
bool contains = quadTree.Contains(30); // 返回false，因为30不在范围