Arbol De Programacion

Árboles

Un árbol es una estructura de datos dinámica ( las estructuras del árbol pueden cambiar durante la ejecución del programa ) no lineal ( puesto que a cada elemento del árbol puede seguirle varios elementos ) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. 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.

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, puede construirse 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 que entre 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 recorrido en 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, puede decirse 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.

Tipos de árboles

• Árboles Binarios

o Árbol de búsqueda binario auto-balanceable

 Árboles AVL

 Árboles Rojo-Negro

 Árbol AA

• Árboles Multicamino

o Árboles B (Arboles de búsqueda multicamino autobalanceados)

 Árbol-B+

 Árbol-B*

Operaciones de árboles.

Las operaciones comunes en árboles son:

• Enumerar todos los elementos.

• Buscar un elemento.

• Dado un nodo, listar los hijos (si los hay).

• Borrar un elemento.

• Eliminar un subárbol (algunas veces llamada podar).

• Añadir un subárbol (algunas veces llamada injertar).

...