Las Listas, las Pilas y las Colas son estructuras de datos lineales, pero existen otras estructuras no lineales y a la vez más ricas. Los árboles son un ejemplo de estas estructuras que permiten representar datos que tienen enlaces jerárquicos entre ellos.

      Un árbol es una colección de elementos llamados nodos, uno de los cuales se distingue entre los demás, llamado raíz, junto con una relación de paternidad que impone una estructura jerárquica sobre los nodos.

      Existen numerosos ejemplos de la realidad como pueden ser los árboles genealógicos, o la estructura de directorios y Archivos que nos podemos encontrar en nuestro disco duro.

      Formalmente, un árbol puede definirse de manera recursiva como sigue:
            1. Un solo nodo es, por sí mismo un árbol. Ese nodo es también la raíz de dicho árbol.
            2. Supongamos que n es un nodo y que A1,A2,...,Ak son árboles con raíces n1,n2,...,nk, respectivamente. Entonces podemos construir un nuevo árbol haciendo que n se constituya en el padre de los nodos n1,n2,...,nk. En el árbol resultante, n es la raíz y A1,A2,...,Ak son los subárboles de la raíz. Los nodos n1,...,nk se llaman hijos delnodo n.

      En algunas ocasiones conviene incluir en este tipo de estructura el árbol nulo. En un árbol existe una relación de paternidad entre los nodos que lo componen. Supongamos que tenemos dos nodos n1 y n2 entonces podremos decir que n1 es padre de n2, si n2 aparece en alguno de los subárboles del árbol que tiene a n1 como raíz.

      Cada nodo del árbol que esté situado directamente bajo otro nodo es su descendiente y si está situado encima es un ascendiente.Al elemento terminal, sin descendientes, se denomina hoja (también podemos decir que es un nodo en el que sus hijos son árboles vacíos).

      Los diferentes nodos están organizados por niveles. La raíz del árbol es el nivel 1; luego cada descendiente siguiente pertenece a un nivel superior. El mayor nivel que puede encontrarse en un árbol determina su profundidad. La profundidad de un árbol puede calcularse como la longitud del camino más largo desde una hoja a la raíz.

      Hay otras propiedades importantes que se pueden analizar en una estructura de este tipo como pueden ser la altura de un nodo dentro un árbol, que es la longitud del camino más largo de ese nodo a una hoja, también otra propiedad útil en ciertas ocasiones es la altura de un árbol que es la altura del nodo raíz.

      Los árboles pueden clasificarse según la máxima cantidad de hijos que puede tener cada uno de los nodos de un árbol, lo que se llama aridad de un árbol. Según su aridad un árbol puede denominarse Binario (aridad 2), Triario (aridad 3), etc. Aquellos árboles donde no es posible calcular la cantidad máxima de hijos que puede tener un nodo cualquiera se los denomina Arboles Generales.

      En ciertas ocasiones los nodos están ordenados, pudiéndose construir dos árboles distintos a partir de los mismos datos, dependiendo del orden interno que adquiera el árbol. Si lo que se hace es ignorar explícitamente el orden de los hijos, entonces estamos ante el caso de un árbol no ordenado.

      Para recorrer todos los nodos de un árbol cualquiera, existen también diferentes formas útiles de hacerlo sistemáticamente. Las 3 tres formas más importantes de realizar el recorrido se llaman de orden previo (pre-order), de orden posterior (post-order) y de orden simétrico (in-order). Los métodos que existen para realizar esta tarea se ejecutan de forma recursiva sobre la estructura del árbol. Todos los métodos varían en el orden en que visitan cada uno de los nodos y sus correspondientes hijos. El primero de estos métodos consiste en visitar el nodo raíz, sus hijos izquierdos y sus hijos derechos, en este orden. El recorrido post order consiste en visitar primero los hijos izquierdos, luego los derechos y por último la raíz del árbol. El último de estos métodos, el que efectúa el recorrido en orden simétrico, visita primero los hijos izquierdos, luego la raíz del árbol y por último los hijos derechos del nodo en cuestión. Cuando decimos que visitamos un nodo significa aplicarle el método con el mismo orden al que se viene aplicando, a cada uno de los hijos como si este, fuese un árbol por sí solo.

      Hasta aquí se han explicado las propiedades y características más significativas de los árboles pero todavía no se ha dicho como puede cualquier programador hacer uso de un árbol en cualquiera de sus programas. Como toda estructura de datos, los árboles para no ser menos, se pueden implementar de varias formas diferentes. Cada una de las realizaciones tendrá sus pro y sus contra, y será el programador quien deba elegir la más apropiada, según sean los requerimientos dados a su problema. Aquí describiremos las realizaciones de árboles mediante Listas de hijos, otra representación implementada mediante arreglos,  y por último la representación de "hijo más izquierdo - hermano derecho. Cabe destacar también que existen otras implementaciones que no se deben olvidar como pueden ser las que se hacen mediante un puntero al padre.

