Componentes de un Arbol

Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo. En relación con otros nodos: 
Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, también se dice que X es antecesor de Y. 
Nodo Hijo: Cualquiera de lo nodo apuntado por uno de lo nodo del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. 
Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En cuanto a la posición dentro del árbol: 
Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. 
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). 
Nodo Interior: Es un nodo que no es raíz ni hoja. 
Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres. 
Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con más de tres hijos 
Nivel: Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y así sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3. 
Rama: Es el camino desde el nodo raíz a una hoja. 
Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. 
Peso: Es el número de nodos del árbol sin contar la raíz. 

 Propiedades del árbol

Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo plano. Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G. Dado n vértices etiquetados, hay n n-2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1,d2,...,dn es: un coeficiente multinomial.
Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números a y ß (a ˜ 3 y ß ˜ 0.5) tales que: 

 Clasificación de arboles

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Tipos de árboles Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura). A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n. Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.


Dado un grafo conexo, un árbol recubierto mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc... , y se usa para asignar un peso total al árbol recubierto mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo. En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores. Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.   Recorrido de un árbol

Árbol binario
• Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho
• Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho
• Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz
En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.
• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho