Arboles

ÁRBOLES.
En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo aes padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que bes hijo dea). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipoespecial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.

ÁRBOLES BINARIOS
Un árbol binario Tse define como un conjunto finito de elementos, llamados nodos, de forma que:
a. Tes vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
b. Tcontiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un parordenado de árboles binarios disjuntos T1 y T2.

Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, sub-árboles izquierdo y derecho de la raíz R. Si T1 no es vació, entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.

Observe que :
a. B es un sucesor izquierdo y C un sucesor derecho del nodo A.b. El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C , G, H, J, K y L.

Figura (1)

Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólo tienen un sucesor , y los nodos D,F, G,L y K no tienen sucesores. Los nodos sin sucesores se llaman nodosterminales.

La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los sub-árboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho. Más aun, si N es un nodo terminal, ambos árboles están vacíos.

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

Frecuentemente se usa una terminología de relaciones familiares para describir las relaciones entre los nodos de un árbol T. En particular, suponga que N es un nodo de T con un sucesor izquierdo S1 y un sucesor derecho S2. Entonces Nse llama padre de S1 y S2. Análogamente, S1 se llama el hijo izquierdo de N y S2 el hijo derecho de N. Es mas, S1 y S2 se dice que son hermanos. Cada nodo N de un árbol binario T, excepto la raíz, tiene un único padre, llamado predecesor de N.
Los términos descendientes y antecesor tienen su significado usual. Así, un nodo L se dice descendiente de un nodo N ( y N se dice antecesor de L) siexiste una sucesión de hijos desde N hasta L. En particular, L se dice descendiente izquierdo o derecho de N dependiendo de si pertenece al subárbol izquierdo o al derecho de N.

También se usa esa terminología de teoría de grafos y de horticultura para un árbol binario T. específicamente, la línea dibujada entre un nodo N de T y un sucesor suyo se llama ariste, y una secuencia de aristasconsecutivas se denomina camino. Un nodo terminal se llama hoja y un camino que termina en una hoja se llama rama.

Cada nodo de un árbol binario T tiene asignado un número de nivel, de la forma que sigue. A la raíz R del árbol T se le asigna el numero de nivel 0, y al resto de los nodos se le asigna un numero de nivel que es mayor en 1 que el numero de nivel de su padre. Más aun, aquellos nodos con el...