Implementación de un árbol con Listas de hijos:

      Una manera importante y útil de representar árboles consiste en formar una lista de los hijos para cada uno de los nodos. La forma de implementar una lista queda a cargo del desarrollador, si desean saber como hacerlo se puede encontrar una explicación en la sección Listas de esta página.
Para representar el árbol con este modelo lo podremos hacer de dos maneras diferentes, con la primera de ellas necesitaremos un arreglo de celdas de encabezamiento indexadas por nodos ,o bien, existe otra variante que utiliza punteros para enlazar los nodos que contienen el dato junto con la lista de sus hijos.

      Pasemos a explicar la primera de ellas. Para comenzar a desarrollar un árbol con este modelo primero debemos definir las estructuras de datos auxiliares necesarias.
Como primer paso vamos definir la estructura nodo. Un nodo tendrá un dato guardado y una clave, que más adelante veremos para que se necesita.
Ahora debemos definir el arreglo de celdas de encabezamiento, que será un vector de N elementos que en cada posición contendrá una lista, al que llamaremos hijos.
La interface de lo que sería un TAD árbol implementado así quedaría

                  Const maxNodos = ...; //variable que representa el nro maximo de
                                                  //nodos que podrá tener el árbol
                  Type elem_Type: ...;    //tipo de dato que almacenará el árbol

                         Nodo = TObject
                              dato  : elem_Type;
                              clave : 1..maxNodos;
                              ...
                              metodos de instancia del objeto Nodo
                              ...
                        end;

                        TArbol = Class
                           private
                              hijos : array[1..maxNodos] of LISTA(INTEGER);
                              nodos : array[1..maxNodos] of Nodo;
                              raiz : 0 .. maxNodos;
                           public
                           ...
                              metodos para el manejo del arbol
                           ...
                        end;

      Con esta representación supondremos que si raíz está en Cero entonces el árbol será vacío, y si es distinta de cero entonces este valor será la posición dentro del vector nodos donde se encuentra la raiz del árbol y la posición donde se encuentra la lista de hijos dentro del vector con el mismo nombre.
El campo clave definido dentro de nodo está para poder en cualquier momento que tengamos un nodo saber cual el la posición dentro de los arreglos que le corresponde.

      La otra variante, que utiliza punteros para enlazar cada uno de los nodos, es más fácil de ver como se va conformando el árbol a partir del nodo raíz y de la lista de hijos de este.
Para comenzar definiremos un nodo, en este caso en esta variante cada uno de los nodos contendrá el dato que representa dentro del árbol y también la lista de hijos que le corresponde. Por lo tanto la definición de un árbol quedará como sigue:

                        Type elem_Type= ... ;

                                Nodo = TObject;
                                 dato : elem_Type;
                                 hijos : Lista (Nodo); // declaración de lista es una simplificación
                                                            // de una lista de Nodos.
                                  ...
                                  métodos de instancia del objeto Nodo
                                  ...
                                  end;

                                 TArbol = Class
                                   private
                                      raiz : Nodo;
                                   public
                                      ...
                                    métodos para el manejo del árbol
                                      ...
                                 end;

      Aquí solamente hemos mostrado las interfaces del TAD árbol para cada una de las variantes porque la implementación no la creemos importante en esta sección, ya que estamos explicando la estructura interna de un árbol.

Implementación de un árbol basada en arreglos:

      En este tipo de realización no se utilizan punteros, sino que todos los elementos del árbol se encuentran almacenados dentro de un arreglo de elementos. Todos los elementos dentro de este arreglo tendrán nombres similares a los valores que puedan tener los indices del arreglo o bien se debe agregar una clave a cada nodo para poder de esta forma ubicar a su padre dentro de la estructura del árbol.
De esta forma si tenemos la función clave (k) que nos devuelve la clave de un nodo ubicado en la posición k, entonces podremos decir que si clave (k) = j, entonces en la posición j del arreglo se encuentra el padre del nodo de la posición k.
      Aquí aparecen otros problemas como pueden ser como identificar a la raíz de un árbol, para ello tendremos que tener un valor para indicar un valor nulo o bien decir que el padre de un nodo raíz es él mismo.

      Esta representación se basa en la propiedad de que en los árboles cada nodo tiene un padre único, y permite hallar el padre de un nodo en un tiempo constante.

      Este tipo de realización tiene la ventaja que es muy fácil y eficiente el recorrido del árbol y como encontrar los ancestros de un nodo dado, ya que para hallar el camino ascendente de un nodo hasta su padre en un tiempo proporcional al número de nodos del camino. Pero tiene grandes inconvenientes como son que es limitado el número máximo de elementos que puede contener el árbol, las operaciones de borrado pueden complicarse porque pueden llevar a un reacomodamiento de gran parte de los nodos del árbol. Otra operación que es ineficiente es la búsqueda de los hijos de un nodo dado o el cálculo de la altura de dicho nodo.

      Si hacemos un TAD de un árbol basada en la implementación con arreglos nos quedaría:

                        Const nroMax = ...;

                        Type elem_Type = ...;

                                Arbol = Class
                                   private
                                     elementos : array [1..nroMax] of elem_Type;
                                   public
                                    ...
                                    métodos para el manejo del árbol
                                    ...
                               end;

      Para esta implementación hemos supuesto que para identificar a la raíz del árbol indicamos como a ella misma como su padre.
