Semana 8 estructura de datos

Árboles

José Hernán Fuentes Contreras

Estructuras de datos

Instituto IACC

30 de diciembre de 2019

Desarrollo

1. Construir un gráfico de árbol binario, con la siguiente secuencia:

22 - 15 - 3 - 8 - 40 - 45 - 13 - 20 - 30 - 1 - 7 - 34 - 48 - 53 - 9 - 23 - 12 - 51 - 4 - 10.

[pic 1]

Como regla para la construcción de este grafo, el primer valor queda como raíz, en la medida que se avanza por la secuencia, pregunto si el valor es menor o mayor que los elementos ingresados al árbol, siendo menor, se ubican hacia la izquierda, y siendo mayor, avanzan hacia la derecha, paso a paso se ejecutó de la siguiente forma:

• El 22 queda como raíz.
• El 15 es menor que 22, a la izquierda.
• El 3 es menor que 22 y que 15, a la izquierda de este último.
• El 8 es menor que 22, menor que 15 y mayor que 3, derecha de este.
• El 40 es mayor que 22, a la derecha de este.
• El 45 es mayor que 22 y mayor que 40, a la derecha de este.
• El 13 es menor que 22, menor que 15, mayor que 3 y mayor que 8, derecha de este último.
• El 20 es menor que 22 y mayor que 15, derecha.
• El 30 es mayor que 22, menor que 40, a la izquierda de este.
• El 1 es menor que 22, menor que 15, menor que 3, a la izquierda de este.
• El 7 es menor que 22, menor que 15, mayor que 3, menor que 8, a la izquierda de este.
• El 34 es mayor que 22, menor que 40, mayor que 30, a la derecha de este.
• El 48 es mayor que 22, mayor que 40, mayor que 45, a la derecha de este.
• El 53 es mayor que 22, mayor que 40, mayor que 45, mayor que 48, a la derecha de este.
• El 9 es menor que 22, menor que 15, mayor que 3, mayor que 8, menor que 13.
• El 23 es mayor que 22, menor que 40, menor que 30.
• El 12 es menor que 22, menor que 15, mayor que 3, mayor que 8, menor que 13, mayor que 9.
• El 51 es mayor que 22, mayor que 40, mayor que 45, mayor que 48 y menor que 53.
• El 4 es menor que 22, menor que 15, mayor que 3, menor que 8, menor que 7.
• El 10 es menor que 22, menor que 15, mayor que 3, mayor que 8, menor que 13, mayor que 9 y menor que 12.

Considere que menor=izquierda y mayor =derecha, para seguir el recorrido en la inserción de los valores

2a. La figura de abajo, representa un gráfico de árbol binario, por lo observado en la disposición de los nodos, ya que cada nodo no posee más de dos descendientes. También se observa los valores que contienen los nodos, al orden en el que están ubicados, los números de menor valor en el subárbol izquierdo, y los de mayor valor, en el subárbol derecho.

[pic 2]

2b. Tabla comparativa de estructuras tipo árbol.

3. Pre orden de la estructura del ejercicio 1.

[pic 3]

22 - 15 - 3 - 1 - 8 - 7 - 4 - 13 - 9 - 12 - 10 - 20 - 40 - 30 - 23 - 34 - 45 - 48 - 53 - 51.

Como se estudió en la semana anterior, el recorrido en pre orden comienza con la raíz, bajando al nodo izquierdo, hasta llegar a NULL, para después pasar al lado derecho. En el grafo se detalla el recorrido.

...