Estructura de Datos con Orientación a Objetos

Árboles

6. Árboles 6.1 Introducción. Hasta el momento sólo se han estudiado estructuras lineales estáticas y dinámicas de datos: a un elemento sólo le sigue otro elemento. Al analizar la estructura árbol se introduce el concepto de estructura de ramificación entre nodos. Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. En la tabla 6.1 se presentan las estructuras de datos más importantes clasificadas de acuerdo a su estaticidad y dinamismo. Tabla 6.1 …ver más…

e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja. f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior. g) Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol. h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. i) Altura del árbol es el máximo número de niveles de todos lo nodos del árbol. A continuación se presenta un ejemplo para clarificar estos conceptos. Ejemplo 6.1 Dado el árbol general de la figura 6.2 se hacen sobre él las siguientes consideraciones: A I J K L D B C A

E

F

G

H

B

C

D

E

F

G

H

I

J

K

L

2

Estructura de Datos con Orientación a Objetos

Árboles

Figura 6.2 Árbol general

1. 2.

3.

4.

5. 6. 7.

A es la raíz del árbol. B es hijo de A. C es hijo de A. D es hijo de B. E es hijo de B. L es hijo de H. A es padre de B. B es padre de D. D es padre de I. C es padre de G. H es padre de L. B y C son hermanos. D, E y F son hermanos. G y H son hermanos. J y K son hermanos. I, E, J, K, G y L son nodos terminales u hojas. B, D, F, C y H son nodos interiores. El grado del nodo A es 2. El grado del nodo B es 3. El grado del nodo C es 2. El grado del nodo D es 1. El grado del nodo E es 0. El grado del