Arboles

Definicion: 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 a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, 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.

Tipos de arboles.

Un árbol ordenado se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado, podemos hablar del primero, segundo o último hijo de un nodo en particular. El primer hijo de un nodo en un árbol ordenado se denomina con frecuencia el hijo más viejo de este nodo y el último se denomina el hijo más joven. Un bosque es un conjunto ordenado de árboles ordenados.

 El árbol de la izquierda es ordenado y el árbol de la derecha es un árbol no ordenado.

 

Arboles de expresion: Representan un orden de ejecucion.

 

 

 

Arboles Similares:Los que tienen la misma estructura (forma).

 

 

 Arboles equivalentes: Son los árboles similares y sus nodos contienen la misma información.

 

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

 

 

 

nLos hermanos se enlazan en forma horizontal (lineal)

nSe enlaza en forma vertical el padre con el hijo que se encuentra mas a la izquierda y se elimina el enlace de este padre con los demás hijos.

nSe rota el diagrama resultante 45 grados hacia la izquierda.

 

Conversion de un arbol general a un arbol binario.