arbre de recherche binaire java

Question

J'ai une question sur comment pourrais-je supprimer un enfant d'un nœud (racine)? Puisque je ne peux pas appeler retirer, si je fais l'hypothèse nulle de l'enfant, seront les enfants de cet enfant monter? Comme, je voudrais simplement initialiser comme nul ?? Ou devrais-je indiquer à l'enfant de l'enfant?

Answer 1

Dans un arbre binaire de recherche traditionnel, la suppression d'un nœud peut avoir des conséquences différentes en fonction du nombre d'enfants du nœud a:

• Un noeud sans enfant peut simplement être supprimé
• Un nœud avec un enfant peut être retiré, et le nœud sera remplacé par son seul enfant. Cela vaut indépendamment du fait que l'enfant est un enfant gauche ou à droite.
• Un nœud avec deux enfants a un peu règle plus compliquée: il faut trouver le successeur en ordre ou dans l'ordre prédécesseur du nœud à supprimer, remplacer la valeur du nœud actuel avec sa valeur de son sucessor ou de son prédécesseur, puis supprimez le successeur ou de son prédécesseur (selon ces règles).

Answer 2

Est-ce devoir? Rien de mal à cela ... nous aimons juste aider les gens à apprendre plutôt que de leur dire les réponses.

Si vous définissez juste le nœud enfant vous null perdrez toutes les informations sur les Childs enfants.

Answer 3

Une classe d'arbre classique saura ses enfants, le plus souvent coincés dans un tableau ou une collection - dans le cas d'un arbre binaire, vous avez seulement deux enfants directs, donc un tableau de taille fixe fonctionne. En raison de cela, ils mettent généralement en œuvre une sorte de méthode « removeMe » que l'enfant appelle à se radiées de la liste des enfants.

Comme mentionné ci-dessus, cela devient compliqué si l'enfant que vous retirez a des enfants.

Answer 4

La réponse de Tim semble mieux. Mais oui, vous voulez faire une des trois choses selon le type de l'enfant, il est votre deplacement. Si vous faites un enfant nul, les enfants de celui-ci ne se déplaceront pas parce que vous avez perdu référence à eux. Au lieu de cela, vous aurez envie de déterminer si les enfants gauche ou à droite de l'enfant votre deplacement doit être réglé sur le pointeur vers l'enfant votre deplacement. Après avoir défini la précédente noeuds pointeur (gauche ou droite) à l'enfant (à gauche ou à droite) du nœud votre deplacement, vous avez l'habitude de plus une référence à ce nœud, il ne ya donc pas besoin de le mettre à null (vous pouvez » accès t plus. A moins que vous avez écrit une sorte de BST doublement lié, dans ce cas, ce n'est pas le BST classique)

Answer 5

Ce code devrait vous aider

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

Vous pouvez faire quelque chose comme ça (code pseudo):

Étant donné une la racine de l'arbre « root » et le nœud à supprimer ou certaines données « x » procédez comme suit

 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;

}