Estructura de datos

Trabajo
de
Investigación
“Arboles Binarios ”
Estructura de DatosSección : 310
Fecha:

Introducción
En este trabajo tratar de la estructura de datos llamada árboles , en este trabajo daremos a conocer una explicación de la teoría de árboles , que consta con los conceptos básicos de los árboles , definiremos o hablaremos de los tipos de nodos , estructura básica de losárboles , diferentes métodos de recorrido de un árbol , como recorrer un árbol , como eliminar los nodos de un árbol , árboles ordenados, cálculo de la profundidad de un árbol.
También mostraremos algunas aplicaciones prácticas de los árboles en problemas reales que se originen tanto en empresas como en juegos.















Árboles de datos
Un árbol de datos es unaestructura no lineal que cada nodo puede apuntar a uno o varios nodos
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Esto son definiciones simples. Pero las características que implican no lo son tanto.







Definiremos Varios conceptos
Nodo Hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.En el ejemplo “L” y “M” son hijos de “G”.
Nodo Padre: Nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo “A” es el padre de “B”,”C” y “D”.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo solo puede ser apuntado por otro nodo, es decir, cada nodo tendrá un padre. Esto hace que estos árboles están fuertemente jerarquizados, y es lo que enrealidad les da la apariencia de árboles

En cuanto a la posición del Árbol:
Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el “A”.
Nodo Hoja: nodo que no tiene hijos. En el ejemplo hay varios. “F”, “H”, “I”, “K”, “L”, “M”, “N”,”O”.
Nodo rama: aunque esta definición apenas la usaremos estos son los nodos que no pertenecen aninguna de las 2 categorías anteriores. En el ejemplo “B”, “C”, “D”, “E”, “G” y “J”.

Otra Característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ningunos de los punteros de cada nodo.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemosconsiderarlo como una estructura independiente. Es decir un nodo cualquiera puede ser considerado como la raíz de un árbol completo.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
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 otro dos es de orden dos, sipuede apuntar a tres será de orden tres etc.
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 existe 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 y el de sus hijos 1.Así sucesivamente. En el ejemplo, el nodo “D” tiene nivel 1, el nodo “G” tiene nivel 2 y el nodo “N”, nivel 3.
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 árbol de ejemplo tiene altura 3, la rama “B” tiene altura 2, la rama “G” tiene...