java binärer Suchbaum

Question

Ich habe eine Frage, wie würde ich ein Kind von einem Knoten (root) entfernen? Da ich entferne nicht anrufen kann, wenn ich das Kind null zu machen, werden die Kinder des Kindes nach oben? Wie würde ich initialisieren es nur als null ?? Oder würde verweise ich auf das Kind Kind?

Answer 1

In einem traditionellen binären Suchbaum, die Entfernung eines Knotens kann unterschiedliche Auswirkungen haben, je nachdem, wie viele Kinder der Knoten:

• Ein Knoten ohne Kinder können einfach entfernt werden
• Ein Knoten mit einem Kind kann entfernt werden, und der Knoten wird durch sein einziges Kind ersetzt werden. Dies gilt unabhängig davon, ob das Kind ein linkes oder rechtes Kind ist.
• Ein Knoten mit zwei Kindern hat eine etwas kompliziertere Regel: Sie müssen die in Ordnung Nachfolger finden oder in Ordnung Vorgänger der Knoten entfernt werden, ersetzen der Wert des aktuellen Knotens mit seinem Nachfolger oder des Vorgängers Wert, dann den Nachfolger oder Vorgänger löschen (nach diesen Regeln).

Answer 2

Ist das Hausaufgaben? Nichts falsch mit dem ... möchten wir nur Menschen und nicht helfen zu lernen, als sie die Antworten erzählen.

Wenn Sie nur die untergeordneten Knoten auf null gesetzt Sie irgendwelche Informationen über den Childs Kinder verlieren.

Answer 3

Eine Standardbaum Klasse wird ihre Kinder wissen, in der Regel in einem Array oder einer Sammlung stecken - im Falle eines binären Baum, nur zwei direkte Kinder haben, so eine feste Größe Array funktioniert. Dieser Grund, sie in der Regel eine Art „removeMe“ Methode implementieren, die das Kind aus dieser Liste von Kindern zu erhalten entfernt nennt.

Wie oben erwähnt, dies kompliziert wird, wenn das Kind den Sie entfernen, Kinder hat.

Answer 4

Tims Antwort scheint am besten. Aber ja wünschen Sie eine von drei Dinge zu tun, je nachdem, welche Art von Kind es ist, zu entfernen. Wenn Sie ein Kind null machen, werden die Kinder es nicht bewegen, weil man auf sie Bezug verloren haben. Stattdessen sollten Sie, wenn die linke oder rechte Kinder des Kindes sollte Ihre Entfernung zu dem Zeiger, der auf das Kind eingestellt werden, um Ihre Entfernung zu bestimmen. Nachdem Sie die vorherigen Knoten Zeiger (links oder rechts), um das Kind (links oder rechts) des Knotens Ihre entfernen, haben Sie nicht einen Verweis mehr auf diesen Knoten, keine Notwendigkeit, so Theres es auf null gesetzt (Sie können‘gesetzt t Zugriff es nicht mehr. es sei denn, Sie irgendeine Art von doppelt verketteten BST schrieb, in dem Fall, dass nicht das klassische BST ist)

Answer 5

Dieser Code soll Ihnen helfen,

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));
}

Answer 6

Sie können so etwas wie dieser (Pseudo-Code) tun:

a die Wurzel des Baumes „root“ gegeben und dem Knoten zu löschen oder einige Daten „x“ gehen Sie wie folgt

 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;

code:

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;

}