A mis hermanos quienes siempre están a mi lado apoyándome incondicionalmente.

...

La profundidad o altura (o altura) de un árbol T es el número máximo de nodos de una rama de T. Equivale a 1 más que el mayor numero de nivel de T.

Dos árboles binarios T y T’ se dice que son similares si tienen la misma estructura o , en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.

La terminología de relaciones familiares, de teoría de grafos y horticultura se usa para los árboles generales de la misma forma que para los árboles binarios. En particular, si N es un nodo con sucesores S 1, S 2,…, S m, se dice que N es el padre de los S i , los S i son hijos de N y los S i son hermanos unos de otros.

El término "árbol" aparece, con significados ligeramente diferentes, en muchas áreas diferentes de las matemáticas y de la informática.

MARCO TEORICO

ARBOL

Un árbol es una colección de elementos, llamados nodos, uno de los cuales se distingue con el nombre de raíz, los cuales mantienen una relación (parentesco) que define una estructura jerárquica entre ellos. F De manera formal, un árbol se puede definir en forma recursiva mediante las reglas siguientes: flEl conjunto vacío de nodos es un árbol, llamado nulo o vacío. flUn nodo es un árbol, el cual es, asimismo, la raíz del árbol. flSi n, es un nodo y T1 , T2 , . . . , Tk son árboles con raíces n1 , n2 , . . . , nk , respectivamente, se puede construir un nuevo árbol haciendo n el padre de los nodos n1 , n2 , . . . , nk . /En este árbol n es la raíz y T1 , T2 , . . . , Tk son los subárboles de la raíz. Los nodos n1 , n2 , . . . , nk se conocen como los hijos del nodo n.

Algunas Definiciones

- Un camino de un nodo n1 a un nodo nk es una secuencia de nodos n1 , n2 , ... , nk de tal manera que ni es padre de ni+1 para i = 1, 2, . . . , k-1.

- La longitud de un camino es uno menos que el número de nodos en el camino.

- Existe un camino de longitud 0 de un nodo a sí mismo.

- Si existe un camino de un nodo a a un nodo b, entonces se dice que a es un ancestro de b y que b es un descendiente de a.

- Un ancestro o descendiente de un nodo diferente de sí mismo se dice que es un ancestro o descendiente propio, respectivamente.

- En un árbol la raíz es el único nodo que no tiene ancestros propios.

- Un nodo sin descendientes propios se conoce como una hoja.

- Un subárbol de un árbol es un nodo junto con todos sus descendientes.

- El peso de un nodo en un árbol es la longitud del camino más largo del nodo a una hoja.

- El peso de un árbol es el peso de la raíz.

- La profundidad de un nodo es la longitud del camino único de la raíz al nodo.

- La profundidad de un árbol es la profundidad de la hoja más profunda.

ARBOLES BINARIOS

Un árbol binario es un conjunto finito de elementos, el cual está vacío o dividido en tres subconjuntos separados:

• El primer subconjunto contiene un elemento único llamado raíz del árbol.

• El segundo subconjunto es en sí mismo un árbol binario y se le conoce como subárbol izquierdo del árbol original. Estructuras de Datos Ricardo Ruiz Rodríguez 68

• El tercer subconjunto es también un árbol binario y se le conoce como subárbol derecho del árbol original.

El subárbol izquierdo o derecho puede o no estar vacío.

Cada elemento de un árbol binario se conoce como nodo del árbol.

La Ilustración 2 muestra una representación de un árbol binario.

Ejercicio: ¿Una lista podría ser un árbol binario? ¿Una lista doblemente enlazada? ¿Por qué? ¿Qué otros ejemplos podrían o no considerarse como árboles binarios?

Ilustración 2 Árbol binario.

Si B es la raíz de un árbol binario y D es la raíz del subárbol izquierdo/derecho, se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B.

A un nodo que no tiene hijos, tal como A o C de la Ilustración 2, se le conoce como hoja.

Un nodo n1 es un ancestro de un nodo n2 (y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2.

Recorrer un árbol de la raíz hacia las hojas se denomina descender el árbol y al sentido opuesto ascender el árbol. Un árbol estrictamente binario es aquel en el que cada nodo que no es hoja, tiene subárbols izquierdo y derecho que no están vacíos.

Un árbol estrictamente binario con n hojas siempre contiene 2n-1 nodos.

El nivel de un nodo en un árbol binario se define del modo siguiente:

1.La raíz del árbol tiene el nivel 0.

2.El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.

La profundidad o altura de un árbol binario es el máximo nivel de cualquier hoja en el árbol.

Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.

Clasificación de arboles Binarios

- Arbol Binario Distinto.

- Arbol Binario Similares.

- Arbol Binario Equivalentes.

- Arbol Binario Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Arbol Binario Distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.