CONOCIENDO LA ESTRUCTURA DE UN ARBOL

• Los árboles representan estructuras dinámicas de datos, debido a que pueden cambiar en tiempo de ejecución y no lineales puesto que a cada elemento del árbol pueden seguirle varios elementos.

ÁRBOLESUn árbol es una estructura jerárquica aplicada sobre una colección de elementosu objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro,etc.

Formalmente se define un arbol de tipo T como una estructura homogenea que es la concatenación de un elemento de tipo T con un número finito de arboles disjuntos llamados subarboles.

A

B C

D E F G H

I J LK

Los árboles tienen una gran variedad de aplicaciones.Para construir un árbol genealógico, para el análisis de circuitos eléctricos, para evaluar expresiones aritméticas, para numerar los capítulos y secciones de un libro, etc.Gráficamente puede representarse una estructura de diferentes formas y todas ellas equivalentes.Por medio de grafos, esta última representación es la que comúnmente se utiliza; y ha originado el término árbol por su parecido abstracto con el vegetal (raíz, ramas, hojas).

APLICACIONES

Luis

Juan Pedro María

Mario José Mateo

Nodo

Arista Es el primer nodo del árbol. Se caracteriza por ser el único nodo que no tiene predecesores.ta

Camino simple

Elías

Nivel 1

Nivel 2

Nivel 3

Nivel 4

Figura 1.1: Árbol genealógico

ARBOL GENERAL

CARACTERÍSTICAS Y PROPIEDADES DE LOS ÁRBOLES

a) Todo árbol que no es vacío, tiene un único nodo raíz.b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado

por el nodo Y. En este caso es común utilizar la expresión X es hijo de Y.c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y.

En este caso es común utilizar la expresión X es padre de Y.d) Se dice que todos los nodos que son descendientes directos (hijos) de un

mismo nodo (padre), son HERMANOS.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 DE Á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 en nivel 1.i) ALTURA del árbol es el máximo número de niveles de todos los nodos del

árbol.

Ejemplo: ÁRBOL GENERAL.

Dado el árbol general de la figura de abajo, se hacen sobre él las siguientes consideraciones.

I

D

B

A

C

H

L

E F

J K

G

1.- 1.- A A es la raíz del árbol.es la raíz del árbol. 2.- 2.- B B es hijo de A. es hijo de A. C C es hijo de A. es hijo de A. D D es hijo de B. es hijo de B. E E es hijo de B. es hijo de B. L L es hijo de H.es hijo de H. 3.- 3.- A A es padre de B. es padre de B. BB es padre de D. es padre de D. D D es padre de I. es padre de I. C C es padre de G. es padre de G. H H es padre de L.es padre de L. 4.- 4.- B y C B y C son hermanos. son hermanos. D,E y F D,E y F son hermanos. son hermanos. G y H G y H son hermanos. son hermanos. J y K J y K son hermanos.son hermanos. 5.- 5.- I, E, J, K, G y L I, E, J, K, G y L son nodos terminales u hojas.son nodos terminales u hojas. 6.- 6.- B, D, F, C y H B, D, F, C y H son nodos interiores.son nodos interiores. 7.- El grado del nodo 7.- El grado del nodo A A es 2. es 2. B B es 3. es 3. C C es 2. es 2. D D es 1. es 1. E E es 0. es 0. El grado del árbol es 3.El grado del árbol es 3. 8.- El nivel del nodo 8.- El nivel del nodo A A es 1. es 1. B B es 2. es 2. D D es 3. es 3. C C es 2. es 2. L L es 4.es 4. 9.- La altura del´árbol es 9.- La altura del´árbol es 4.4.

ARBOLES BINARIOS

• Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho.

• Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.

• Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Tipos de Arboles Binarios

ARBOL BINARIO DISTINTOS:

Dos árboles binarios son distintos cuando sus estructuras son diferentes.

Arbol Binario EquivalenteSon aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:Arbol Binario EquivalenteSon aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

ARBOL BINARIO EQUIVALENTE.

Son aquellos arboles que son similares y que además los nodos contienen la misma información.

• ARBOL BINARIO SIMILAR.

• Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

• ARBOL BINARIO COMPLETO

• Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

•