programacion
Árbol binario
Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave delnodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.
Representación grafica
La representación gráfica de un árbol binario es la siguiente:Representación en Memoria
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registrosque contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cadanodo se representa gráficamente de la siguiente manera:
Recorrido de un Árbol Binario
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuenciadistinta para analizar el árbol como se puede ver a continuación:
INORDEN
Recorrer el subarbol izquierdo en inorden.
Examinar la raíz.
Recorrer el subarbol derecho en inorden.PREORDEN
Examinar la raíz.
Recorrer el subarbol izquierdo en preorden.
recorrer el subarbol derecho en preorden
POSTORDEN
Recorrer el subarbol izquierdo en postorden.Recorrer el subarbol derecho en postorden.
Examinar la raíz.
A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.
Inorden: GDBHEIACJKF
Preorden:ABDGEHICFJK
Postorden: GDHIEBKJFCA
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol...
Regístrate para leer el documento completo.