¿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:
Fuentes: https://www.uaeh.edu.mx/docencia/P_Presentaciones/icbi/asignatura/Cap6ARBOLES.pdf
http://c.conclase.net/edd/?cap=006
https://www.programacion.com.py/escritorio/c/arboles-en-c
http://blog.martincruz.me/2012/11/arboles-binarios-de-busqueda-c.html
