Pasar expresión algebraica en preorden a árbol binario - ForoCoches
TEMA VOLVER USUARIO
Pasar expresión algebraica en preorden a árbol binario
    1. Dabledore Dabledore está desconectado
  • Lo pongo también por aquí que en el general no ha tenido mucho éxito, a ver si me podéis ayudar. Gracias!!
    La cosa es hacer algo tal como:
    De esto: + ^ x 2 sen x
    Conseguir esto:
    +
    / \
    ^ sen
    / \ |
    x 2 x
    El lenguaje me da lo mismo, en pseudocódigo me vale!!
    1. meneill0s meneill0s está desconectado
  • Pero eso no se puede, si te dan la expresión te tienen que decir que recorrido tienes que hacer, ya sea inorden, preordeon o postorden. Sí mal no recuerdo
    Calla coño que ya dices que lo quieres en preorden.


 

 

    1. Dabledore Dabledore está desconectado
  • Cita de meneill0s
    Pero eso no se puede, si te dan la expresión te tienen que decir que recorrido tienes que hacer, ya sea inorden, preordeon o postorden. Sí mal no recuerdo
    Calla coño que ya dices que lo quieres en preorden.
    ¿No se puede?
    1. meneill0s meneill0s está desconectado
  • Sí sí, es que estaba equivocado. Lo que te decía es que sí te dan la expresión y te piden que les des el arbol te tienen que decir el recorrido que quieren.
    1. Dabledore Dabledore está desconectado
  • Cita de meneill0s
    Sí sí, es que estaba equivocado. Lo que te decía es que sí te dan la expresión y te piden que les des el arbol te tienen que decir el recorrido que quieren.
    ¿Recorrido? Ya me dan todos los ingredientes (expresión + notación prefija) como para saber formar el árbol!
    1. meneill0s meneill0s está desconectado
  • Yo lo llamo recorrido pero sí, notación es lo mismo. Espera que busco unos apuntes shurbro.
    1. J. M. Pastroll J. M. Pastroll está desconectado
  • Se puede hacer fácil de forma recursiva, dividiendo el vector de elementos en subvectores.

    El primer elemento siempre es la raíz del árbol o subárbol, en este caso +


    El resto del vector lo divides en 2 (que van a ser subárbol izquierdo y derecho), y aplicas la misma metodología para cada uno de ellos hasta que te queden los vectores vacíos.


    Para tu ejemplo:


    + ^ x 2 sen x
    + es la raíz, ^ x 2 el subarbol izq y sen x el derecho


    Dentro de ^ x 2 y de sen x vuelves a aplicar lo mismo, quedándote ^ como la raiz del subarbol izquierdo, x como subarbol derecho de esa raiz, y 2 como subarbol izquierdo. Ahora tienes los vectores x y 2 por separado. Como sólo tienen un elemento son la raíz de su subarbol, que es vacío (por tanto son hojas).


    Por el otro lado, divides en sen y x, siendo el primero la raíz, y el segundo la raíz de su hijo izquierdo.


    Con esta explicación no te será muy complicado pasarlo a código supongo
    1. Dabledore Dabledore está desconectado
  • Cita de J. M. Pastroll
    Se puede hacer fácil de forma recursiva, dividiendo el vector de elementos en subvectores.

    El primer elemento siempre es la raíz del árbol o subárbol, en este caso +


    El resto del vector lo divides en 2 (que van a ser subárbol izquierdo y derecho), y aplicas la misma metodología para cada uno de ellos hasta que te queden los vectores vacíos.


    Para tu ejemplo:


    + ^ x 2 sen x
    + es la raíz, ^ x 2 el subarbol izq y sen x el derecho


    Dentro de ^ x 2 y de sen x vuelves a aplicar lo mismo, quedándote ^ como la raiz del subarbol izquierdo, x como subarbol derecho de esa raiz, y 2 como subarbol izquierdo. Ahora tienes los vectores x y 2 por separado. Como sólo tienen un elemento son la raíz de su subarbol, que es vacío (por tanto son hojas).


    Por el otro lado, divides en sen y x, siendo el primero la raíz, y el segundo la raíz de su hijo izquierdo.


    Con esta explicación no te será muy complicado pasarlo a código supongo
    Gracias!! ¿Funcionaría también ese método aunque como he puesto en el ejemplo, pueda haber nodos con hijos únicos (sen x, e^x, etc...)?
    1. meneill0s meneill0s está desconectado
  • En los apuntes que tengo es lo mismo que te había pasado antes. Te paso una práctica que lo que hace que tú metiendole la expresión te calcula el resultado. No es lo mismo pero puede que veas algo. Yo es que no me acuerdo una mierda de árboles y eso que fue la penúltima asignatura que aprobé.
    Archivos Adjuntos
    Tipo de Archivo: rar E3.rar (13,7 KB, 3 visitas)
    1. J. M. Pastroll J. M. Pastroll está desconectado
  • Cita de Dabledore
    Gracias!! ¿Funcionaría también ese método aunque como he puesto en el ejemplo, pueda haber nodos con hijos únicos (sen x, e^x, etc...)?
    Quizá la manera más sencilla de hacerlo sea con 2 casos base: cuando tienes un vector de 2 elementos (raíz de su subarbol e hijo izquierdo) y cuando tienes uno de 1 elemento (nodo hoja de la posición que le corresponda), así evitas hacer comparaciones más complejas.
    1. J. M. Pastroll J. M. Pastroll está desconectado
  • Cita de J. M. Pastroll


    Dentro de ^ x 2 y de sen x vuelves a aplicar lo mismo, quedándote ^ como la raiz del subarbol izquierdo, x como subarbol derecho de esa raiz, y 2 como subarbol izquierdo. Ahora tienes los vectores x y 2 por separado. Como sólo tienen un elemento son la raíz de su subarbol, que es vacío (por tanto son hojas).
    He puesto estas 2 al revés


    Es x el hijo izquierdo y 2 el derecho obviamente
    1. Dabledore Dabledore está desconectado
  • Cita de J. M. Pastroll
    Quizá la manera más sencilla de hacerlo sea con 2 casos base: cuando tienes un vector de 2 elementos (raíz de su subarbol e hijo izquierdo) y cuando tienes uno de 1 elemento (nodo hoja de la posición que le corresponda), así evitas hacer comparaciones más complejas.
    Pero en este caso: + x + x x
    Quedaría así:

    ..+
    ./..\
    x....+
    ..../...\
    ...x.....x
    Según tú, cogeríamos el + y meteríamos recursión dividiendo en dos el vector. Quedando en el lado izquierdo + y x. Y como ves, + está a la derecha.
    1. sk40s sk40s está desconectado
  • Estas cosas las hice en la asignatura Compiladores de la carrera, lo hacíamos con el uso de gramáticas.
    1. J. M. Pastroll J. M. Pastroll está desconectado
  • Cita de Dabledore
    Pero en este caso: + x + x x
    Quedaría así:

    ..+
    ./..\
    x....+
    ..../...\
    ...x.....x
    Según tú, cogeríamos el + y meteríamos recursión dividiendo en dos el vector. Quedando en el lado izquierdo + y x. Y como ves, + está a la derecha.
    Pero ese árbol no está equilibrado. Vamos a partir de que con un sólo recorrido no puedes sacar el árbol original, necesitas mínimo 2 recorridos para sacar el exacto, si no hay varias opciones. Yo suelo tirar por la opción de equilibrar ambas ramas, dejando aproximadamente el mismo número de elementos en un subarbol que en el otro, y en ese ejemplo me quedaría:


    ........x
    ..+.........x
    x..........x
    1. ne01982 ne01982 está desconectado
  • Cita de sk40s
    Estas cosas las hice en la asignatura Compiladores de la carrera, lo hacíamos con el uso de gramáticas.
    Muy cierto .
Utilizamos cookies propias y de terceros para prestar nuestros servicios y mostrar publicidad relacionada con sus preferencias.
Si continua navegando, consideramos que acepta su uso. Puede obtener más información, o bien conocer cómo cambiar la configuración, en nuestra Política de cookies.