Insert BST en C++

Question

J'apprends le C++ et j'écris un arbre de recherche binaire. Ce qui suit est le code que j'ai écrit pour ma méthode d'insertion.

BSTNode * BST::Insert(const std::string & v) { 
    BSTNode *n = !root ? root = new BSTNode(v) : Insert_Helper(v,root); 
    if(n) size++; 
    return n; 
} 

BSTNode * BST::Insert_Helper(const std::string & v, BSTNode *n) { 
    if(!n->value.compare(v)) 
     return NULL; // already have v 
    else if(n->value.compare(v) > 0) // v goes to the left 
     if(n->left) return Insert_Helper(v,n->left); 
     else return n->left = new BSTNode(v); 
    else // v goes to the right 
     if(n->right) Insert_Helper(v,n->right); 
     else return n->right = new BSTNode(v); 
} 

Le bug que je reçois va comme ceci: tout cela fonctionne bien et dandy, jusqu'à ce que je tente d'insérer un nœud double. Il n'ajoute pas de nouveau noeud, mais il incrémente le nombre. En observant dans GDB, j'ai constaté que lorsque j'essaie d'ajouter une chaîne que j'ai déjà, Insert_Helper fonctionne correctement et renvoie NULL. Cependant, cette valeur (sur ma machine) est quelque chose comme 0x6, qui est hors limites bien sûr, mais pas 0x0 comme je pensais que ce serait. Je pense que cela cause un problème au point où j'ai l'instruction if (n). Dans ce cas, n est évalué à "true" et augmente donc d'un cran la taille d'un.

En outre, à ce stade de mon programme, les nœuds continuent d'être ajoutés correctement, mais ma fonction d'insertion continue de renvoyer 0x6 comme adresse, même s'ils sont réellement dans des emplacements valides en mémoire auxquels je peux accéder. Est-ce que quelqu'un peut me donner des indications sur ce que je pourrais faire de mal?

Answer 1

Votre compilateur devrait probablement repéré, mais cette ligne à la fin de votre aide:

if(n->right) Insert_Helper(v,n->right);

Vous devriez probablement revenir tout Insert_Helper rendement:

if(n->right) return Insert_Helper(v,n->right);

Answer 2

Vous pouvez modifier if(n) size++ à if (n != NULL) size++