ARBOLES BINARIOS
Los árboles binarios son estructuras de datos muy similares
a las listas doblemente enlazadas, en el sentido que tienen dos punteros que
apuntan a otros elementos, pero no tienen una estructura lógica de tipo lineal
o secuencial como aquellas, sino ramificada. Tienen aspecto de árbol, de
ahí su nombre.
Un árbol binario es una estructura de datos no lineal en la
que cada nodo puede apuntar a uno o máximo a dos nodos. También se suele dar
una definición recursiva que indica que es una estructura compuesta por un dato
y dos árboles. Esto son definiciones simples. Este tipo de árbol se caracteriza
porque tienen un vértice principal y de él se desprende dos ramas. La rama
izquierda y la rama derecha a las que también se les conoce como subárboles.
Estructura de un árbol binario.
La rama izquierda y la derecha también son dos árboles
binarios. El Vértice principal se denomina raíz y cada una de las ramas se
puede denominar subárbol izquierdo y
subárbol derecho.
Datos importantes de los Árboles
Nodos: Se le llama Nodo a cada elemento que contiene un
Árbol.
Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un
nodo del Árbol puede ser la Raíz.
Nodo Padre: Se utiliza este termino para llamar a todos
aquellos nodos que tiene al menos un hijo.
Nodo Hijo: Los hijos son todos aquellos nodos que tiene un
padre.
Nodo Hermano: Los nodos hermanos son aquellos nodos que
comparte a un mismo padre en común dentro de la estructura.
Nodo Hoja: Son todos aquellos nodos que no tienen hijos,
los cuales siempre se encuentran en los extremos de la estructura.
Nodo Rama: Estos son todos aquellos nodos que no son la
raíz y que ademas tiene al menos un hijo.
Los arboles ademas de los nodos tiene otras propiedades
importantes que son utilizadas en diferente ámbitos los cuales son:
Nivel: Nos referimos como nivel a cada generación dentro
del árbol. Por ejemplo, cuando a un nodo hoja le agregamos un hijo, el nodo
hoja pasa a ser un nodo rama pero ademas el árbol crece una generación por lo
que el Árbol tiene un nivel mas.
- Un árbol vacío tiene 0 niveles
- El nivel de la Raíz es 1
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 se puede hablar de altura de ramas.
Peso: Conocemos como peso a el número de nodos que tiene un Árbol. Este factor es importante por que nos da una idea del tamaño del árbol y el tamaño en memoria que nos puede ocupar en tiempo de ejecución
Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, se dice que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres y así sucesivamente.
Recorrido de arboles
Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden especifico, los recorridos nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo.
Recorrido en Pre-orden:
Recorrer un árbol en pre-orden consiste en primer lugar, examinar el dato del nodo raíz, posteriormente se recorrer el subárbol izquierdo en pre-orden y finalmente se recorre el subárbol derecho en pre-orden.
Recorrido en Inorden
Recorrer un árbol en Inorden consiste en primer lugar
en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo
raíz, y finalmente se recorre el subárbol derecho en Inorden.
Recorrido en Postorden:
Recorrer un árbol en Postorden consiste
en primer lugar en recorrer el subárbol izquierdo en Postorden, luego serecorre
el subárbol derecho en Postorden y finalmente se visita el nodo raíz.
Fuentes:
0 comentarios:
Publicar un comentario