Inserire i nodi negli alberi di espressione

c++ expression-trees list

Domanda

Sto cercando di valutare un'espressione usando un albero binario. L'albero ha queste caratteristiche:

  • Ogni nodo ha zero, uno o due figli.
  • Solo i nodi contenenti operatori possono avere figli.
  • Tutti i nodi foglia devono essere numeri.
  • Per semplicità, gli unici operatori consentiti sono * e +

Qualcosa come quelli:
Alberi espressione

Questa è la mia classe di albero:

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

E questa è la mia funzione di inserimento:

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

Il problema è in questa funzione. L'ho scritto partendo da una funzione per inserire i nodi in un albero di ricerca binaria , ma non funziona. Quando eseguo una semplice main (che, usando insert() , aggiunge i nodi del secondo albero alla volta) si blocca senza restituire alcun errore, solo una finestra di dialogo di Windows 7 che chiede di verificare una soluzione online .

Penso che il problema principale sia che non controlla tutti gli elementi di un albero, ma solo un ramo, e per questo motivo aggiunge nuovi nodi in modo illegale. Sfortunatamente, non riesco a capire come risolverlo.

Spero che questa domanda non sia troppo specifica.

Nota: is_operator() accetta una stringa e restituisce true se è + o * e false altrimenti.

Risposta accettata

Il problema può essere risolto aggiungendo alla classe la possibilità di tenere traccia del nodo genitore per ciascun nodo. Ecco la nuova 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);
};

L'unica differenza rispetto alla precedente è l'aggiunta di un altro membro dati Node* . Questo memorizzerà il puntatore sul nodo genitore, dando in questo modo la possibilità di attraversare l'albero all'indietro.

Anche la funzione insert() richiede alcune modifiche. Ecco qui:

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

Le differenze con la versione precedente sono: l'aggiunta di else istruzione nella parte principale if all'interno del while che interrompe il ciclo nel caso in cui tutti i nodi foglia siano numeri (ciò significa che non possono avere figli) [1] e la sostituzione (come specificato per // + ) del precedente precedente con un incarico che attiva il cursore verso il nodo genitore di quello corrente.

Inoltre, anche il costruttore Node() passa attraverso una modifica: ogni volta che viene creato un nuovo nodo, viene collegato con il suo genitore che passa il puntatore del genitore e il secondo argomento.

Solo un'ultima cosa L'ordine per inserire elementi è dall'alto verso il basso sinistra-destra . Ad esempio, seguendo il primo albero nella domanda, gli elementi devono essere inseriti in questo ordine: *, +, *, 7, 121, 12, +, 9, 3 .


[1] suggerito da Dr_Sam.


Risposta popolare

Penso di aver individuato due problemi.

(UN)

Supponiamo di provare ad inserire l'albero che si trova sulla destra nella tua immagine. Hai già inserito * in alto e * e + basso. Hai inserito anche il 7 e il 121 .

Ora vuoi inserire il 12 ed è qui che il tuo codice fallisce.

La radice è un operatore e entrambi i bambini non sono nulli, quindi vai nella clausola "else" e considera il figlio sinistro come la posizione corrente. MA questa parte è già piena! Quindi non sarai in grado di inserire nulla lì.

Non sono sicuro che sia l'unico errore, dal momento che dovresti vedere il tuo messaggio di errore visualizzato.

(B)

Penso che se inizi con un numero il tuo albero (non con un operatore), inserisci un loop infinito quando provi ad inserire una foglia e non vedi il messaggio visualizzato (il primo se fallisce sempre)



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché