Bonsoir !

Ça fait un certain temps que je n'ai pas fait de C++, mais je ne crois pas être tombée sur un problème comme ça auparavant. Je vous explique.

Je cherche à construire un arbre binaire de recherche, et mon code se compile sans erreur. J'ai donc une classe Node et une classe Tree :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
 
class Tree
{
    // Attributes
 
    int m_nbNodes;
 
    public :
    std::vector<Node> m_nodes;
 
    // Methods
 
    Tree();
    int getNbNodes();
    Node* getRoot();
    bool addNode(std::string key,int order);
 
 
 
};
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
class Node
{
    // Attributes
 
    std::string m_key;
    int m_order;
    Node* m_left;
    Node* m_right;
 
 
    //Methods
    public:
 
    Node();
 
    Node(std::string key, int order);
 
    std::string getKey();
 
    int getOrder();
 
    Node* getLeft();
 
    Node* getRight();
 
    void changeKey(std::string newKey);
 
    void changeOrder(int newOrder);
 
    void changeRight(Node* newRight);
 
    void changeLeft(Node* newLeft);
 
    void show();
 
    void addLeft(Node* son);
 
    void addRight(Node* son);
 
 
};
Je veux ajouter des nouveaux noeuds : "head","foot","often" et "coffee", dans cette ordre. Voila le code d'ajout d'un nouveau noeud :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
bool Tree::addNode(std::string key,int order)
{
    Node* newNode= new Node(key,order);
    Node* tmpNode;
    Node* tmpFather;
    string keyComp;
    if(m_nbNodes != 0)
    {
        tmpNode = &m_nodes[0];
        do
        {
            tmpFather = tmpNode;
            keyComp =tmpNode->getKey();
            if(key>keyComp)
            {
                tmpNode = tmpNode->getRight();
                if(!tmpNode)
                {
                    tmpFather->changeRight(newNode);
                    break;
                }
            }
            else if(key<keyComp)
            {
                tmpNode = tmpNode->getLeft();
                if(!tmpNode)
                {
                    tmpFather->changeLeft(newNode);
                    break;
                }
            }
            else
            {
                cout<<"This word is already in the tree."<<endl;
                return false;
            }
        }while(tmpNode);
    }
    m_nodes.push_back(*newNode);
    m_nbNodes++;
    return true;
}
Jusqu'à often, tout se passe bien : "head" est la racine, "foot" est son fils gauche, "often" est son fils droit, et ces derniers n'ont pas de fils. Quand je veux ajouter "coffee", à l'intérieur de la fonction tout se passe bien (en particulier, la ligne 29 tmpFather->changeLeft(newNode); est bien effectuée, les changements d'adresses sont corrects). Problème : une fois sorti de la fonction, le programme oublie qu'il a changé la valeur du fils gauche de "foot".

Du coup je me suis dit que c'est tmpFather qui n'est pas bien relié au noeud qui a un fils gauche vide, mais dans ce cas là je ne comprends pas pourquoi ça n'a pas raté lors de l'assignation de "foot" en tant que fils gauche de "head".

Quelqu'un a une idée de ce qui se passe ? J'ai passé l'aprem dessus sans comprendre d'où ça venait.

Merci d'avance