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:
Corrida:
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:
Corrida:
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:
Corrida:
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:
Corrida:
Trabajo corregido
ResponderEliminar