C＃二进制搜索树 删除

Question

我正在尝试从二进制搜索树中删除项目。我可以插入数字以及其他可以正常工作的函数来查找树的高度和大小，但是我无法使代码删除函数正常工作。

我已经确定了必要时需要合并子树，并将最小的数字（最小的项）设置为新节点，但是我目前无法使其正常工作）>

提前感谢您的帮助。

我目前拥有的代码：

主要：

static void Main(string[] args)
    {
        BSTree<int> testTree = new BSTree<int>();

        testTree.InsertItem(6);
        testTree.InsertItem(12);
        testTree.InsertItem(1);

        testTree.RemoveItem(12);
    }
BinTree：

class BinTree<T> where T : IComparable
{
    protected Node<T> root;

    public BinTree()
    {
        root = null;
    }
    public BinTree(Node<T> node)
    {
        root = node;
    }
节点：

class Node<T> where T : IComparable
{
    private T data;
    public Node<T> Left, Right;

    public Node(T item)
    {
        data = item;
        Left = null;
        Right = null;
    }
    public T Data
    {
        set { data = value; }
        get { return data; }
    }
}
BSTree：

class BSTree<T> : BinTree<T> where T:IComparable
{
    public BSTree()
    {
        root = null;
    }
    public void InsertItem(T item)
    {
        insertItem(item, ref root);
    }
    private void insertItem(T item, ref Node<T> tree)
    {
        if (tree == null)
            tree = new Node<T>(item);
        else if (item.CompareTo(tree.Data) < 0)
            insertItem(item, ref tree.Left);
        else if (item.CompareTo(tree.Data) > 0)
            insertItem(item, ref tree.Right);
    }
    public void RemoveItem(T item)
    {
        removeItem(item, ref root);
    }
    private void removeItem(T item, ref Node<T> tree)
    {
        if (tree == null)
            tree = new Node<T>(item);
        if (item.CompareTo(tree.Data) < 0)
            removeItem(item, ref tree.Left);
        else if (item.CompareTo(tree.Data) > 0)
            removeItem(item, ref tree.Right);
        if (tree.Left == null)
            tree = tree.Right;
        else if (tree.Right == null)
            tree = tree.Left;

        T newRoot = leastItem(tree.Right);
        tree.Data = newRoot;
        removeItem(newRoot, ref tree.Right);
    }
    public T leastItem(Node<T> tree) //returns left most item in tree
    {
        if (tree.Left == null) //if tree.Left is empty
            return tree.Data;
        else
        {
            return leastItem(tree.Left);
        }
    }

我正在尝试从二进制搜索树中删除项目。我可以插入数字以及其他可以正常工作的功能来查找树的高度和大小，但是我无法获得代码删除功能...

Answer 1

这是一个基于您的符号的有效示例。