Fügen Sie Knoten in Ausdrucksbäume ein

c++ expression-trees list

Frage

Ich versuche, einen Ausdruck mithilfe eines Binärbaums auszuwerten. Der Baum hat diese Eigenschaften:

  • Jeder Knoten hat null, ein oder zwei Kinder.
  • Nur Knoten, die Operatoren enthalten, können untergeordnete Objekte haben.
  • Alle Blattknoten müssen Nummern sein.
  • Der Einfachheit halber sind die einzigen erlaubten Operatoren * und +

So etwas wie diese:
Ausdrucksbäume

Das ist meine Baumklasse:

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);
};

Und das ist meine Einfügefunktion:

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;
                    }
                }
            }
        }
    }
}

Das Problem liegt in dieser Funktion. Ich habe es geschrieben, beginnend mit einer Funktion zum Einfügen von Knoten in einem Binär-Suchbaum , aber es funktioniert nicht. Wenn ich einen einfachen main insert() mit insert() die Knoten des zweiten Baums nacheinander hinzufügt) stürzt er ab, ohne einen Fehler zu melden, nur ein Windows 7 Dialog, der nach einer Online Lösung fragt.

Ich denke, dass das Hauptproblem ist, dass es nicht alle Elemente eines Baumes untersucht, sondern nur einen Zweig, und aus diesem Grund fügt es neue Knoten auf illegale Weise an. Leider kann ich nicht herausfinden, wie ich das lösen kann.

Ich hoffe, dass diese Frage nicht zu spezifisch ist.

Hinweis: is_operator() einen String und gibt true wenn er + oder * , andernfalls false.

Akzeptierte Antwort

Das Problem kann gelöst werden, indem der Klasse die Möglichkeit hinzugefügt wird, die Spur des übergeordneten Knotens für jeden Knoten zu behalten. Hier die neue Klasse:

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);
};

Der einzige Unterschied zu dem vorherigen ist das Hinzufügen eines anderen Node* -Datenelements. Dies speichert den Zeiger auf den Elternknoten und gibt auf diese Weise die Möglichkeit, den Baum rückwärts zu durchlaufen.

Auch die Funktion insert() benötigt einige Modifikationen. Hier ist es:

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;
            }
        }
    }
}

Die Unterschiede zur vorherigen Version sind: das Hinzufügen einer else Anweisung im main, if innerhalb der while , die die Schleife unterbricht, falls alle Blattknoten Zahlen sind (dh sie können keine Kinder haben) [1] und die Ersetzung (wie angegeben durch // + ) des vorherigen else mit einer Zuweisung, die den Cursor rückwärts zum übergeordneten Knoten des aktuellen verweist.

Darüber hinaus durchläuft auch der Konstruktor Node() eine Änderung: Jedes Mal, wenn ein neuer Knoten erstellt wird, wird er mit seinem Elternknoten verknüpft und übergibt das zweite Argument des Elternzeigers an die Anzeige.

Nur eine letzte Sache. Die Reihenfolge zum Einfügen von Elementen ist von oben nach unten links / rechts . Beispielsweise müssen nach dem ersten Baum in der Frage die Elemente in dieser Reihenfolge eingefügt werden: *, +, *, 7, 121, 12, +, 9, 3 .


[1] vorgeschlagen von Dr_Sam.


Beliebte Antwort

Ich denke, dass ich zwei Probleme entdeckt habe.

(EIN)

Angenommen, Sie versuchen, den Baum zu betreten, der sich rechts in Ihrem Bild befindet. Sie haben bereits das * oben und das * und + darunter eingegeben. Sie haben auch die 7 und die 121 eingegeben.

Jetzt möchten Sie die 12 eingeben und das ist, wo Ihr Code fehlschlägt.

Die Wurzel ist ein Operator und beide untergeordneten Objekte sind nicht null. Sie gehen also in die "else" -Klausel und betrachten das linke Kind als aktuellen Ort. ABER dieser Teil ist bereits gefüllt! Sie können also dort nichts einfügen.

Nicht sicher, dass es der einzige Fehler ist, da Sie Ihre Fehlermeldung angezeigt bekommen sollten.

(B)

Ich denke, wenn Sie mit einer Nummer Ihren Baum (nicht mit einem Operator) beginnen, geben Sie eine Endlosschleife ein, wenn Sie versuchen, ein Blatt einzufügen, und Sie sehen die Nachricht nicht angezeigt (die erste, wenn immer fehlschlägt)



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum