Insérer des nœuds dans les arbres d'expression

c++ expression-trees list

Question

J'essaie d'évaluer une expression à l'aide d'un arbre binaire. L'arbre a ces caractéristiques:

  • Chaque nœud a zéro, un ou deux enfants.
  • Seuls les nœuds contenant des opérateurs peuvent avoir des enfants.
  • Tous les nœuds feuilles doivent être des nombres.
  • Par souci de simplicité, les seuls opérateurs autorisés sont * et +

Quelque chose comme ceux-ci:
Arbres d'expression

Ceci est ma classe d'arbre:

class ExpressionTree {
    struct Node {
        std::string data;

        Node *leftChild, *rightChild;

        Node(std::string d): data(d), leftChild(NULL), rightChild(NULL) {}
    } *root;
    uint tsize;
public:
    ExpressionTree(): root(NULL), tsize(0) {}
    Node* treeRoot() { return root; }
    void insert(std::string s);
};

Et voici ma fonction d'insertion:

void insert(std::string s) {
    if (root == NULL) {
        root = new Node(s);
        ++tsize;
    } else {
        Node* current = root;
        while (true) {
            if (is_operator(current->data)) {
                if (current->leftChild == NULL) {
                    current->leftChild = new Node(s);
                    ++tsize;
                    return;
                } else if (current->rightChild == NULL) {
                    current->rightChild = new Node(s);
                    ++tsize;
                    return;
                } else {
                    if (is_operator(current->leftChild->data)) {
                        current = current->leftChild;
                        continue;
                    } else if (is_operator(current->rightChild->data)) {
                        current = current->rightChild;
                        continue;
                    } else {
                        std::cout << "Error: only nodes who hold operators"
                                  << " can have children." << std::endl;
                        return;
                    }
                }
            }
        }
    }
}

Le problème est dans cette fonction. Je l'ai écrit à partir d'une fonction pour insérer des nœuds dans une arborescence de recherche binaire , mais cela ne fonctionne pas. Lorsque j'exécute un insert() principal simple (qui, à l'aide de insert() , ajoute les nœuds de la deuxième arborescence l'un après l'autre), il se bloque sans générer d'erreur, seul un dialogue Windows 7 demandant de rechercher une solution en ligne .

Je pense que le problème principal est qu’il n’inspecte pas tous les éléments d’un arbre, mais seulement une branche, et c’est pour cette raison qu’il ajoute de nouveaux noeuds de manière illégale. Malheureusement, je ne vois pas comment résoudre ce problème.

J'espère que cette question n'est pas trop spécifique.

Remarque: is_operator() prend une chaîne et renvoie true s'il s'agit de + ou * et false sinon.

Réponse acceptée

Le problème peut être résolu en ajoutant à la classe la possibilité de conserver une trace du nœud parent pour chaque nœud. Voici la nouvelle classe:

class ExpressionTree {
    struct Node {
    std::string data;

        Node *leftChild, *rightChild;
        Node* parent; // +

        Node(std::string d, Node* p):
        data(d), leftChild(NULL), rightChild(NULL), parent(p) {}
    } *root;
uint tsize;
public:
    ExpressionTree(): root(NULL), tsize(0) {}
    Node* treeRoot() { return root; }
    void insert(std::string s);
};

La seule différence par rapport à la précédente réside dans l'ajout d'un autre membre de données Node* . Ceci stockera le pointeur sur le nœud parent, donnant ainsi la possibilité de parcourir l’arbre en arrière.

De plus, la fonction insert() nécessite quelques modifications. C'est ici:

void insert(std::string s) {
    if (root == NULL) {
        root = new Node(s, NULL);
        ++tsize;
    } else {
        Node* current = root;
        while (true) {
            if (is_operator(current->data)) {
                if (current->leftChild == NULL) {
                    current->leftChild = new Node(s, current);
                    ++tsize;
                    return;
                } else if (current->rightChild == NULL) {
                    current->rightChild = new Node(s, current);
                    ++tsize;
                    return;
                } else {
                    if (is_operator(current->leftChild->data)) {
                        current = current->leftChild;
                        continue;
                    } else if (is_operator(current->rightChild->data)) {
                        current = current->rightChild;
                        continue;
                    } else {
                        current = current->parent->rightChild; // +
                        continue;
                    }
                }
            } else {
                std::cout << "Error: only nodes who hold operators "
                          << "can have children." << std::endl;
                return;
            }
        }
    }
}

Les différences avec la version précédente sont les suivantes : l'ajout d'une else déclaration dans la principale if l' intérieur du while qui casse la boucle dans le cas où tous les nœuds feuilles sont des nombres (ce qui signifie qu'ils ne peuvent pas avoir des enfants) [1] et la substitution (comme spécifié par // + ) du précédent avec une affectation qui fait basculer le curseur vers le nœud parent du nœud actuel.

De plus, le constructeur Node() subit également une modification: chaque fois qu'un nouveau nœud est créé, il est lié à son parent en transmettant le pointeur et le second argument du parent.

Juste une dernière chose. L'ordre d'insertion des éléments est de haut en bas, de gauche à droite . Par exemple, après le premier arbre de la question, les éléments doivent être insérés dans cet ordre: *, +, *, 7, 121, 12, +, 9, 3 .


[1] suggéré par Dr_Sam.


Réponse populaire

Je pense avoir repéré deux problèmes.

(UNE)

Supposons que vous tentiez d'entrer dans l'arbre situé à droite de votre image. Vous avez déjà entré le * en haut et le * et le + dessous. Vous avez également entré le 7 et le 121 .

Maintenant, vous voulez entrer le 12 et c'est là que votre code échoue.

La racine est un opérateur et les deux enfants ne sont pas nuls. Vous allez donc dans la clause "else" et considérez l'enfant de gauche comme l'emplacement actuel. MAIS cette partie est déjà remplie! Donc, vous ne pourrez rien y insérer.

Pas sûr cependant que ce soit la seule erreur, puisque votre message d'erreur devrait s'afficher.

(B)

Je pense que si vous commencez avec un numéro dans votre arbre (pas avec un opérateur), vous entrez une boucle infinie lorsque vous essayez d'insérer une feuille et vous ne voyez pas le message affiché (le premier si échoue toujours)




Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi