termo

UNIVERSIDAD DE EL SALVADOR
FACULTAD DE INGENIERIA Y ARQUITECTURA
ESCUELA DE INGENIERIA DE SISTEMAS INFORMATICOS
ESTRUCTURAS DE DATOS
GUIA DE LABORATORIO No. 7
ARBOLES BINARIOS
Introducción:
Un árbol es una estructura que organiza sus elementos, formando jerarquías. Es ramificada o no lineal porque a
cada elemento le puede suceder uno o varios elementos, llamados nodos. Los árboles sonestructuras de datos
dinámicas porque pueden cambiar durante la ejecución de un programa.
Los árboles tienen una gran variedad de aplicaciones, por ejemplo para construir un árbol genealógico, para el
análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro. La representación más
comúnmente utilizada es por medio de grafos que ha originado el término árbol por suparecido abstracto con
un árbol real que posee raíz, ramas, hojas.
Objetivo: Estudiar los conceptos, propiedades y operaciones, revisados en clase, relacionadas a árboles
generales y binarios mediante la solución de ejercicios prácticos.
La presente guía está formada de tres partes: La primera comprende la revisión de conceptos relacionados a
árboles generales, la segunda parte ejercicios deprogramación en árboles binarios. La tercera parte incluye un
programa en lenguaje C, en el cual se han implementado las propiedades de los árboles binarios. Para que sea
analizado durante la sesión de laboratorio.
Parte I: Resuelva los siguientes ejercicios dejando constancia del procedimiento utilizado.
1. Dadas las siguientes secuencias de nodos obtenidas por los recorridos preorden, inorden ypostorden,
dibuje el árbol correspondiente:
Preorden: P-R-A-C-H-T-O-M
Inorden: A-R-H-C-P-O-T-M
Postorden: A-H-C-R-O-M-T-P
2. Dados los siguientes árboles generales (unos representados en forma de grafo y otro representado
como anidación de paréntesis, identifique sus propiedades. Nodos hoja, peso del árbol, altura, nodos
internos, nodos por nivel, nodos hermanos, grados del árbol, grado delnodo C, Longitud de camino
interno y Externo, etc.

a)

b)

D

62
A

U

B

C

I

R

H

O

P

Q

49
31
10

78
55

37

69

90

66

96

S
93

c) (A(B(E,F(K)),C(G(L,M(Q,R),N)),D(H,I(O(S),P))))
ESTRUCTURAS DE DATOS

CICLO II/2014
1

3. Dada las siguientes claves que representan los signos del zodíaco, construya un árbol binario de
búsqueda:piscis- acuario-capricornio-cáncer-sagitario-virgo-leo-escorpión-libra-géminis-aries-tauro
4. Dado el árbol binario de búsqueda de la figura 1, elimine las claves: 49 -37-62-90-78
Parte II. Ejercicios de Programación. Realice lo que se pide en los siguientes literales. Para verificar el
funcionamiento de los programas y procedimientos, debe crear las funciones de inserción de nodos yvisualización de árboles binarios.
5. Escriba un programa que calcule cuántos nodos tiene un árbol binario, cuál es su máximo valor y cuál
es el promedio de los nodos. Nota: Los nodos tienen valores enteros.
6. Escriba un procedimiento que visite los nodos de un árbol binario de la siguiente forma: raíz, rama
derecha y rama izquierda.
7. Escriba un procedimiento que realice lo siguiente:
a) Imprima lashojas de un árbol binario.
b) Imprima los nodos internos de un árbol binario.
8. Escriba tres procedimientos que efectúen los recorridos en preorden, inorden y postorden en forma
iterativa en lugar de recursiva (deberá utilizar una pila).
9. Escriba un programa que cargue los nodos de un árbol binario en un arreglo unidimensional. Cuide que
se mantenga la relación padre-hijo entre los nodos.10. Escriba una función que determine si dos árboles binarios son equivalentes.
11. Se tiene almacenada toda la ascendencia de Carlos en un árbol binario. Se ha seguido el siguiente
criterio (para Carlos y todos sus progenitores): en la rama izquierda se ha guardado el nombre de la
madre y en la rama derecha el nombre del padre. Por ejemplo: el árbol genealógico de Carlos está
representado...