Comment ajouter des enfants à BST

Question

J'essaie de créer/créer un BST, mais cela ne semble pas fonctionner correctement. J'ai littéralement été assis ici pendant des heures à essayer de comprendre ce qui se passe. C'est arrivé au point où j'ai dessiné un million de diagrammes pour comprendre cela, mais mon code me manque. Je dois passer dans un nœud racine dans une fonction. Ensuite, j'ai besoin de traverser l'arbre jusqu'à ce que je trouve que le paramètre chaîne parent de la fonction coïncide avec la chaîne du nœud parent de l'arbre. Si je le trouve, je dois insérer la chaîne dans le parent, et créer deux nouveaux enfants à partir de ce parent. Si je ne trouve pas la chaîne parent, alors je renvoie false.

bool insertNode(BSTNode *n, char* parentQ, char* leftQ, char* rightQ) 
{ 
    if(n->Q == parentQ) 
    { 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q != parent) 
    { 
    insertNode(n->left,parentQ,leftQ,rightQ); 
    insertNode(n->right,parentQ,leftQ,rightQ); 
    } 
    else 
    return false; 
} 

Je dois aussi faire une autre méthode qui prend l'arbre que j'ai créé, et corrige les cordes. Ainsi, la méthode modifie la chaîne parent, si elle est trouvée, et regarde ses enfants, si elle est trouvée, et remplace ces chaînes par celles trouvées dans les paramètres de la méthode. C'est un peu comme ajouter un sous-arbre sans visser tout l'arbre. Merci d'avance!

bool changeNode(BSTNode *n,char* parentQ, char* leftQ, char* rightQ) 
{ 
    if(n->Q == leftQ) 
    { 
    n->Q = parentQ; 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q == rightQ) 
    { 
    n->Q = parentQ; 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q != leftQ) 
    { 
    changeNode(n->left,parentQ,leftQ, rightQ); 
    } 
    else if(n->Q != rightQ) 
    { 
    changeNode(n->right,parentQ,leftQ,rightQ); 
    } 
    return false; 
} 

Answer 1

Vous ne mentionne même pas ce que l'erreur a été, par exemple d'entrée/sortie attendue, mais vous ne devriez pas être vérifier si le noeud courant a en fait un enfant gauche et à droite, avant d'appeler la fonction avec les enfants ?

else if(n->Q != parentQ) // <--- you have a typo in this line, "parent" 
    {      //  (and you don't even need the 'if') 
    insertNode(n->left,parentQ,leftQ,rightQ); 
    insertNode(n->right,parentQ,leftQ,rightQ); 
    // in this case you return nothing! corrupted return value 
    } 

^Cela semble très sujet aux erreurs, en particulier null-pointeur. Vous devriez en faire quelque chose comme:

else 
     { 
     if(n->left != NULL) // take a look at nullptr if you have C++11 
      if(insertNode(n->left,parentQ,leftQ,rightQ)) return true; 
     if(n->right != NULL) 
      if(insertNode(n->right,parentQ,leftQ,rightQ)) return true; 
     return false; 
     } 

Sinon, votre retour true ne se propage au-delà du premier return, alors vous êtes toujours revenir false à moins que dans le seul cas où la racine de l'arbre est en fait la nœud que vous recherchiez.

En outre, ne pas comparer deux tableaux en utilisant char==, à moins n->Q est en fait un std::string. Vous devriez utiliser if(strcmp(n->Q, parentQ) == 0) sinon. Votre deuxième code, cependant, est juste un gâchis. Vous devez regarder ce qui se passe exactement sur votre else if et voir s'il fait ce que vous voulez (indice: ce n'est pas le cas), car vous n'exécutez actuellement que 1 bloc de code, même si plus d'une condition est vraie.