J'essaie de gérer un BST en C ++ pour mon objectif académique.

Je n'ai aucun problème à part la fonction DeleteNode, également J'ai choisi d'implémenter cette structure de données avec un class et non avec un struct.

Le problème est que je ne peux pas comprendre comment faire fonctionner correctement la fonction de suppression, souvent j'ai une erreur 0xDDDDDDDDD mon débogueur dit, parfois je peux supprimer le nœud, parfois mon programme plante.

Je pense que c'est un problème possible de pointeur, mais je ne peux tout simplement pas comprendre où je me trompe.

Voici ma fonction de suppression de nœud, celle qui me pose de sérieux problèmes:

EDIT: Le cas de suppression sans fils fonctionne parfaitement , celui qui me rend fou est la suppression de cas à un fils.

 //function that delete a selected node
    void DeleteNode(TreeNode* root,int key) {
        /*we got three case here:*/


        //until we find the right node with value in the tree
        if (root->getValue() != key && root != nullptr) {
            if (root->getValue() > key) {
                DeleteNode(root->Left, key);
            }
            else if (root->getValue() < key) {
                DeleteNode(root->Right, key);
            }
        }
        else { //when we found the right node, then operate 
               /* THIS WORKS PERFECTLY! */

            //first case: our node got no right and left son
            if (!root->Left && !root->Right) {

                TreeNode* tmp = root->Father; 

                if (tmp->Left == root) { //if the son is a left son
                    tmp->Left = nullptr;
                    delete root;
                }
                else if (tmp->Right == root) { //if the son is a right son
                    tmp->Right = nullptr;
                    delete root;
                }

            }
            //second case: our node got a left but no right son
            /* THIS ONE DOESN'T WORK. */
            else if (!root->Right) { 
                TreeNode *tmp = root;
                root = root->Left; //new root is the left son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Left = root; //linking the son to the new father

                delete tmp;                     

                std::cout << "Erased!" << std::endl;
            }
            else if (!root->Left) {
                TreeNode *tmp = root;
                root = root->Right; //new root is the right son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Right = root; //linking the son to the new father

                delete tmp;

                std::cout << "Erased!" << std::endl;

            }
        }


        }

