Fecha y hora actual: Domingo 25 Ago 2019 05:03
Índice del Foro

Foros de programación informática, diseño gráfico y Web

En esta comunidad intentaremos dar soporte de programación a todos los niveles, desde principiantes a profesionales de la informática, desarrollo de programas, programación web y mucho más.

Lección 56: Árbol Binario - Recorrido común - Eliminación

Responder al Tema Ir a página 12Siguiente

Índice del Foro > Programación en general > Lección 56: Árbol Binario - Recorrido común - Eliminación

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Miércoles 25 Abr 2012 18:57

Título del mensaje: Lección 56: Árbol Binario - Recorrido común - Eliminación

Responder citando

En las dos lecciones anteriores comenzamos a trabajar con árboles binarios, más precisamente, con árboles binarios de búsqueda. Hemos visto un pantallazo de lo que es esta estructura y de cómo implementarla en Modula 2.

Ahora comenzaremos a ver cómo recorrer un árbol binario de forma sencilla para imprimir su contenido, enfatizando cómo la recursividad nos resuelve la vida.

Espero que hasta ahora vallan siguiendo los temas que hemos dado, ya que no han habido muchos comentarios al respecto. La participación ha decaído bastante y eso no me complace demasiado. Igualmente continuaré con el curso tal como lo he hecho hasta ahora porque siempre hay alguien que lee algo, pero de verdad me gustaría que todos los que leen una lección comenten si han entendido, si les ha gustado el tema, si les parece interesante o no, etc.

En fin, sigamos con lo que nos compete.

Tres formas comunes de recorrer un árbol binario:

Veremos ahora las tres formas más comunes de recorrer un árbol binario (de búsqueda o no). Si por ejemplo, quisiéramos mostrar en pantalla los elementos que contiene mi árbol, tendría que recorrerlos todos para ir imprimiéndolos. ¿Cómo harían eso ustedes? Peor aún ¿cómo imprimirían todos los elementos de un árbol binario sin recorrer más de una vez cada nodo? Y peor todavía ¿cómo recorrerían un árbol binario sin pasar más de una vez por cada nodo de modo que al imprimir los elementos estos queden mostrados en pantalla de menor a mayor?

La magia de la recursividad resuelve estos problemas. Veamos entonces cuáles son las tres formas de recorrer un árbol binario para luego profundizar en cada una:


  • Recorrido en Pre-orden: La idea de esta forma de recorrer un árbol es, dado el mismo primero visitamos la raíz, luego el subárbol izquierdo y luego el subárbol derecho.
  • Recorrido En-orden: Esta forma, dado un árbol binario, recorre primero el subárbol izquierdo, luego la raíz y luego el subárbol derecho. Créanme que si usan esta forma de recorrer un árbol binario de búsqueda, estarán visitando los nodos en forma ascendente. Ya veremos esto.
  • Recorrido en Post-orden: Esta forma recorre, dado un árbol binario, primero el subárbol izquierdo, luego el derecho y finalmente la raíz.



Ejemplo de recorrido En-orden:

Supongan tenemos el mismo árbol binario que ya conocemos:



Imprimiremos los elementos recorriéndolo En-Orden. Dado que esto es un procedimiento recursivo, tendremos que ir anotando lo que nos va quedando pendiente en cada llamado. Recuerden que el recorrido En-orden es así:

  • Recorro el subárbol izquierdo.
  • Recorro la raíz.
  • Recorro el subárbol derecho.


Iremos llamado a llamado numerándolos. En cada ejemplo pondré en verde lo siguiente a realizar, en rojo lo que va quedando pendiente y en azul lo que ya hemos realizado.

Llamado 1: Tengo el árbol de raíz 20 (el dibujo anterior). Entonces tenemos que hacer esto:

** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2.
** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo.
** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20.


Llamado 2: Tenemos el subárbol de raíz 1:

** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3.
** Imprimimos el número 1 (raíz actual).
** Debemos recorrer el subárbol derecho (raíz 6).




Llamado 3: Tenemos el subárbol de raíz 0:



** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4.
** Imprimimos el número 0 (raíz actual).
** Debemos recorrer el subárbol derecho (vacío).


Llamado 4: Tenemos un árbol vacío, por lo tanto no hay nada por hacer así que volvemos hacia el Llamado 3 a ver que teníamos pendiente.

Llamado 3: Tenemos el subárbol de raíz 0:



** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4.
** Imprimimos el número 0 (raíz actual).
** Debemos recorrer el subárbol derecho (vacío). Llamado 5.

Como ya hemos cumplido la primera instrucción de este llamado, ahora vamos a la segunda que consta simplemente de imprimir un 0, entonces la salida de nuestro programa será por ahora:

Código:
0


Cumplido eso, vamos al Llamado 5.

Llamado 5: Tenemos un árbol vacío. Tampoco hay nada por hacer. Volvemos al Llamado 3.

Llamado 3: Hemos cumplido todas las instrucciones de este llamado. Como su invocación había sido hecha desde el Llamado 2, volvemos hacia él.



** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4.
** Imprimimos el número 0 (raíz actual).
** Debemos recorrer el subárbol derecho (vacío). Llamado 5.


Llamado 2: Volvemos a tener el árbol de raíz 1:



** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3.
** Imprimimos el número 1 (raíz actual).
** Debemos recorrer el subárbol derecho (raíz 6). Llamado 6.

Ahora debemos imprimir la raíz del árbol, es decir el 1. Con eso nuestra salida queda ahora:

Código:
0 1


Hecho eso debemos ahora ir a la tercera instrucción de este llamado, recorrer el árbol de raíz 6.

Llamado 6: Tenemos el árbol de raíz 6:



Al igual que en el llamado 3, cuando solo teníamos el nodo 0, este llamado acabará por imprimir el 6 en pantalla, quedando nuestra salida así:

Código:
0 1 6


Como este llamado fue hecho desde el llamado 2 debemos volver a él.

Llamado 2: Hemos realizado todas las instrucciones de este llamado:
** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3.
** Imprimimos el número 1 (raíz actual).
** Debemos recorrer el subárbol derecho (raíz 6). Llamado 6.


Hecho eso, como este llamado fue realizado desde el llamado 1, volvemos a él.

Llamado 1: Tenemos nuevamente el árbol de raíz 20. Las instrucciones están así:
** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2.
** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo.
** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20.

De este modo ahora debemos imprimir el 20, quedando nuestra salida así:

Código:
0 1 6 20


Ahora nuestras instrucciones están así:

** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2.
** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo.

** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20.

Para realizar la última instrucción de este llamado tendríamos un nuevo llamado el cual derivaría en nuevos llamados a su vez. Lo que quiero es que noten que la salida ha ido quedando ordenada de menor a mayor, y así acabaríamos por imprimir todo el árbol.
No seguiré ejemplificando hasta el final ya que creo que ha quedado claro como funciona esto. Ahora les mostraré cómo quedan los códigos fuente para recorrer un árbol binario.

======================

Implementación de impresión en Pre-orden:

Este procedimiento imprimirá en pantalla un árbol del tipo ABBEnteros recorriéndolo en Pre-orden, ese decir así:

  • Imprimo la raíz.
  • Imprimo el subárbol izquierdo.
  • Imprimo el subárbol derecho.


Código:
PROCEDURE ImprimirPreOrden(abb: ABBEnteros);
BEGIN
   IF NOT EsVacioABBEnteros(abb) THEN
      WriteCard(abb^.num,1); WriteString(" ");
      ImprimirPreOrden(abb^.izq);
      ImprimirPreOrden(abb^.der);
   END;
END ImprimirPreOrden;


Como verán, este procedimiento recursivo tiene una única condición o caso base: el árbol vacío, en cuyo caso no realiza tarea alguna. Quiero que noten que las instrucciones están escritas en el orden en que se deben realizar las impresiones según el recorrido en Pre-orden, es decir, primero tenemos la instrucción:

Código:
WriteCard(abb^.num,1); WriteString(" ");

Claramente esto se condice con Imrpimo la raíz.

Luego tenemos la instrucción:

Código:
ImprimirPreOrden(abb^.izq);

Como verán esto es un llamado recursivo a ImprimirPreOrden pero pasando como argumento el subárbol izquierdo.

Por último tenemos:

Código:
ImprimirPreOrden(abb^.der);

Análoga a la anterior pero pasando el subárbol derecho como argumento al nuevo llamado.

Aquí está la magia de la recursión. Como verán, el código es simple y corto, respetando el orden que tiene la definición teórica de lo que es recorrido en Pre-orden.

Si ustedes hacen un análisis como el que yo hice para el recorrido En-Orden, verán que esto funciona y funciona bien. Si fueran a intentar hacer algo como esto de forma iterativa créanme que se quedarían sin pelos.

De este modo, las operaciones de recorrido En-Orden y en Post-Orden quedan análogas a las definiciones de estos tipos de recorridas. Sin embargo se las dejo aquí para que las tengan.

==================================

Implementación de impresión En-Orden:

Recuerden que la definición teórica dice:


  • Imprimo el subárbol izquierdo.
  • Imprimo la raíz.
  • Imprimo el subárbol derecho.


Código:
PROCEDURE ImprimirEnOrden(abb: ABBEnteros);
BEGIN
   IF NOT EsVacioABBEnteros(abb) THEN
      ImprimirEnOrden(abb^.izq);
      WriteCard(abb^.num,1); WriteString(" ");
      ImprimirEnOrden(abb^.der);
   END;
END ImprimirEnOrden;


================================

Implementación de impresión en Post-Orden:

Recuerden que la definición teórica dice:
  • Imprimo el subárbol izquierdo.
  • Imprimo el subárbol derecho.
  • Imprimo la raíz.


Código:
PROCEDURE ImprimirPostOrden(abb: ABBEnteros);
BEGIN
   IF NOT EsVacioABBEnteros(abb) THEN
      ImprimirPostOrden(abb^.izq);
      ImprimirPostOrden(abb^.der);
      WriteCard(abb^.num,1); WriteString(" ");
   END;
END ImprimirPostOrden;


Espero que esto les haya quedado claro. No es en sí super difícil, pero requiere que entiendan la recursividad y cómo esta opera recorriendo los nodos uno a uno sin repetirlos.

Aquí hemos usado las recorridas simplemente para imprimir en pantalla lo que contienen los árboles, pero podría haber sido cualquier otra cosa. En tal caso, lo único que tienen que hacer es simplemente cambiar los WriteCard por las instrucciones que necesiten hacer, sean tantas como sean.

Existe otra forma de recorrer árboles que es por niveles, pero la veremos luego.

===============================================

Eliminación de un nodo en un árbol binario de búsqueda:

La tarea de eliminar un nodo en un árbol binario de búsqueda tiene tres casos, dos de ellos sencillos y uno muy complejo. Entonces, dado nuestro ya conocido árbol de ejemplo:



¿Sería difícil eliminar alguno de sus nodos hoja? Es decir, si quiero por ejemplo eliminar el nodo 22, no tengo más que simplemente borrarlo, decir que el subárbol derecho de 23 es NIL y ya. Tendríamos esto:



Ahora bien, imaginen que ahora, en el árbol que me ha quedado quiero eliminar el nodo 21, obviamente sin perder el 23. ¿Qué hago? Pues simplemente debo intercambiar el 21 con el 23 para finalmente eliminar el 21. Quedaría así:



¿Qué pasa si quiero eliminar el nodo 20? Ahí se complica la cosa. Imaginen que tenemos el árbol inicial:



Quiero quitar el nodo 20 de ahí. ¿Qué hago? Hay que mantener el orden que tiene el árbol binario de búsqueda, pero el nodo 20 tiene dos hijos los cuales a su vez tienen más nodos. Pues bien, este caso es el más complejo. Lo que se hace es buscar el nodo más grande del subárbol izquierdo o bien el nodo más pequeño del subárbol derecho. Veamos ambos ejemplos.

Imaginen que me decidí por buscar el nodo más grande del subárbol izquierdo. En este caso es el 6. Entonces coloco el 6 en lugar del 20 y luego elimino este, quedando el árbol así:



Como ven, el orden de los elementos se sigue manteniendo.
La otra opción en vez de elegir el 6 era elegir el elemento más pequeño del subárbol derecho, en este caso el 21. Hacemos lo mismo, es decir, sustituimos el 21 por el 20 y luego eliminamos este. El árbol quedaría así:



Noten que el 21 tenia hijos, pero estos se mantienen intactos. El orden de los elementos sigue siendo correcto.

Resumiendo, los tres posibles casos para eliminar un nodo, según su dificultad son:

  • El nodo es un nodo hoja. Este es el caso más sencillo.
  • El nodo tiene un único hijo. En este caso solo debemos hacer un intercambio.
  • El nodo tiene dos nodos hijos. Este es el caso más complejo y difícil de resolver.


La implementación que haremos para la operación de borrado será iterativa. ¿Por qué? Porque se puede hacer de forma sencilla, y pues, siempre que podamos tener iteración y esta no sea super complicada, es mejor que hacerlo de forma recursiva ya que como saben la recursividad utiliza el Stack de memoria y pues es menos eficiente en el consumo de recursos.

Para las operaciones de recorrida no nos quedaba otra solución que la recursividad porque no existe forma sencilla de hacerlo iterativo. Además, en cada llamado nos quedaban cosas por hacer, y justamente eso es lo que justifica a la recursividad ante la iteración.

Necesitaremos funciones auxiliares para poder implementar la eliminación tal como yo la he pensado. Se podrían omitir y hacer todo en una sola operación, pero creo que de este modo el código será mucho más claro para ustedes y pues, podrán comprender mejor qué es lo que se está haciendo. Si buscan en Wikipedia encontrarán algún algoritmo interesante, pero un poco más difícil de entender.

Veremos entonces tres operaciones auxiliares:

  • MayorABBEnteros: Dado un árbol binario de búsqueda no vacío nos devolverá el nodo mayor existente en él.
  • MenorABBEnteros: Dado un árbol binario de búsqueda no vacío nos devolverá el nodo menor existente en él.
  • DesengancharNodo: Dado un árbol binario de búsqueda no vacío y un nodo existente de él, esta función lo desenganchará del árbol pero no lo eliminará de la memoria. Al desenganchar un nodo perderemos del árbol todos los subárboles de ese nodo.


Aquí están las implementaciones de estos subprogramas:

Función MayorABBEnteros:

Código:
(*PRECONDICIÓN: El árbol no es vacío*)
PROCEDURE MayorABBEnteros(abb: ABBEnteros): ABBEnteros;
VAR iterador: ABBEnteros;
BEGIN
   iterador:= abb;
   WHILE NOT EsVacioABBEnteros(iterador^.der) DO
         iterador:= iterador^.der;
   END;
   RETURN iterador;
END MayorABBEnteros;


-------------------------------------------------

Función MenorABBEnteros:

Código:
(*PRECONDICIÓN: El árbol no es vacío*)
PROCEDURE MenorABBEnteros(abb: ABBEnteros): ABBEnteros;
VAR iterador: ABBEnteros;
BEGIN
   iterador:= abb;
   WHILE NOT EsVacioABBEnteros(iterador^.izq) DO
         iterador:= iterador^.izq;
   END;
   RETURN iterador;
END MenorABBEnteros;


-----------------------------------

Procedimiento DesengancharNodo:

Código:
(*PRECONDICIÓN: El nodo a desenganchar no es la raíz de abb. El nodo a desenganchar debe existir en el árbol*)
PROCEDURE DesengancharNodo(n: INTEGER; VAR abb: ABBEnteros);
VAR iterador, padre: ABBEnteros;
BEGIN
   iterador:= abb;
   WHILE (iterador^.num<>n) DO
      padre:= iterador;
      IF (iterador^.num<n) THEN
         iterador:= iterador^.der;
      ELSE
         iterador:= iterador^.izq;
      END;
   END;

   IF (n>padre^.num) THEN
      padre^.der:= NIL;
   ELSE
      padre^.izq:= NIL;
   END;
END DesengancharNodo;


Ejercicio: Sigan ustedes a mano el funcionamiento de este procedimiento a modo de entender la lógica que se debe emplear con los árboles binarios. No es nada muy complicado.

Ahora si, veamos el procedimiento EliminarNodoABBEnteros. El ejemplo que pondré aquí estará largo porque diferencié por completo cada uno de los tres casos posibles a la hora de destruir un nodo. Se podría compactar bastante el código, si quieren eso pueden hacerlo como ejercicio. Yo quiero que vean todo claro y por eso lo he hecho largo pero entendible y fácil de seguir, relativamente jeje.

No describiré paso a paso este código ya que lo he comentado bastante y creo que son ampliamente capaces de seguirlo.

Código:
PROCEDURE EliminarNodoABBEnteros(n: INTEGER; VAR abb: ABBEnteros);
VAR aBorrar, padre, aIntercambiar, iteradorAuxiliar: ABBEnteros;
BEGIN
   (*Buscamos el nodo a borrar y mantenemos también una referencia hacia su    padre teniendo en cuenta que la raíz del árbol es a su vez su propio    padre.*)
   padre:= abb;
   aBorrar:= abb;
   WHILE (aBorrar^.num<>n) DO
      padre:= aBorrar;
      IF (aBorrar^.num<n) THEN
         aBorrar:= aBorrar^.der;
      ELSE
         aBorrar:= aBorrar^.izq;
      END;
   END;

   (*1-- NODO HOJA:Veo si el nodo a borrar es una hoja, es decir, si sus
   subárboles izquierdo y derecho son vacíos (primer caso)*)
   IF EsVacioABBEnteros(aBorrar^.izq) AND EsVacioABBEnteros(aBorrar^.der)    THEN
      (*Verifico si el nodo a borrar está a la izquierda o a la derecha       de su padre, a fin de ver qué puntero del padre debo actualizar*)
      IF (padre^.der=aBorrar) THEN
         DISPOSE(padre^.der);
         padre^.der:= NIL;
      ELSE
         DISPOSE(padre^.izq);
         padre^.izq:= NIL;
      END;
   
   (*2-- NODO CON UN ÚNICO HIJO: Veo si el nodo a borrar tiene un único
   hijo. (segundo caso)*)
   ELSIF (EsVacioABBEnteros(aBorrar^.der) AND (NOT
      EsVacioABBEnteros(aBorrar^.izq))) OR
      (NOT EsVacioABBEnteros(aBorrar^.der) AND          
      EsVacioABBEnteros(aBorrar^.izq)) THEN
      (*Verifico si el nodo a borrar está a la izquierda o a la derecha       de su padre*)
      IF (padre^.der=aBorrar) THEN
         (*Verifico hacia qué lado está el hijo del nodo aBorrar*)
         IF (aBorrar^.der<>NIL) THEN
            padre^.der:= aBorrar^.der;
         ELSE
            padre^.der:= aBorrar^.izq;
         END;
      ELSE
         (*Verifico hacia qué lado está el hijo del nodo aBorrar*)
         IF (aBorrar^.der<>NIL) THEN
            padre^.izq:= aBorrar^.der;
         ELSE
            padre^.izq:= aBorrar^.izq;
         END;
         DISPOSE(aBorrar);
      END;
   
   (*3-- NODO CON DOS HIJOS: Aquí estamos en el tercer caso, es decir, el
   nodo a borrar tiene dos hijos*)
   ELSE
      (*Realizaré el intercambio utilizando el nodo mayor del subárbol
      izquierdo*)
      aIntercambiar:= MayorABBEnteros(aBorrar^.izq);
      (*Desengancho el nodo que utilizaré para el intercambio*)
      DesengancharNodo(aIntercambiar^.num,abb);
      (*Actualizo los hijos del nodo a intercambiar. Para ello debo
      navegar hasta la hoja más a la izquierda del arbol aIntercambiar
      para enganchar con el subárbol izquierdo del nodo aBorrar.
      Análogo para la parte derecha*)
      
      (*Actualizo el nodo del lado izquierdo*)
      iteradorAuxiliar:= aIntercambiar;
      WHILE (NOT EsVacioABBEnteros(iteradorAuxiliar^.izq)) DO
         iteradorAuxiliar:= iteradorAuxiliar^.izq;
      END;
      iteradorAuxiliar^.izq:= aBorrar^.izq;
      
      (*Actualizo el nodo del lado derecho*)
      iteradorAuxiliar:= aIntercambiar;
      WHILE (NOT EsVacioABBEnteros(iteradorAuxiliar^.der)) DO
         iteradorAuxiliar:= iteradorAuxiliar^.der;
      END;
      iteradorAuxiliar^.der:= aBorrar^.der;
      
      (*Veo si el padre es la raíz del árbol inicial*)
      IF (padre=abb) THEN
         abb:= aIntercambiar;
      ELSE
         (*Veo cual nodo del padre debo actualizar*)
         IF (padre^.der=aBorrar) THEN
            padre^.der:= aIntercambiar;
         ELSE
            padre^.izq:= aIntercambiar;
         END;
      END;
      DISPOSE(aBorrar);
   END;
END EliminarNodoABBEnteros;




Un código largo pero con tres casos bien diferenciados. Pueden seguir cada caso por separado para ver como funciona. Yo les recomiendo que tomen lápiz y papel, se dibujen un árbol binario como el de los ejemplos y sigan este código en base a ese arbolito y a algún nodo seleccionado. Verán como comprenden todo con mucha profundidad si lo hacen de ese modo. Esto les servirá como un gran ejercicio.

La operación de eliminar un árbol binario completo se la dejo a ustedes.

A continuación les dejaré un listado de ejercicios de árboles binarios y árboles binarios de búsqueda. No son muy sencillos al hacerlos manejarán muy bien estas estructuras.

=========================================

Niveles de un árbol:

Decimos que la altura de un árbol está dada por la cantidad de niveles que tiene, es decir, cuántas veces como máximo podemos bajar hacia un nodo inferior. Veámoslo en una imagen:



Los nodos que están en un mismo nivel se llaman hermanos siempre que su padre sea el mismo. En ese ejemplo, los nodos 1 y 21 son hermanos porque están ambos en el nivel 2 y tienen como padre al nodo 20. Luego los nodos 0 y 6 son hermanos porque están en el nivel 3 y su padre es el nodo 1; el nodo 23 no es hermano de los nodos 0 y 6 porque a pesar de estar también en el nivel 3 no tiene el mismo padre que ellos, de este modo no tiene hermanos. Finalmente el nodo 22 está solito. Como ven, el nivel de un árbol está dado por la ruta más larga a una de sus hojas.

¿Se les ocurre una función que dado un árbol binario calcule cuantos niveles tiene, es decir, que calcule su altura? Más les vale que sí, porque tendrán algún ejercicio con eso.

Los veremos en la próxima lección.



Ultima edición por Kyshuo Ayame el Miércoles 02 May 2012 19:25; editado 1 vez
Volver arriba
Ver perfil del usuario Enviar mensaje privado
ale91
Usuario Iniciado


Registrado: 13 Abr 2012
Mensajes: 18

Mensaje Publicado: Jueves 26 Abr 2012 03:30

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Hola! muy buena lección, ahora tengo una duda:

Como podría hacer para copiar en "PREORDEN (izquierda, raiz, derecha)" el Arbol entero en una Lista?

Por ejemplo los TYPES son:

Código:
TYPE 
        abb = POINTER TO NodoAbb;
             NodoAbb = RECORD
                  elem:CARDINAL;
                  izq,der:NodoAbb;
             END;
TYPE
       List = POINTER TO NodoList;
               NodoList = RECORD
                      elem:CARDINAL;
                      sig:NodoList;
               END;


Se me complico mucho implementar este procedimiento!
Lo que estoy intentando de hacer, como dije al principio, es copiar recorriendo en preorder el arbol entero en una lista.

Saludos

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Adrosoad



Registrado: 06 Abr 2012
Mensajes: 3

Mensaje Publicado: Jueves 26 Abr 2012 04:26

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Buenas! la verdad que muy buena la lección! me han ayudado pila para un proyecto de facultad! estoy cursando Programacion 2 en la facultad de ingenieria (montevideo), y hace días estoy trancado con un procedimiento que tengo que "filtrar" nodos de un árbol según su monto sea mayor o igual al monto que me pasan, y tengo que devolver un árbol nuevo que no comparta memoria, el recorrido tiene que ser en "pre-orden".. El procedimiento es así:

PROCEDURE FiltrarCnjColaboradores (monto: CARDINAL; abb: TipoAbb) :TipoAbb;

Mi problema está en la recursión, realmente no sé muy bien como hacerla y no encuentro por ningún lado información de como crear un árbol a partir de otro árbol, si me podes dar una manito te agradeceria pila!! y realmente muchas gracias por las lecciones! un abrazo. Ok

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Jueves 26 Abr 2012 18:20

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Cita:
Hola! muy buena lección, ahora tengo una duda:

Como podría hacer para copiar en "PREORDEN (izquierda, raiz, derecha)" el Arbol entero en una Lista?

Por ejemplo los TYPES son:

Código:
TYPE 
        abb = POINTER TO NodoAbb;
             NodoAbb = RECORD
                  elem:CARDINAL;
                  izq,der:abb;
             END;
TYPE
       List = POINTER TO NodoList;
               NodoList = RECORD
                      elem:CARDINAL;
                      sig:List;
               END;



Se me complico mucho implementar este procedimiento!
Lo que estoy intentando de hacer, como dije al principio, es copiar recorriendo en preorder el arbol entero en una lista.

Saludos


Corregí apenas la declaración de tus tipos, fíjate bien.

Este tipo de cosas cuestan muchísimo, y es aquí donde la teoría se queda corta, porque por mucha explicación que yo pueda dar de recursividad y de como van quedando las cosas pendientes guardadas en un Stack para ser ejecutadas luego, utilizar eso para lograr cosas como esta se complica mucho.

Yo te diría que implementes un procedimiento más o menos así:

Código:
PROCEDURE ArbolALista(arbol: abb; VAR l: List);


De este modo un pseudocódigo para esta operarción sería:

Código:
Insertar raíz de arbol en l (*Conviene tener ya una operación de inserción*)
ArbolALista(arbol^.izq,l); (*Llamado recursivo con IZQ)
ARbolALista(arbol^.der,l) (*Llamado recursivo con DER)


Nota que la lista se pasa por referencia, entonces es fácil pasarla a cada llamado recursivo, de este modo siempre tenemos la misma lista. No es la forma más correcta, pero es la más sencilla. Si te sale así, luego puedes pensar en una forma de esta operación que sea así:

Código:
PROCEDURE ArbolALista(arbol: abb): List;


La recursión acá se complica, pero es la forma más TEÓRICAMENTE correcta.

===============================================

Cita:
Buenas! la verdad que muy buena la lección! me han ayudado pila para un proyecto de facultad! estoy cursando Programacion 2 en la facultad de ingenieria (montevideo), y hace días estoy trancado con un procedimiento que tengo que "filtrar" nodos de un árbol según su monto sea mayor o igual al monto que me pasan, y tengo que devolver un árbol nuevo que no comparta memoria, el recorrido tiene que ser en "pre-orden".. El procedimiento es así:

PROCEDURE FiltrarCnjColaboradores (monto: CARDINAL; abb: TipoAbb) :TipoAbb;

Mi problema está en la recursión, realmente no sé muy bien como hacerla y no encuentro por ningún lado información de como crear un árbol a partir de otro árbol, si me podes dar una manito te agradeceria pila!! y realmente muchas gracias por las lecciones! un abrazo.


Los del InCo, como siempre, son expertos en complicar las cosas de una manera impresionante. Te comento que yo también estoy haciendo esa taréa y esa función me complicó la vida. La hice, pero no la he testeado, así que todavía me va a joder.

Te tiro una idea, bien distinta a la que yo usé para que no salten con el tema de la individualidad, igualmente, si alguien más lee esto, tengan cuidado con eso. Miren que si salta COPIA marcharon, y marcharon mal porque no solo implica la pérdida del curso.

Podrías, dentro de FiltrarCnjColaboradores crear un procedimiento que funcione como este:

Código:
PROCEDURE CopiarFiltrando(cnj: CnjColaboradores; VAR copia: CnjColaboradores);


de este modo, deberías ir recorriendo el árbol cnj en orden e ir insertando en copia cada nodo que cumple la condición establecida:

Código:
CopiarFiltrando(cnj^.izq; copia); (*Llamado recursivo con IZQ*)
Evalúo si la raíz cumple la condición, en ese caso la inserto en copia.
CopiarFiltrando(cnj^.der; copia); (*Llamado recursivo con DER*)


La idea que manejo acá es la misma que le expliqué al lector anterior.
Vas a tener que ver una cuestión: Si la raíz no cumple la condición entonces vas a tener que insertar el nodo más grande del subárbol izquierdo en lugar de la raíz. Eso te va a complicar un poco, pero la idea es esa.

Espero que esto te ayude un poco.

Saludos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
ale91
Usuario Iniciado


Registrado: 13 Abr 2012
Mensajes: 18

Mensaje Publicado: Jueves 26 Abr 2012 19:37

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Muchas gracias por la respuesta, ya implemente el procedimiento como me dijiste me pareció una muy buena idea, no lo copio acá por el tema de individualidad pero tenes un correo para mandártelo para saber si es correcto?

saludos disculpa la molestia

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Jueves 26 Abr 2012 19:44

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Mandámelo por mensaje privado.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
ale91
Usuario Iniciado


Registrado: 13 Abr 2012
Mensajes: 18

Mensaje Publicado: Jueves 26 Abr 2012 20:36

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

ok

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Adrosoad



Registrado: 06 Abr 2012
Mensajes: 3

Mensaje Publicado: Jueves 26 Abr 2012 21:35

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Muchas gracias loco!! después de darle mil vueltas me salió!! muy buena la de hacer un procedimiento adentro de la funcion para poder recorrer todo el arbol, si no me tirabas ese pique no lo sacaba ni ahi!! Aplauso jeje tenia miedo de hacer la pregunta porque pensé que eras uno de los profesores del Inco! y la verdad que si, buscan la forma de complicarte! un abrazo, vamos a ver como sigo con lo que falta!!

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Adrosoad



Registrado: 06 Abr 2012
Mensajes: 3

Mensaje Publicado: Sábado 28 Abr 2012 01:40

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Buenas! perdona que te joda! tengo una consulta! porque en el test stress me da error de memoria cuando prueba el filtro, donde puede estar el error? se supone que en el filtro cuando no cumple la condición tengo que borrar el nodo que no la cumple? porque solamente inserto en la lista nueva los nodos que si la cumplen! me tiene medio loco eso! un abrazo

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Sábado 28 Abr 2012 02:35

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

No tengo forma de saber eso... tenés que usar el depurador y ver en donde salta el error para detectar qué es lo que pasa...

Laburo tedioso, chino y espantoso... pero no hay otra...

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Martin1991
Usuario Iniciado


Registrado: 24 Abr 2012
Mensajes: 10

Mensaje Publicado: Martes 01 May 2012 21:28

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Estás seguro que el de eliminar nodos esta bien? porque probe tu procedimiento y con el debugger se me queda en el While de desenganchar

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Miércoles 02 May 2012 19:18

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Pues el algoritmo tiene algunos errores que he visualizado en estos días, pero no justamente en el trozo de código que tú mencionas.

Editaré la lección para dejar constancia.

Saludos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Juan333



Registrado: 20 Abr 2013
Mensajes: 4

Mensaje Publicado: Sábado 20 Abr 2013 17:37

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Hola estuve leyendo las lecciones porque estoy haciendo el curso en la faculatad y tengo un problema con identificar los niveles en un arbol binario de busqueda.

No se si se puede utilizar un contador con recursion

Gracias saludos

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Domingo 21 Abr 2013 00:00

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Pues sí, en recursión puedes usar cualquier cosa. No es tan fácil ver cómo lograrlo. Iterativamente uno ya está acostumbrado a poner contadores y demás.

La recursión tienes que pensarla "de antemano". Imagina que tienes un árbol binario común y corriente. Intuitivamente vos ya sabés lo que es un nivel y por tanto a mano es fácil contarlos



Ese árbol de ahí tiene 4 niveles (3 si pensamos en que el primer nivel es el 0). ¿Cómo los contas? Bueno, pensalo así:

Dado un nodo raíz:

  • Cuento los niveles del subárbol izquierdo.
  • Cuento los niveles del subárbol derecho.
  • La cantidad de nodos de mi árbol es el máximo valor de los anteriores más 1 (el nivel actual)


Por ejemplo, según el árbol anterior, cuando estoy en la raíz (nodo 20), cuento los niveles del subárbol izquierdo (tiene 2), cuento los niveles del subárbol derecho (tiene 3); de esos dos valores el mayor es el 3 así que mi árbol tiene 3 nivles más el actual, o sea, 4.

Ahora me dirás: Todo lindo, pero para contar los niveles de un árbol tengo que contar los niveles de sus dos subárboles, pero lo que yo quiero saber es ¡¡¡¡COMO CONTAR NIVELES!!!

La idea es esa que te dije (justamente recursiva), para contar niveles de un árbol cuento los de sus subárboles. La cuestión de la recursión es identificar los casos base, es decir, aquellos árboles en que la cantidad de niveles se deduce directo ¿Cuales son?

Si un árbol es vacío no tiene niveles, por tanto tiene 0 niveles.
Si un árbol es una hoja tiene un nivel, o sea 1.

Entonces, un pseudocódigo sería:

  • Si el árbol es vacío retorno 0
  • Si el árbol es una hoja retorno 1
  • Si el árbol no es vacío ni hoja:
    • Cuentos los niveles del izquierdo
    • Cuento los niveles del derecho
    • Retorno el mayor de esos dos valores más 1.


Pensalo un poco a ver que sale.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Juan333



Registrado: 20 Abr 2013
Mensajes: 4

Mensaje Publicado: Domingo 21 Abr 2013 18:51

Título del mensaje: Re: Lección 56: Árbol Binario - Recorrido común - Eliminació

Responder citando

Gracias!! creo que ahora pude hacer para averiguar el nivel de un nodo.
ahora mi problema es que yo utilizando recursion llego hasta el nodo que voy a imprimir pero cuando voy a averiguar el nivel antes de imprimirlo necesito darle la raiz principal del arbol y no se como hacer una copia o alguna forma para tener un puntero que empiece siempre de la raiz principal


Muchas gracias! saludos

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Responder al Tema Ir a página 12Siguiente
Mostrar mensajes anteriores:   
Ir a:  
Todas las horas están en GMT + 2 Horas

Temas relacionados

Tema Autor Foros Respuestas Publicado
El foro no contiene ningún mensaje nuevo

[Duda] Ejercicios Archivo Binario - En C

Pedrolo C, C#, Visual C++ 1 Viernes 03 Nov 2017 04:17 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Ayuda Punto flotante a binario´Vc++

Kristian C, C#, Visual C++ 1 Lunes 05 Oct 2015 22:12 Ver último mensaje
El foro no contiene ningún mensaje nuevo

interpretar texto binario

gilbertohilgemann Python 1 Viernes 12 Jun 2015 05:01 Ver último mensaje
El foro no contiene ningún mensaje nuevo

arbol de expresiones

marcela Java 0 Viernes 02 Ene 2015 07:15 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Convertir de decimal a binario (lenguaje C)

DanielC C, C#, Visual C++ 10 Martes 01 Jul 2014 15:39 Ver último mensaje
Panel de Control
No puede crear mensajes, No puede responder temas, No puede editar sus mensajes, No puede borrar sus mensajes, No puede votar en encuestas,