Arboles

ESTRUCTURA DE DATOS

ESTRUCTURAS NO LINEALES ÁRBOLES

Árboles binarios

Un árbol binario es un conjunto finito de elementos que o esta vació o esta dividido en tres subconjuntos desarticulados. El primer subconjunto contiene un solo elemento llamado raíz del árbol. Los otros dos son en sí mismos árboles binarios, llamados subárboles izquierdo y derecho del árbol original. Unsubárbol izquierdo o derecho puede estar vacío. Cada elemento de un árbol binario se llama nodo del árbol.

Un árbol binario

.
Este árbol consiste de nueve nodos y tiene a A como raíz .Un subárbol izquierdo tiene a B con raíz y su subárbol derecho a C. Esto queda señalado por las dos ramas que salen de A: hacia B a la izquierda y hacia C a la derecha. La ausencia de ramas indica quees un subárbol vacío Por ejemplo, tanto el subárbol izquierdo del árbol binario que tiene raíz en C como el subárbol derecho del árbol binario que tiene raíz en E están vacíos. Los árboles binarios con raíz en D, G, H e I tiene subárboles derecho e izquierdo vacíos.

Si A es la raíz de un árbol binario y B es la raíz de su subárbol derecho o izquierdo entonces A se llama el padre de B yB el hijo izquierdo o derecho de A. Un nodo que no tiene hijos (como D, G, H o I de la figura anterior)se llama hoja. El nodo n1 es un ancestro del nodo n2(y n2 es un descendente de n1) si n1 es el padre de n2 o el de algún ancestro de n2. Por ejemplo, el árbol anterior, A es un ancestro de G y H es un descendiente de C, pero E no es ni ancestro ni descendiente de C. Un nodo n2 es undescendiente izquierdo de un nodo n1 si n2 es el hijo izquierdo de n1 o un descendiente del hijo izquierdo de n1. Un descendiente derecho puede definirse de manera similar. Dos nodos son Hermanos si son hijos derecho e izquierdo del mismo padre.

Aun que los árboles naturales crecen con sus raíces en la tierra y sus hojas en el aire, los científicos de la computación representan, casi a niveluniversal, las estructura de datos como árboles con la raíz en la cúspide y las hojas en el fondo. La dirección de la raíz hacia las hojas se llama “hacia abajo”, y de las hojas a la raíz “hacia arriba”. Ir de las hojas a la raíz se llama “trepar” a un árbol; e ir de la raíz a las hojas,”descender” de un árbol.

Si un nodo que no es hoja de un árbol binario tiene subárboles izquierdo y derechono vacíos, el árbol se llama Árbol estrictamente binario.

Un árbol estrictamente binario.

Estructuras que no son árboles binarios.

A)

B)

Operaciones con árboles binarios

Existen varias operaciones primitivas que pueden aplicarse a árboles binarios. Si p es un apuntador a un nodo nd de un árbol binario, la función info(p) da como resultado los contenidos de nd. Lasfunciones left(p), right(p), father(p), y brother(p)dan como resultado apuntadores al hijo izquierdo, hijo derecho, padre y hermano de nd, respectivamente. Estas funciones dan como resultado el apuntador nulo si nd no tiene hijo izquierdo, hijo derecho o hermano. Como consecuencia, las funciones lógicas isleft(p) e isright(p) dan como resultado verdadero (true) si nd es hijo izquierdo o derecho,respectivamente, de algún otro nodo del árbol, y falso (false) en caso contrario.
Obsérvese que las funciones isleft(p), is right(p) y brother(p) pueden implantarse mediante las funciones left(p), right(p) y father(p). Por ejemplo isleft puede implantarse como sigue:

q= father(p);
If (q==null)
Return(false);
If (left(q) == p) /* p a punta a la raíz*/Return(true);
Retun(false);

O, de manera más simple, como father(p)&&==left(father(p)).isright puede implantarse de manera similar, o llamando a isleft.brother(p) puede implantarse mediante isleft o isright como sigue:

If (father(p)= = null)
Return(null); /*p apunta a la raiz*/
If (isleft(p))
Return (right(father(p)));
Return(left(father(p)));

Las...