J'ai essayé beaucoup de combinaisons, mais le résultat est le même à chaque fois: il plante à la première occurrence de la fonction d'affichage InOrder. (et quand ce n'est pas le cas, la fonction supprime simplement les premiers nœuds, puis se bloque lorsque j'essaye d'en supprimer un nouveau.)

Voici un élément principal simple dans lequel j'essaye de procéder à la suppression:

int main()
{

    TreeNode root;

    root.insertNode(&root,50);
    root.insertNode(&root,30);
    root.insertNode(&root,20);
    root.insertNode(&root,40);
    root.insertNode(&root,70);
    root.insertNode(&root,60);
    root.insertNode(&root,80);

    for (int i = 0; i < 5; i++) {
        int n;
        cin >> n;

        root.DeleteNode(&root, n);

        cout << "In-Order: "; root.inOrder(&root);
        cout << endl;
        cout << "Pre-Order: "; root.preOrder(&root);
        cout << endl;
        cout << "Post-Order: "; root.postOrder(&root);
        cout << endl;
    }

}

Voici mon code BST complet (sauf celui de suppression que j'ai soumis auparavant, juste pour être plus complet dans la compréhension de mon code)

    class TreeNode {
private:
    int value;
    TreeNode* Left;
    TreeNode* Right;
    TreeNode* Father;

public:

    //constructor
    TreeNode() {
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    TreeNode(int value) {
        this->value = value;
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    //functions
    int getValue() { return value; }
    void setValue(int value) { this->value = value; }


    //function to create a new node and insert a value into it
    TreeNode* insertNode(TreeNode* root, int value) {

        if (root->getValue() == NULL) {
            root->setValue(value);
            root->Father = nullptr;
        }

        else {
            if (value > root->getValue()) {
                if (root->Right) {
                    insertNode(root->Right, value);
                }
                else
                    root->Right = new TreeNode(value);
                    root->Right->Father = root;
            }
            else if (value < root->getValue()) {
                if (root->Left) {
                    insertNode(root->Left, value);
                }
                else
                    root->Left = new TreeNode(value);
                    root->Left->Father = root;
            }

        }
        return root;
    }

    //function to search a value into a BST
    TreeNode* SearchNode(TreeNode* root, int key) {

        if (root->getValue() == key) {
            return root;
        }
        else if (root->getValue() < key) {
            if (root->Right) {
                SearchNode(root->Right, key);
            }
            else return nullptr;
        }
        else if (root->getValue() > key) {
            if (root->Left) {
                SearchNode(root->Left, key);
            }
            else return nullptr;
        }
    }

    //function that return the height of the tree 
    int TreeHeigth(TreeNode* root) {

        int heigth;

        if (root == nullptr) {
            return 0;
        }
        else {
            return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
        }
    }

    //function that returns the number of the nodes
    int CountTreeNode(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        else {
            return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
        }
    }

    //function that returns the minimum values into the tree
    TreeNode* MinimumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Left != nullptr) {
            root = root->Left;
        }

        return root;
    }

    //function that returns the maximum value into the tree  
    TreeNode* MaximumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Right != nullptr) {
            root = root->Right;
        }

        return root;
    }

    //function that returns a successor of a given nodeb
    TreeNode* SuccessorNode(TreeNode* node) {

        //first case: our node got a rigth subtree:
        if (node->Right != nullptr) {
            return MinimumNode(node->Right); 
        }

        //second case: our node doesnt got a right subtree: lets get 
        //upper in the tree until our node isn't a left child.

        TreeNode* Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Right) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

    }

    //function tht returns a predecessor of a given node
    TreeNode* PredecessorNode(TreeNode* node) {

        //first case: (inverse to successor) our node got a left subtree:
        if (node->Left != nullptr) {
            return MaximumNode(node->Left);
        }

        TreeNode* Ancestor;

            if (node->Father == nullptr)
                return nullptr;
            else 
                Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Left) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

        return Ancestor;
    }



    //function that prints information about nodes
    void InfoNode(TreeNode *root) {

        root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
            : std::cout << "Nodo corrente: " << "NULL" << std::endl;

        root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
            : std::cout << "Padre: " << "NULL" << std::endl;

        root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
            : std::cout << "Figlio SX: " << "NULL" << std::endl;

        root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
            : std::cout << "Figlio DX: " << "NULL" << std::endl;
    }

    //visits of a tree
    void preOrder(TreeNode* root) {
        if (root != nullptr) {
            std::cout << root->getValue() << " ";
            preOrder(root->Left);
            preOrder(root->Right);
        }
    }

    void inOrder(TreeNode* root) {
        if (root != nullptr) {
            inOrder(root->Left);
            std::cout << root->getValue() << " ";
            inOrder(root->Right);
        }

    }

    void postOrder(TreeNode *root) {
        if (root != nullptr) {
            postOrder(root->Left);
            postOrder(root->Right);
            std::cout << root->getValue() << " ";
        }
    }


    //max between 2 numbers
    int max(int a, int b) {
        return a > b ? a : b;
    }


    };

Et il y a la représentation de l'arbre sur lequel je suis en train de travailler:

          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 

Où est-ce que je fais mal?

2
Asynchronousx 18 nov. 2017 à 15:23

4 réponses

Meilleure réponse

Regardez cette condition: root->getValue() != key && root != nullptr, ce premier appel getValue et après cela vérifie root a une valeur légale. échangez-les (root != nullptr && root->getValue() != key).

Enfin, je pense que vous devez changer la dernière ligne en tmp->Father->Left = root; pour résoudre le problème de plantage.

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father

PS: Faites également cet échange pour l'autre côté ...

Remarque: Ceci est vrai jusqu'à ce que root soit laissé enfant de son père, sinon votre code est vrai. Précisément, vous devez vérifier si root est laissé enfant si son père fait tmp->Father->Left = root; else tmp->Father->Right = root;

Remarque: Comme vous l'avez mentionné, votre code ne gère pas la suppression d'un nœud avec deux enfants.

3
Bonje Fir 18 nov. 2017 à 14:23

Comme il existe déjà une réponse vous donnant des instructions pour corriger les erreurs spécifiques, je vais essayer de me concentrer sur une suggestion qui vous aidera à éviter une erreur similaire dans l'ensemble:

Essayez de séparer votre fonction actuelle en deux:

  1. Celui qui recherche un nœud avec une clé spécifique, par exemple: Node* search(int key) fonction qui renvoie soit un pointeur vers le nœud avec la clé souhaitée ou nullptr, soit celle que vous avez déjà.

  2. Celui qui supprime (et re-relie) le nœud passé comme pointeur et renvoie: suivant, précédent, etc: Node* delete(Node* n).

Appelez ensuite search, testez par rapport à nulltpr, et s'il est différent, passez le pointeur renvoyé comme argument d'entrée dans delete.

De cette façon, vous pouvez facilement détecter à quelle phase vous rencontrez un problème: recherche ou suppression.


P.S.: la détermination des bogues de recâblage se fait généralement à l'aide de schémas (encadrés et flèches). Décidez de ce que vous devez faire, séparez-le en étapes et mettez-le en œuvre.

2
Ziezi 18 nov. 2017 à 12:59

Je voudrais ajouter quelque chose à la réponse de @Bonje Fir. Bien sûr, c'est une réponse correcte, mais partiellement: je vais vous expliquer pourquoi.

Il a suggéré d'échanger le dernier morceau de code que j'ai écrit:

Cas: nous sommes dans le bon sous-arbre, et nous aimerions effacer 70 (car nous n'avons plus le nœud feuille 60):

          50
       /     \
      30      70
     /  \       \
   20   40      80 

Maintenant, avec le code que @Bonje Fir nous a suggéré, nous aurions un problème ici:

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left (instead of Right)  = root; //linking the son to the new father

Parce que le code dit, qu'une fois que vous avez mis à jour la nouvelle racine avec son fils, liez le père de la racine précédente (que nous avons sauvegardée dans une variable tmp) avec son fils gauche. Ensuite, nous aiderions à quelque chose comme ceci:

          50
       /     x
      80      80
     /  \       
   20   40     

Et c'est incohérent.

Jetez maintenant un œil de l'autre côté, avec le même code et sans nœud feuille 20:

      50
   /      \
  30       70
    \     /  \
    40   60  80

Le code tient ici, car nous sommes dans le bon sous-arbre. donc une fois la mise à jour 30 avec 40 (root = root -> right), la situation serait la suivante:

      50
   x      \
  40       70
          /  \
         60  80

Alors le morceau de code @Bonje Fir nous a écrit, conviendrait parfaitement:

tmp->Father->Left = root

Car bien sûr, nous attribuons 40 au fils gauche du père de la racine d'origine. (parce que nous sommes dans le sous-arbre de gauche.)

      50
   /      \
  40       70
          /  \
         60  80

J'ai donc fait un petit changement pour corriger ce problème de logique et le faire fonctionner à la fois dans le sous-arbre droit et gauche.

else if (!root->Left) {
            TreeNode *tmp = root;
            root = tmp->Right;
            root->Father = tmp->Father; //linking the father to the new son

            //we need also to connect the son with the father, but first
            //we need to know in which subtree we're in.

            if (root->Father->Right == tmp) //if we're in the right subtree
                tmp->Father->Right = root;
            else                            ////if we're in the left subtree
                tmp->Father->Left = root;

            delete tmp;

            std::cout << "Erased!" << std::endl;                
        }

J'ai profité du fait que je n'ai pas effacé ma racine, une fois la nouvelle affectée, le père de la racine pointe toujours vers l'ancienne racine.

(même discours pour le cas contraire.)

1
Asynchronousx 18 nov. 2017 à 17:32

Eh bien, une fois que l'on sait que la version DEBUG utilise la valeur sentinelle, il devient beaucoup plus trivial de trouver des problèmes dans le code.

0xDD est pour la mémoire morte. C'est la mémoire qui a déjà été supprimée. Ainsi, lorsque le débogueur s'arrête et qu'il vous indique que vous avez un mauvais pointeur et que les données contiennent beaucoup de 0xDD, vous savez que les données ont déjà été supprimées. À ce stade, vous devez inspecter la classe qui contient les données pour voir si elles sont également supprimées afin de savoir quels objets ont été supprimés lorsque les sont incorporés les uns dans les autres.

Sachez que certaines données peuvent parfois avoir été modifiées dans une partie de la classe si certaines opérations utilisent la mémoire de suppression. L'examen du modèle de mémoire aide également à trouver la mémoire non initialisée et d'autres problèmes similaires.

Quelques autres liens:

Dans un cas comme le vôtre, si vous suivez les bonnes pratiques d'écriture de tests unitaires, il serait encore plus trivial de trouver le problème. En fait, si vous effectuez des tests appropriés, vous testerez tous les cas possibles afin de savoir quels cas échouent et cela vous aiderait à trouver où vous pourriez faire quelque chose de mal.

2
Phil1970 18 nov. 2017 à 14:05
47366014