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 を適切に実装する方法を理解できないように見えることです。ヘルプやヒントをいただければ幸いです。

編集（！）

したがって、remove メソッドのケース 2 である 1 つのことを除いて、ほとんどすべてを順番に取得しました。

            //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

2 に答える 2

0

疑似コードが次の remove メソッドにもう 1 つの条件を追加します。

    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 に答える