0

首先，这是一个学校作业，所以那里。如果不是因为我真的很伤心寻求帮助，我就不会发帖了。

现在我们有了这个我们应该实现的二叉搜索树。基本上，下面这节课就完成了，我给理解一下。

    public class BinarySearchTree<T> where T : IComparable<T>
{
    BinarySearchTreeNode<T> _root;

    public BinarySearchTreeNode<T> Root
    {
        get { return _root; }
    }

    public BinarySearchTree()
    {

    }

    public BinarySearchTree(BinarySearchTreeNode<T> root)
    {
        _root = root;
    }

    public void Insert(T value)
    {
        if (_root != null)
            _root.Insert(value);
        else
            _root = new BinarySearchTreeNode<T>(value);
    }

    public void Remove(T value)
    {
        if (_root == null)
            return;

        if (_root.LeftChild != null || _root.RightChild != null)
        {
            _root.Remove(value);
        }
        else if (_root.Value.CompareTo(value) == 0)
        {
            _root = null;
        }
    }

    public bool Find(T value)
    {
        if (_root != null)
            return _root.Find(value);
        else
            return false;
    }

}

这里是我应该实现的类，或者至少就我所知。

public class BinarySearchTreeNode<T> where T : IComparable<T>
{
    private T _value;
    public T Value 
    {
        get { return _value; }
    }

    public BinarySearchTreeNode<T> LeftChild
    {
        get { return _leftChild; }
        set { _leftChild = value; }
    }
    private BinarySearchTreeNode<T> _leftChild, _parent, _rightChild;

    public BinarySearchTreeNode<T> RightChild
    {
        get { return _rightChild; }
        set { _rightChild = value; }
    }

    public BinarySearchTreeNode<T> Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }

    public BinarySearchTreeNode(T value)
    {
        _value = value;
        Parent = this;
    }

    public void Insert(T value)
    {
        if (value.CompareTo(Parent.Value) < 0)
        {

            if (LeftChild != null)
            {
                LeftChild.Insert(value);
             }
            else
            {
                LeftChild = new BinarySearchTreeNode<T>(value);
                LeftChild.Parent = this;
            }

        }
        else if (Value.CompareTo(Parent.Value) >= 0)
        {
            if (RightChild != null)
                RightChild.Insert(value);
            else{
                RightChild = new BinarySearchTreeNode<T>(value); 
                Righthild.Parent = this;
                }
        }

    }

    public void Remove(T value) 
    {



        if (LeftChild != null)
            if (value.CompareTo(Parent.Value) < 0)
                    LeftChild.Remove(value);

            else if (RightChild != null)
                if (value.CompareTo(Parent.Value) >= 0)
                    RightChild.Remove(value);
    }


    public bool Find(T value)
    {
        if (value.Equals(Parent.Value)) 
            return true;

        else if (value.CompareTo(Parent.Value) < 0)
        {
            if (LeftChild != null)
                return LeftChild.Find(value);
        }
        else if (value.CompareTo(Parent.Value) > 0)
        {
            if (RightChild != null)
                return RightChild.Find(value);
        }

        return false;
    }

}

问题是我似乎不太了解我应该如何正确实施删除，以便我可以简单地通过指向父母来删除一个节点，例如。任何帮助或提示表示赞赏。

编辑（！）

所以我几乎把所有东西都整理好了，只剩下一件事，那就是 remove 方法的案例 2。

            //Case 2: If node has only one child, copy the value of the child to your node, and assign LeftChild or RightChild to null (as is the case)   
            if (RightChild != null && LeftChild == null)
            {
                if (value.CompareTo(this.Parent._value) > 0)
                {
                    Parent.RightChild = RightChild;
                    RightChild = null;
                }
            }
            if (RightChild == null && LeftChild != null)
            {
                if (value.CompareTo(Parent._value) < 0)
                {
                Parent.LeftChild = LeftChild;
                LeftChild = null;
                }
            }

基本上，我完全无法替换原来的节点。如果我有 4 - 3 - 2 （预购）并且我想删除 3，那么我可以这样做并获得 4 - 2。但是，如果我想删除 4 ，它不会做任何事情，尽管它只有一个孩子。我认为那是因为它没有父母，但我不确定如何解决这个问题。有任何想法吗？

4

2 回答 2

0

二叉搜索树

需要考虑三种可能的情况： 删除叶子（没有子节点的节点）：删除叶子很容易，因为我们可以简单地将其从树中删除。删除具有一个子节点的节点：删除节点并将其替换为其子节点。删除有两个子节点的节点：将要删除的节点称为 N。不要删除 N。而是选择它的有序后继节点或它的有序前驱节点 R。将 N 的值替换为 R 的值，然后删除 R。

在此处输入图像描述

于 2013-04-19T00:28:53.450 回答
0

在您的 remove 方法中再添加一个条件，其伪代码为：

    if (value.CompareTo(Parent.Value) == 0){
        //Case 1: If node has no children, then make Parent = null
        // Case 2: If node has only one child, copy the value of the child to your node, and assign LeftChild or RightChild to null (as is the case)
        //Case 3: Find the in-order successor, copy its value to the current node and delete the in-order successor.

    }
于 2013-04-19T00:38:15.147 回答