4. Árboles

4.1 Introducción

En este capítulo se definirán estructuras lineales como arreglos, listas enlazadas, pilas y colas. Además de las estructuras no lineales como árboles y grafos.

4.2 Árboles generales

4.2.1 Definiciones

Un árbol es una estructura de datos no lineal y homogénea en el que cada elemento puede tener varios elementos posteriores denominados nodos, pero tan sólo puede tener un elemento anterior.

Árbol

4.2.2 Orden de los nodos

4.3 Árboles binarios

Un Árbol Binario es aquel donde cada nodo tiene como máximo dos nodos. Como se muestra en la figura.

Árbol binario

4.4 Recorridos de árboles: orden previo (postorder), orden simétrico (inorder) y orden posterior (postorder)

Recorrer un árbol binario consiste en acceder una sola vez a todos sus nodos. Esta operación es básica en el tratamiento de árboles ya que nos permite por ejemplo imprimir o eliminar toda la información almacenada en el árbol.

• Recorrido preorden

- Procesar el nodo raíz R

- Recorrer el Subárbol izquierdo de R en Preorden.

- Recorrer el Subárbol derecho de R en Preorden.

• Recorrido inorden

- Recorrer el Subárbol izquierdo de R en Inorden.

- Procesar el nodo raíz R

- Recorrer el Subárbol derecho de R en Inorden.

• Recorrido postorden

- Recorrer el Subárbol izquierdo de R en Postorden.

- Recorrer el Subárbol derecho de R en Postorden.

- Procesar el nodo raíz R.

 

4.5 Recorrido por niveles

Recorridos en amplitud (o por niveles)

En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.

El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola.

Representacion en ‘c’

4.6 Longitud de camino; Algoritmo de Huffman

Árbol de Huffman generado para las frecuencias de apariciones exactas del texto "Esto es un ejemplo de árbol de Huffman". Las frecuencias y códigos de cada carácter se muestran abajo. Codificar esta frase usando este código requiere 156 bits, sin contar con el espacio para el árbol.

4. 7 Ejemplos

Aquí les dejo un video, esta super recreativo por si no le entienden.