二元搜索樹刪除參考父母

Question

首先，這是一個學校的任務，所以在那裏。如果不是因爲我真的很傷心尋求幫助，我不會發布信息。

現在我們有這個二叉搜索樹，我們應該實現。基本上，這個類下面是完整的，我明白了。

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，它不會做任何事情，儘管它只有一個孩子。我認爲這是因爲它沒有父母，但我不確定如何解決這個問題。有任何想法嗎？

Answer 1

Binary Search Tree

有三種可能的情況來考慮： 刪除葉（節點無子女）：刪除葉是容易的，因爲我們可以簡單地從樹中刪除它。 刪除一個孩子的節點：刪除該節點並將其替換爲其子節點。 刪除一個有兩個子節點的節點：調用要刪除的節點N.不要刪除N.而是選擇其有序的後繼節點或其有序的前任節點R。將N的值替換爲值R，然後刪除R.

Answer 2

添加一個條件你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. 

    }