0

ノード（ルート）から子を削除するにはどうすればよいですか？removeを呼び出すことができないので、子をnullにすると、その子の子は上に移動しますか？たとえば、nullとして初期化するだけですか？それとも、子供の子供を指さしますか？

4

6 に答える 6

2

従来の二分探索木では、ノードの削除は、ノードの子の数に応じて異なる結果をもたらす可能性があります。

  • 子のないノードは簡単に削除できます
  • 子が1つあるノードは削除でき、ノードはその唯一の子に置き換えられます。これは、子が左または右の子であるかどうかに関係なく適用されます。
  • 2つの子を持つノードには、もう少し複雑なルールがあります。削除するノードの順序どおりの後続または順序付きの先行を見つけ、現在のノードの値を後続または先行の値に置き換えてから、後続または先行を削除する必要があります。 （これらの規則に従って）。
于 2009-10-31T19:49:47.890 に答える
0

標準のツリークラスはその子を認識し、通常は配列またはコレクションにスタックします。バイナリツリーの場合、直接の子は2つしかないため、固定サイズの配列が機能します。そのため、通常、子がその子のリストから削除するために呼び出す、ある種の「removeMe」メソッドを実装します。

上記のように、削除する子に子がある場合、これは複雑になります。

于 2009-10-31T20:33:04.903 に答える
0

これは宿題ですか？それは何も悪いことではありません...私たちは人々が答えを言うのではなく、学ぶのを助けるのが好きです。

子ノードをnullに設定しただけでは、子の子に関する情報はすべて失われます。

于 2009-10-31T19:51:11.733 に答える
0

ティムの答えが一番いいようです。しかし、はい、あなたはそれがあなたの連れ去る子供たちの種類に応じて、3つのことのうちの1つをしたいと思うでしょう。子をnullにすると、子への参照が失われるため、子は上に移動しません。代わりに、削除する子の左または右の子を、削除する子を指すポインタに設定する必要があるかどうかを判断する必要があります。前の'ノードポインタ（左または右）を削除するノードの子（左または右）に設定すると、そのノードへの参照がなくなるため、nullに設定する必要はありません（'もうアクセスしないでください。二重にリンクされたBSTを作成した場合を除き、その場合は従来のBSTではありません）

于 2009-10-31T23:20:04.590 に答える
0

このコードはあなたを助けるはずです

public Node<T> getParentOf(Node<T> child){
    findParentOf(this.root, child);
    return temp;
}

private void findParentOf(Node<T> ROOT, Node<T> child){
    if(ROOT.hasLeft()){
        findParentOf(ROOT.left, child);
    }

    if(ROOT.left == child || root.right == child){
        temp = ROOT;
    }

    if(ROOT.hasRight()){
        findParentOf(ROOT.right, child);
    }
}


private void replaceNode(Node<T> original, Node<T> newNode){
    Node<T> tempParent = getParentOf(original);
    if(original == tempParent.left){
        tempParent.left = newNode;
    }else if(original == tempParent.right){
        tempParent.right = newNode;
    }
}

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){
    newParent.insert(oldParent.data);
    if(oldParent.hasLeft()){
        traverseChildrenAndAdd(newParent,oldParent.left);
    }



    if(oldParent.hasRight()){
        traverseChildrenAndAdd(newParent,oldParent.right);
    }
}
private void deleteNode(Node<T> ROOT, Node<T> d){
    if(d.data.compareTo(ROOT.data) < 0){
        deleteNode(ROOT.left, d);
    }else if(d.data.compareTo(ROOT.data) > 0){
        deleteNode(ROOT.right, d);
    }else if(d == this.root){
        if(this.root.hasLeft()){
            traverseChildrenAndAdd(root.left, root.right);
            root = root.left;
        }else if(root.hasRight()){
            root = root.right;
        }else{
            root = null;
        }
    }else{
        if(ROOT.hasLeft()&&ROOT.hasRight()){
            Node<T> successor = getMinNode(ROOT);
            replaceNode(successor, successor.right);
        }else if(ROOT.hasLeft() || ROOT.hasRight()){
            if(ROOT.hasLeft()){
                replaceNode(ROOT, ROOT.left);
            }else{
                replaceNode(ROOT, ROOT.right);
            }
        }else{
            replaceNode(ROOT, null);
        }
    }
}

public void remove(T data){
    deleteNode(this.root, new Node<T>(data));
}
于 2011-02-13T09:14:15.463 に答える
0

あなたはこのようなことをすることができます（擬似コード）：

ツリーのルート「root」と削除するノードまたは一部のデータ「x」が与えられた場合、次のようにします。

 if x < root
      recurse to left child
 if x > root
      recurse to right child
 else //node found
      find the min item of the node right child //min item should be left most leaf node node
      replace the value of the node you want to delete with min nodes value
      now delete the min node
 return root;

コード：

delete(Node root, Object x){
    if(root == null){
        return null;
    }

    if(data < root.data){
        root = delete(root.left);
    }else if(root.data < data){
        root = delete(root.right);
    }else{
        if(root.left != null && root.right != null){
            Object tmp = findMin(root.right);
            root.data = tmp;
            root.right = delete(root.right, tmp);
        }else{
            return (root.left != null) ? root.left : root.right;    
        }
    }
return root;

}

于 2014-09-09T19:33:58.293 に答える