Estructura De Datos

un árbol es una estructura de datos ampliamente usada que imita 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 más nodos hijos conectados a él. Se dice que un nodo es padre de un nodo si existe un enlace desde hasta (en ese caso, también decimos que es hijo de ). Sólo puede haber un único nodo sinpadres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Definición
Formalmente, podemos definir un árbol de la siguiente forma:
 Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
 Un nuevo árbol a partir de un nodo y árboles de raíces con elementos cada uno, puedeconstruirse estableciendo una relación padre-hijo entre y cada una de las raíces de los árboles. El árbol resultante de nodos tiene como raíz el nodo , los nodos son los hijos de y el conjunto de nodos hoja está formado por la unión de los conjuntos hojas iniciales. A cada uno de los árboles se les denota ahora subárboles de la raíz.
Una sucesión de nodos del árbol, de forma queentre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y asísucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel (a distancia aristas de la raíz), se deben haber listado todos los de nivel . Otros recorridos típicos del árbol son preorden, postorden e inorden:
 El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
 El recorridoen inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar , luego la raíz y luego cada uno de los hijos en orden simétrico.
 El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.
Finalmente, puededecirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico.
[editar]Tipos de árboles


Ejemplo de árbol (binario).
Árboles Binarios: 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únhijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. Tipos de árboles binarios
 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.

 Árbol de búsqueda binario auto-balanceable: un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz,...