Construction d'arborescence avec des pointeurs

Question

J'essaie de créer une fonction qui insère une structure de clé dans un arbre. La fonction définit correctement la racine, mais ne définit pas les branches lorsqu'elle est appelée à nouveau avec une autre clé. Voici le code:

tree.h:

class tree{ 

    key *tree_root; 

public: 
    tree(); 
    //Constructor 

    void treedestroy(key *root); 
    //Tree destructor helper 

    ~tree(); 
    //Destructor 

    void insert(key* root, key *newkey, int disc); 

}; 

fonction d'insertion

de la classe d'arbre:

void tree::insert(key *root, key *newkey, int disc){ 
    if (root == NULL){ 
     root = newkey; 
     return; 
    } 
    if (newkey->cord[disc] <= root->cord[disc]) 
     insert(root->left, newkey, (disc+1)%4); 
    else if (newkey->cord[disc] > root->cord[disc]) 
     insert(root->right, newkey, (disc+1)%4); 
} 

Je suis un peu inexpérimenté avec des pointeurs C++ et je me demandais comment je pouvais résoudre ce problème code afin qu'il remplisse l'arbre correctement?

Answer 1

Je ne suis pas tout à fait sûr de votre approche, mais pour vous aider à obtenir sur vos pieds, il serait utile d'utiliser une signature de fonction:

void insert(key*& root, key *newkey, int disc); 

Ceci passe le pointeur de la racine par référence, ce qui signifie que les modifications apportées à l'intérieur de la fonction vont "coller" à la variable que vous avez transmise.

Votre fonction telle qu'elle est modifiée modifie une variable fonction-locale, sans propagation de ces changements.

This article est une lecture équilibrée et rapide en passant par référence (je ne peux pas dire si c'est le meilleur - il était le premier décent j'ai trouvé)

Answer 2

1. Si au premier appel, la nouvelle clé est nulle, la racine restera nulle. Assurez-vous que l'appel de méthode est correct.

2. Je mettrais un autre plutôt qu'un autre si. Si c'est un arbre binaire, il est soit égal, supérieur ou inférieur à.

3. Est-ce que ça va dans Insert_helper ou pas? Pourquoi ne l'avez-vous pas inclus, semble important? Je suppose que cela devient au moins aussi loin.

Answer 3

root = newKey; 

Cela ne modifie pas la racine réelle. Il suffit de modifier l'argument de la fonction qui est une copie du pointeur que vous spécifiez lors de l'appel de la fonction intsert.

la version correcte serait ressemble à quelque chose comme ceci:

private: 
void tree::insert_helper(key **root, key *newkey, int disc) { 
    if ((*root) == NULL) { 
    *root = key; 
    } else if (newkey->cord[disc] <= root->cord[disc]) { 
    insert_helper(&((*root)->left), newkey, (disc+1)%4); 
    } else { 
    insert_helper(&((*root)->right), newkey, (disc+1)%4); 
    } 
} 

public: 
void tree::insert(key *newKey, int disc) { 
    insert_helper(&tree_root, newkey, disc); 
} 

Aussi, vous devez être sûr que « clé » constructol NULL pour régler gauche et à droite. Et le constructeur d'arbre devrait définir NULL pour tree_root