1. T es vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
2. T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.

1. B es un sucesor izquierdo y C un sucesor derecho del nodo A.
2. 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 nodos terminales.

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 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.

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) si existe 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 aristas consecutivas 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 mismo número de nivel se dice que pertenecen a la misma generación.

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 termino "árbol" aparece, con significados ligeramente diferentes, en muchas áreas diferentes de las matemáticas y de la informática. Aquí asumimos que nuestro árbol general T esta enraizado, es decir, que T tiene un nodo distinguido R llamado raíz de T; y que T esta ordenado, ósea, que los hijos de cada nodo N de T tienen un orden especifico. Estas dos propiedades no se requieren siempre para definir un árbol.

Ejemplo:

La figura muestra un árbol general T con 13 nodos,

1. El nodo C tiene tres hijos.
2. Cada uno de los nodos B y K tienen dos hijos.
3. Cada uno de los nodos D y H tiene un hijo.
4. Los nodos E,F,G,L,J,M y N no tienen hijos.

1. un árbol binario T’ puede estar vació, pero un árbol general T no es vació.
2. Suponga que un nodo N tiene un solo hijo. Entonces el hijo se distingue por ser el izquierdo o el derecho en un árbol binario T’, mientras que no existe esa distinción en un árbol general T.

Figura (2)

1. INFO [ K ] contiene los datos del nodo N.
2. HIJO [ K ] contiene la posición del primer hijo de N. La condición HIJO [ K ]= NULO indica que N no tiene hijos.
3. HERM [ K ] contiene la posición del siguiente hermano de N. La condición HERM [ K ] = NULO indica que N es el ultimo hijo de su padre.

Ejemplo:

Considere el árbol general T de la figura (2) , suponga que los datos de los nodos de T se guardan en un Array INFO como en la figura (3) las relaciones estructurales de T se obtienen asignando valores al puntero RAIZ y a los Arrays HIJO y HERM tal y como sigue:

1. como la raíz A de T se guarda en INFO [ 2 ], se y hace RAIZ:= 2.
2. Como el primer hijo de A es el nodo B, guardado en INFO [3 ], se hace HIJO [ 2 ]:= 3. como A no tiene hermanos, se hace HERM [ 2 ]= NULO.
3. Como el primer hijo de B es el nodo E, guardado en INFO [ 15 ], se hace HIJO [3]:= 15. como el nodo C es el siguiente hermano de B y C se guarda en INFO [ 4 ], se hace HERM [3]:=4.

Y así sucesivamente. La figura (3) da los valores finales de HIJO y HERM. Observe que la lista DISP de nodos vacos se mantiene en el primer array, hijo, donde DISP = 1.

Figura (3)

1. T contiene un elemento distinguido R, llamado raíz de T.
2. Los restantes elementos de T forman una colección ordenada de cero o mas árboles disjuntos T1, T2,.., Tm..

Figura (4)

1. Array lineal ordenado. Aquí se puede buscar y encontrar un elemento con un tiempo de ejecución f(n) = (log2n), pero es costoso el insertar y borrar elementos.
2. Lista enlazada. Aquí se puede insertar y borrar elementos fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se debe usar una búsqueda secuencial.

Aunque cada nodo de un árbol binario de búsqueda puede contener un registro entero de datos, la definición del árbol binario depende de un campo dado cuyos valores son distintos y deben estar ordenados.

Supongamos que T es un árbol binario. Entonces T se dice que es un árbol binario de búsqueda ( o árbol binario ordenado) si cada nodo N de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor del subárbol izquierdo de N y es menor que cualquier valor del subárbol derecho de N. ( no es difícil ver que esta propiedad garantiza el recorrido inorden de T dará una lista ordenada de los elementos de T) .

Es bueno hacer énfasis en esto ya que se puede saber mucho sobre lo que tiene que ver con los árboles; entre las cosas que podemos mencionar se encuentra la raíz, los nodos de un árbol y la diferencia entre nodos sucesores y nodos terminales, como se muestran en el contenido del trabajo.

Bachilleres:

Autor:

Estudiante universitario de Informática.

Fecha de realización: 24 de Abril 2006.