Recursividad

De forma recursiva, un árbol como un tipo de datos se define como un valor (de un cierto tipo de datos, posiblemente vacía), junto con una lista de los árboles (posiblemente una lista vacía), los subárboles de sus hijos:

t: v [t[1], ..., t[k]]

(Un árbol t se compone de un valor v y una lista de otros árboles.)

Más elegantemente, a través de la recursión mutua, de los cuales un árbol es uno de los ejemplos más básicos, un árbol se puede definir en términos de un bosque (una lista de árboles), donde un árbol consta de un valor y un bosque (los subárboles de sus hijos):

f: [t[1], ..., t[k]]

t: v f

Tenga en cuenta que esta definición es en términos de valores, y es apropiada en lenguaje funcional (se asume la transparencia referencial); diferentes árboles no tienen conexión, ya que son simplemente listas de valores.

Como una estructura de datos, un árbol se define como un nodo (la raíz), que a su vez consta de un valor (de algún tipo de datos, posiblemente vacío), junto con una lista de referencias a otros nodos (lista posiblemente vacía y referencias posiblemente nulas):

n: v [&n[1], ..., &n[k]]

(Un nodo n se compone de un valor v y una lista de referencias a otros nodos.)

Esta estructura de datos define un grafo dirigido,1​ y para que sea un árbol hay que añadir una condición en su estructura global (en su topología), y esto es que a lo sumo una referencia puede apuntar a cualquier nodo dado (un nodo tiene como máximo un solo padre), y ningún nodo del árbol puede apuntar a la raíz. De hecho, todos los nodos (que no sean la raíz) deben tener exactamente un padre, y la raíz no debe tener ningún padre.

De hecho, dada una lista de nodos, y para cada nodo de una lista de referencias a sus hijos, no se puede saber si esta estructura es un árbol o no sin analizar su estructura global, como se define a continuación.

- Tipos de Arboles (Binarios y HEAP).

-  Teoremas I y II para árboles Binarios.

-  Algoritmos INSERTAR y HEAPIFY