Ajouter des nœuds à l'arbre de recherche binaire C++

Question

Je construis un arbre de recherche binaire. Maintenant, j'ai un problème avec l'ajout d'un nœud à l'arbre.

void BinaryTree::add(int value, Node* node) { 
    if(!node) 
     node = new Node(value); 
    else if(node->key < value) 
     this->add(value, node->rightNode); 
    else if(node->key > value) 
     this->add(value, node->leftNode); 
} 

Ce code ne semble pas fonctionner quand je l'appelle:

BinaryTree test; 
test.add(4, test.root); 
test.add(1, test.root); 
test.add(5, test.root); 
test.add(2, test.root); 
test.add(3, test.root); 
test.add(7, test.root); 
test.add(6, test.root); 

Après le premier appel d'ajout, la racine du « test » de l'arbre est encore vide. Comment dois-je changer le code pour qu'il soit mis à jour quand j'appelle add et que le noeud va à l'endroit correct de l'arbre? Merci beaucoup!

Answer 1

Vous passez la Node * en valeur ici:

void BinaryTree::add(int value, Node* node) { 

Une solution consiste à passer par référence à la place:

void BinaryTree::add(int value, Node *& node) { 
            ^

Si vous passez en valeur la fonction est juste de recevoir une copie du Node * et ainsi toute modification ne sera pas reflétée dans le code appelant.

En outre, vous voudrez peut-être penser à ce qui se passe lorsque value est égal à key.

Answer 2

Vous appelez de manière récursive la fonction add, mais je ne vois nulle part que vous assignez en réalité leftNode ou rightNode au noeud passé.