Estructura de datos(Arboles AB y ABB)

¿Que son?

Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir.
El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva.

un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja.

Propiedades

En la ciencia de la computación definimos un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados , y a la secuencia de líneas se le denomina ruta (path).

 Además, los árboles tienen las siguientes propiedades:

 Tienen un nodo al que se le llama raíz del árbol.

 Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna).

 Existe una ruta única del nodo raíz a todos los demás nodos del árbol.

 Si hay una ruta , entonces a „b‟ se le denomina „hijo‟ de „a‟ y es el nodo raíz de un subárbol.

CARACTERÍSTICAS Y PROPIEDADES DE LOS ÁRBOLES.

1. NODO indica un elemento, o ítem, de información.

2. Todo árbol que no es vacío, tiene un único nodo raíz.

3. Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.

4. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.

5. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

6. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

7. Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

8. Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol.

9. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene nivel 1.

10. Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

ÁRBOLES BINARIOS

Un árbol ordenado es aquel en el cual la distribución de las ramas sigue cierto orden. Los árboles ordenados de grado 2 son de especial interés puesto que representan una de las estructuras de datos más importante en computación, conocida como árboles binarios.

ÁRBOLES BINARIOS COMPLETOS

Se define un árbol binario completo como un árbol en el que todos sus nodos, excepto los de último nivel, tienen dos hijos; el subárbol izquierdo y el subárbol derecho

En un árbol binario cada nodo puede tener como máximo dos subárboles; y siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho.

ÁRBOLES BINARIOS DE BÚSQUEDA.

 El árbol binario de búsqueda es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación.

 Formalmente se define un árbol binario de búsqueda de la siguiente manera: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T deben ser menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos el subárbol derecho de T deben ser mayores o iguales al valor del nodo T”.

Cada elemento(nodo) de un árbol ABB cuenta con tres campos:

- Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero).
- Puntero al nodo derecho
- Puntero al nodo izquierdo

Los punteros tienen que ser del tipo árbol, ya que apuntaran a un nodo del mismo tipo, este seria un ejemplo de como se seria el tipo arbol ABB.

Primero creamos el nodo:
struct nodo{
int dato;
struct nodo *der;
struct nodo *izq;
};
"Los punteros son variables que guardaran en la memoria la dirección de otra variable" en este caso la de una estructura llamado nodo.

Ejemplo de ABB: