Estructura de datos: Árboles

                        

UCNE 

Libro: Estructura de datos en c++ Kendall y Kendall  |   Capítulo 16                            Fecha:02/04/2023

                                                        

                                 Árboles

                                                                   -Terminología

Un árbol se puede definir como una estructura jerárquica y en forma no lineal, aplicada sobre una colección de elementos u objetos llamados nodos. El árbol es una estructura de datos muy importante en informática y en ciencias de la computación. Los árboles son estructuras no lineales, al contrario que los arrays y las listas enlazadas que constituyen estructuras lineales.

                                                                  -Características

En relación con otros nodos:

Nodos. Se le llama nodo a cada elemento que contiene el árbol. 

 Nodo padre. Se utiliza este término para llamar a todos aquellos nodos que tienen al menos un hijo.

 Nodo hijo. Los hijos son todos aquellos nodos que tienen un padre. 

 Nodo hermano. Los nodos hermanos son aquellos nodos que comparten un mismo padre en común dentro de la estructura.

En relación a su posición:

Nodo Raíz. Se refiere al primer nodo de un árbol, Solo un nodo del árbol puede ser la raíz. 

 Nodo Hoja. Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura. 

 Nodo Interior o Rama. Estos son todos aquellos nodos que no son la raíz y que además tiene al menos un hijo.

En relación al tamaño del árbol:

Nivel. El nivel de un nodo es su distancia a la raíz. 

Por lo tanto: 

◦ Un árbol vacío tiene 0 niveles 

◦ El nivel de la raíz es 1 

◦ El nivel de cada nodo se calculado contando cuantos nodos existen sobre él, hasta llegar a la raíz + 1, y de forma inversa también se podría, contar cuantos nodos existen desde la raíz hasta el nodo buscado + 1. Altura. Se le llama altura al número máximo de niveles de un árbol.

                                         Árboles binarios

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario, cada nodo puede tener, cero, uno o dos hijos (subárboles). 

Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. árbol binario es una estructura recursiva. 

Cada nodo es el raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados los subárboles derecho e izquierdo del nodo, respectivamente. Un árbol binario se divide en tres subconjuntos disjuntos:

                                                                           Equilibrio

La distancia de un nodo al raíz determina la eficiencia con la que puede ser localizado. Por ejemplo, dado cualquier nodo de un árbol, a sus hijos se puede acceder siguiendo sólo un camino de bifurcación o de ramas, el que conduce al nodo deseado. 

De modo similar, los nodos a nivel 2 de un árbol sólo pueden ser accedidos siguiendo sólo dos ramas del árbol. La característica anterior nos conduce a una característica muy importante de un árbol binario, su balance o equilibrio. Para determinar si un árbol está equilibrado, se calcula su factor de equilibrio. El factor de equilibrio de un árbol binario es la diferencia en altura entre los subárboles derecho e izquierdo.

                                                               Árboles completos

Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2 sub árboles llamados de acuerdo a su caso como:

 1. Si el nodo raíz tiene 0 relaciones, se llama hoja. 

2. Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo. 

3. Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.

                                                          Estructura de un árbol binario

Un árbol binario se construye con nodos. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos de enlace (apuntador), uno al subárbol izquierdo (izquierdo, izdo) y otro al subárbol derecho (derecho, dcho). 

El valor NULL indica un árbol o un subárbol vacío. 

Ejemplo;

Se puede observar que los nodos de un árbol binario que son hojas se caracterizan por tener sus dos campos de enlace a NULL.

                                                          Representación de un nodo

La clase Nodo agrupa a todos los atributos de que consta: dato, izdo (rama izquierda) y dcho (rama derecha). Además, dispone de dos costructores, el primero inicializa el campo dato a un valor y los enlaces a NULL, en definitiva, se inicializa como hoja. El segundo, inicializa dato a un valor y las ramas a dos subárboles. Se incluyen, además, las funciones miembro de acceso y modificación de cada uno de sus atributos.

Creación de un árbol binario

Árbol de expresión

la expresión es una secuencia de tokens (componentes léxicos siguiendo las reglas establecidas). 

Un árbol de expresión es un árbol binario con las siguientes propiedades:

Los subárboles son subexpresiones cuyo nodo raíz es un operador. 
 Los árboles binarios se utilizan para representar expresiones en la memoria; En realidad, no aparecen en el árbol, pero están implícitos en su forma, y ​​esto es muy interesante para evaluación de la expresión.

Reglas para la construcción de árboles de expresiones

Los árboles de expresiones se utilizan en las computadoras para evaluar expresiones usadas en El algoritmo más sencillo para construir un árbol de expresión es aquél que lee una expresión completa que contiene paréntesis en la misma. (a * c) + (e / g) - (b + d) Los operadores que siguen en orden de prioridad son + y -, que se evalúan de izquierda a derecha. Por consiguiente, se puede escribir:((a * c) + (e / g)) - (b + d)Por último, la expresión completa entre paréntesis será:(((a * c) + (e / g)) - (b + d))

Recorrido de un arbol BINARIO

Recorrido en preorden  :En este tipo de recorrido: 1-Primero se visita el nodo raíz. 2-Luego se recorre el subárbol izquierdo. 3-finalmente, se recorre el subárbol derecho.

 Recorrido en orden :En este tipo de recorrido: 1-Primero se recorre el subárbol izquierdo. 2-Luego se visita el nodo raiz. 3-Finalmente, se recorre el subárbol derecho.

 Recorrido en postorden: En este tipo de recorrido: 1-Primero se recorre el subárbol izquierdo. 2-Luego se recorre el subárbol derecho 3-Finalmente, se visita el nodo raíz.

Operaciones en Arboles binarios de búsqueda

Estas operaciones son: 

 Búsqueda de un nodo. Devuelve la referencia al nodo del árbol, o NULL.

Inserción de un nodo. Crea un nodo con su dato asociado y lo añade, en orden, al árbol. 

 Borrado de un nodo. Busca el nodo del árbol que contiene un dato y lo quita del árbol. El árbol debe seguir siendo de búsqueda. Recorrido de un árbol. Los mismos recorridos de un árbol binario preorden, inorden y postorden.

DISEÑO RECURSIVO DE UN ÁRBOL DE BÚSQUEDA

En un árbol binario de búsqueda cada nodo tiene dos enlaces que apuntan a sus subárboles izquierdo y derecho, respectivamente. por lo que para declarar la clase ArbolBusqueda es necesario tener previamente definida la clase Nodo, ya que la raíz del árbol es un puntero a un objeto de tipo Nodo. Por lo tanto, se debe definir primero la clase Nodo antes de la clase ArbolBusqueda.