Insertar nodos en arboles de expresiones.

c++ expression-trees list

Pregunta

Estoy tratando de evaluar una expresión usando un árbol binario. El árbol tiene estas características:

  • Cada nodo tiene cero, uno o dos hijos.
  • Sólo los nodos que contienen operadores pueden tener hijos.
  • Todos los nodos de la hoja deben ser números.
  • En aras de la simplicidad, los únicos operadores permitidos son * y +

Algo así como esos
Arboles de expresion

Esta es mi clase de árbol:

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

Y esta es mi función de inserción:

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

El problema está en esta función. Lo escribí a partir de una función para insertar nodos en un árbol de búsqueda binaria , pero no funciona. Cuando ejecuto un simple main (que, al usar insert() , agrega los nodos del segundo árbol uno a la vez) se bloquea sin devolver ningún error, solo un cuadro de diálogo de Windows 7 que solicita verificar una solución en línea .

Creo que el problema principal es que no inspecciona todos los elementos de un árbol, sino solo una rama, y ​​por esta razón agrega nuevos nodos de manera ilegal. Desafortunadamente, no puedo encontrar la manera de resolver esto.

Espero que esta pregunta no sea demasiado específica.

Nota: is_operator() toma una cadena y devuelve true si es + o * , y false en caso contrario.

Respuesta aceptada

El problema se puede resolver agregando a la clase la posibilidad de realizar un seguimiento del nodo principal para cada nodo. Aquí la nueva clase:

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 única diferencia con la anterior, es la adición de otro miembro de datos Node* . Esto almacenará el puntero al nodo padre, dando así la posibilidad de atravesar el árbol hacia atrás.

También la función insert() necesita algunas modificaciones. Aquí está:

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

Las diferencias con la versión anterior son: la adición de una instrucción else en main if inside the while que rompe el ciclo en caso de que todos los nodos de hoja sean números (eso significa que no pueden tener hijos) [1] y la sustitución (como se especifica) por // + ) del anterior, con una asignación que toca el cursor hacia el nodo principal del actual.

Además, también el constructor Node() pasa por una modificación: cada vez que se crea un nuevo nodo, se vincula con su padre que pasa el segundo argumento del anuncio del puntero del padre.

Sólo una última cosa. El orden para insertar elementos es de arriba a abajo de izquierda a derecha . Por ejemplo, después del primer árbol de la pregunta, los elementos deben insertarse en este orden: *, +, *, 7, 121, 12, +, 9, 3 .


[1] sugerido por Dr_Sam.


Respuesta popular

Creo que vi dos problemas.

(UN)

Supongamos que intenta ingresar el árbol que está a la derecha en su imagen. Ya ingresaste el * en la parte superior y * y + abajo. También entraste en el 7 y el 121 .

Ahora quieres ingresar el 12 y ahí es donde tu código falla.

La raíz es un operador y ambos hijos no son nulos, por lo que entra en la cláusula "else" y considera al niño izquierdo como la ubicación actual. ¡PERO esta parte ya está llena! Así que no podrás insertar nada allí.

Sin embargo, no estoy seguro de que sea el único error, ya que deberías ver tu mensaje de error.

(SEGUNDO)

Creo que si comienza con un número en su árbol (no con un operador), ingresa un ciclo infinito cuando intenta insertar una hoja y no ve el mensaje (el primero, si siempre falla)



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow