Unidad 5: Arboles Binarios

Definición:

Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:

El Árbol Binario es Vació si no tiene ningún elemento en el.

El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.

Los Árboles tiene 3 Recorridos Diferentes los cuales son:

Pre-Orden

In-Orden

Post-Orden

Pre-Orden

Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:


PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprimir “Árbol Vació…” y Salir

Repetir mientras Temp ≠ Nulo

Imprimir Arbol[Temp]

Si Der[Temp] ≠ Nulo

Top → Top + 1

Pila[Top] → Der[Temp]

Si Izq[Temp] ≠ Nulo

Temp → Izq[Temp]

Si no:

Temp → Pila[Top];

Top → Top - 1

Fin del ciclo

Salir


Diagrama:

image593.jpg

Corrida:

image552.jpg

In-Orden

Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:


PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprmir “Arbol Vacio…” y Salir

Etiqueta:

Mientras Temp ≠ Nulo

Top → Top + 1

Pila[Top] → Temp

Temp → Izq[Temp]

Fin del ciclo

Temp → Pila[Top]

Top → Top - 1

Mientras Temp ≠ Nulo

Imprimir Arbol[Temp]

Si Der[Temp] ≠ Nulo

Temp → Der[Temp]

Ir a Etiqueta

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Salir


Diagrama:

image594.jpg

Corrida:

image553.jpg

In-Orden

Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la Raiz.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:


PostOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprimir “Arbol Vacio…” y Salir

Etiqueta:

Mientras Temp ≠ Nulo

Top → Top + 1

Pila[Top] → Temp

Si Der[Temp] ≠ Nulo

Top → Top + 1

Pila[Top] → - (Der[Temp])

Temp → Izq[Temp]

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Mientras Temp ≥ 0

Imprimir Arbol[Temp]

Si Arbol[Temp] = Info[Raiz]

Salir

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Si Temp < 0

Temp = -(Temp)

Ir a Etiqueta

Salir


Diagrama:

image595.jpg

Corrida:

image554.jpg

Búsqueda

Definición:

La Búsqueda es Similar a todas los Métodos anteriores de Búsqueda, simplemente efectúa un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos.

Detalle:

El Algoritmo de Búsqueda compara el Elemento a buscar con cada uno de los datos de nuestro Árbol, compara si el Elemento con el Nodo Raíz, si no se encuentra en la Raíz… compara Elemento contra la Raíz para empezar a viajar por el Árbol respectivamente, usa un método similar al anterior hasta encontrar el Elemento. De otra forma la búsqueda es fallida.

Algoritmo:


Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem)

Si Raiz = Nulo

Imprimir “Arbol Vacio”

Pos → Nulo

Pad → Nulo

Regresar Pos y Pad

Salir

Si Elem = Arbol[Raiz]

Imprimir “Elemento Encontrado”

Pos → Raiz

Pad → Nulo

Regresar Pos y Pad

Salir

Si Elem < Arbol[Raiz]

Temp → Izq[Raiz]

Temp2 → Raiz

Si no:

Temp → Der[Raiz]

Temp2 → Raiz

Mientras Temp ≠ Nulo

Si Elem = Arbol[Temp]

Imprimir “Elemento Encontrado…”

Pos → Temp

Pad → Temp2

Regresar Pos y Pad

Salir

Si Elem < Arbol[Temp]

Temp2 → Temp

Temp → Izq[Temp]

Si no:

Temp2 → Temp

Temp → Der[Temp]

Fin del ciclo

Imprimir “Elemento no Encontrado…”

Pos → Nulo

Pad → Temp2

Regresar Pos y Pad

Salir


Diagrama:

image596.jpg

Corrida:

image555.jpg

Programa click here:

 


 


Driven by DokuWiki

Politica de Privacidad