Por la misma razón que en la anterior implementación sólo mostramos la interface del TAD y la implementación de los metodos los dejamos para el programador ;-).

Representacion "hijo más a la izquierda - hermano derecho":

      Este modelo de realización de árboles no se tiene la necesidad de utilizar ni Listas ni arreglos para almacenar la información que luego vamos a recuperar para poder armar la estructura de un árbol.
En este modelo la estructura de cada nodo es más simple que en las anteriores realizaciones pues aquí un nodo solamente contendrá información a cerca del dato que debe guardar, un enlace con su hijo más a la izquierda y otro con su hermano a la derecha.

      En este punto nos puede parecer dificultoso de entender que con solo esta información se pueda armar la estructura de un árbol pero veamos como se hace; por ejemplo, supongamos que queremos obtener la lista de todos los hijos de un nodo dado, entonces debemos tomar el hijo más a la izquierda de este nodo ( el cual lo obtenemos con el enlace de dicho nodo), luego con este nodo hijo encontrado, comenzaremos con una búsqueda repetida sobre el hermano a la derecha, y luego con el hermano a la derecha de este otro, y así hasta llegar a un nodo que no tenga hermano a la derecha. De esta forma hemos recorrido todos hermanos a partir de un nodo, y como habíamos comenzado con el hijo más a la izquierda de un nodo hemos, en consecuencia, encontrado la lista de todos los hijos del nodo dado.

      En este modelo de realización todas las operaciones son fáciles de implementar, escepto aquella que encuentra al padre de un nodo, pues esto requiere que se busque, en el peor de los casos, en toda la estructura del árbol. Una mejora que se puede introducir para solucionar este problema es agregar a la estructura nodo un enlace hacia el nodo padre.

      Si definimos la estructura de un TAD Arbol con este modelo, nos quedará algo así:

                        Type type_elem = . . . ;

                                Nodo = TObject
                                    dato : type_elem;
                                    hijo_izq : Nodo;
                                    hno_dcho: Nodo;
                                   ...
                                    metodos del objeto nodo;
                                   ...
                               end;

                              Arbol = Class
                               private
                                    raiz : Nodo;
                               public
                               ...
                                 métodos de la clase árbol
                               ...
                              end;

Tipos de árboles más conocidos:

Arboles Binarios: es un árbol en el cual cada nodo tiene cero, uno o dos hijos.

Arboles Binarios de Búsqueda: son árboles binarios en el que los nodos guardan un cierto orden entre ellos. Por ejemplo, si tenemos un árbol de números enteros, tomamos el valor de un nodo y sabemos que todos los nodo con valores menores a él los vamos a encontrar en un subárbol y los mayores a él en el otro subárbol.

Arboles Generales: son árboles en los que un nodo puede tener un nro cualquiera de hijos.

Arboles AVL: el nombre de este tipo de árboles es debido a sus inventores. Una traducción posible, puede ser Arbol Balanceado en Altura. Son árboles binarios de búsqueda en el que no se admite que las alturas de dos hermanos difieran en más de uno.

Arboles 2-3: son árboles que tienen las siguientes propiedades:
- Cada nodo interior tiene dos o tres hijos
- Todos los caminos que van de la raíz a una hoja tienen idéntica longitud.
Puede decirse que un árbol 2-3 es un árbol B de orden 3.

Arboles B: es una clase especial de arbol n-ario balanceado. Es una generalización de los árboles 2-3. Formalmente un árbol B de orden n tiene las siguientes propiedades:
- La raíz es una hoja o tiene al menos dos hijos.
- Cada nodo, excepto la raíz y las hojas, tiene entre (n /2) y n hijos.
- Cada camino desde la raíz hasta una hoja tiene la misma longitud.
Los datos reales se encuentran en las hojas, y en los nodos internos sólo se encuentran claves de búsqueda.

Arboles B*: es un árbol B en el que cada nodo interno está lleno en dos terceras partes por lo menos (en vez de la mitad).