Arboles Binarios

ESTRUCTURA DE DATOS ÁRBOLES

Generalidades: Un árbol es una estructura de datos no lineal constituida por un conjunto de elementos del mismo tipo llamados nodos, que normalmente representan instancias de clases. La estructura de datos árbol se dice no lineal porque sus elementos (nodos) no se organizan de la misma manera que por ejemplo en un arreglo, en una matriz o en una lista enlazada, endonde vemos que existe un orden de precedencia entre los elementos y sobre todo el recorrido de estos se hace en un mismo sentido o dirección, es decir de izquierda a derecha o de derecha a izquierda. De este modo un árbol es una estructura de datos no lineal puesto que no existe un único camino para acceder a un elemento (nodo) desde otro, además de que sus elementos no se organizan de formaposicional (como en un arreglo), ni tampoco en el sentido de antecesor y sucesor, toda vez que la estructura de un árbol organiza sus nodos según una relación de jerarquía, en el sentido de nodos padres y nodos hijos, sin haber relación de herencia; es decir, que la relación entre los nodos de un árbol es más una relación de contenencia o pertenencia que de herencia, por cuanto algunos nodos del árbol(llamados padres) pueden estar compuestos por otros nodos (llamados hijos). Recuerde que las estructuras de datos lineales se caracterizan por que a cada elemento le corresponde como máximo un único elemento siguiente, mientras que en las estructuras de datos no lineales como es el caso de un árbol, un elemento (nodo) puede tener varios sucesores (elementos siguientes), lo cual representa unaestructura multi enlazada.

Terminología: En un árbol el nodo principal es llamado nodo raíz, a partir de él se crean los demás elementos del árbol como hijos del nodo principal, o hijos de los hijos de este. Los nodos que no tienen hijos se les llaman nodos hojas y a los nodos que no son ni raíz ni hojas se les llama ramas o nodos internos. Al conjunto de nodos comprendido entre dos nodos dados,que se usa para llegar desde uno hasta otro se le llama camino. La longitud de un camino representa la cantidad de nodos que lo conforman. Además de estos conceptos, en la terminología de árboles encontramos otros conceptos, como por ejemplo el grado de un nodo, que se define como el número de nodos hijos (descendientes directos) que un nodo tiene. El grado de un árbol, es entonces determinado porel número de nodos hijos que tiene el nodo de mayor cantidad de hijos. En virtud de este concepto un árbol tenemos a los arboles binarios, cuyo grado es dos, lo que significa que cualquier nodo del árbol como máximo puede tener dos hijos y son los tipos de arboles más populares y de mayor aplicabilidad. Los arboles tiene muchas aplicaciones y se suelen usar para representar información que seorganiza en forma jerárquica, es decir, según un orden de prioridad o de importancia, por ejemplo el índice de un libro que está compuesto por unidades, las cuales contienen capítulos y estos se dividen en temas que comprenden subtemas. Otra situación en la que podemos usar un árbol es para representar el organigrama de una empresa, o también la estructura los archivos del disco duro de tucomputadora, en la cual el nodo raíz es el disco duro y los hijos del nodo raíz, son todas las carpetas de primer nivel del disco duro, las cuales a su vez pueden contener a otras carpetas o subdirectorios. Un árbol es un conjunto finito de uno o más nodos capaces de guardar algún tipo de información y tales que:
●

Existe un nodo especialmente designado y denominado RAIZ del árbol.

●

Los nodosrestantes se dividen en m >= 0 conjuntos disjuntos, cada uno de los cuales es a su vez, un árbol. Estos árboles se llaman subárboles del RAIZ. Observar la naturaleza recursiva de la definición de árbol. Cada elemento en un árbol se denomina nodo del árbol.

Conceptos:
●

Nodo: También llamado vértice o elemento del árbol. Es el contenedor de los datos y los enlaces a sus hijos y a su padre....