trees c basic terminology
Este tutorial detallado sobre árboles C ++ explica los tipos de árboles, las técnicas de recorrido de árboles y la terminología básica con imágenes y programas de ejemplo:
En esta serie C ++, hasta ahora hemos visto la estructura de datos lineal de naturaleza tanto estática como dinámica. Ahora procederemos con la estructura de datos no lineal. La primera estructura de datos de esta categoría es 'Árboles'.
pasando matrices a métodos en java
Los árboles son estructuras de datos jerárquicas no lineales. Un árbol es una colección de nodos conectados entre sí por medio de 'bordes' que están dirigidos o no. Uno de los nodos se designa como 'nodo raíz' y los nodos restantes se denominan nodos secundarios o nodos hoja del nodo raíz.
En general, cada nodo puede tener tantos hijos pero solo un nodo padre.
=> Consulte toda la serie de formación en C ++
Los nodos de un árbol están en el mismo nivel llamados nodos hermanos o pueden tener una relación padre-hijo. Los nodos con el mismo padre son nodos hermanos.
Lo que vas a aprender:
- Árboles en C ++
- Tipos de árboles C ++
- Técnicas de recorrido de árboles
- Conclusión
- Lectura recomendada
Árboles en C ++
A continuación se muestra un árbol de ejemplo con sus diversas partes.
Repasemos las definiciones de algunos términos básicos que usamos para los árboles.
- Nodo raíz: Este es el nodo más alto de la jerarquía del árbol. En el diagrama anterior, el nodo A es el nodo raíz. Tenga en cuenta que el nodo raíz no tiene ningún padre.
- Nodo hoja: Es el nodo más inferior en una jerarquía de árbol. Los nodos hoja son los nodos que no tienen ningún nodo hijo. También se conocen como nodos externos. Los nodos E, F, G, H y C en el árbol anterior son todos nodos de hojas.
- Subárbol: El subárbol representa varios descendientes de un nodo cuando la raíz no es nula. Un árbol generalmente consta de un nodo raíz y uno o más subárboles. En el diagrama anterior, (B-E, B-F) y (D-G, D-H) son subárboles.
- Nodo padre: Cualquier nodo excepto el nodo raíz que tiene un nodo hijo y un borde hacia arriba hacia el padre.
- Nodo ancestro: Es cualquier nodo predecesor en una ruta desde la raíz hasta ese nodo. Tenga en cuenta que la raíz no tiene antepasados. En el diagrama anterior, A y B son los antepasados de E.
- Llave: Representa el valor de un nodo.
- Nivel: Representa la generación de un nodo. Un nodo raíz siempre está en el nivel 1. Los nodos secundarios de la raíz están en el nivel 2, los nietos de la raíz están en el nivel 3 y así sucesivamente. En general, cada nodo se encuentra en un nivel superior al de su padre.
- Camino: El camino es una secuencia de aristas consecutivas. En el diagrama anterior, la ruta hacia E es A => B-> E.
- La licenciatura: El grado de un nodo indica el número de hijos que tiene un nodo. En el diagrama anterior, el grado de B y D es 2 cada uno, mientras que el grado de C es 0.
Tipos de árboles C ++
La estructura de datos de árbol se puede clasificar en los siguientes subtipos como se muestra en el diagrama a continuación.
# 1) Árbol general
El árbol general es la representación básica de un árbol. Tiene un nodo y uno o más nodos secundarios. El nodo de nivel superior, es decir, el nodo raíz, está presente en el nivel 1 y todos los demás nodos pueden estar presentes en varios niveles.
En la figura siguiente se muestra un árbol general.
Como se muestra en la figura anterior, un árbol general puede contener cualquier número de subárboles. Los nodos B, C y D están presentes en el nivel 2 y son nodos hermanos. De manera similar, los nodos E, F, G y H también son nodos hermanos.
Los nodos presentes en diferentes niveles pueden exhibir una relación padre-hijo. En la figura anterior, los nodos B, C y D son hijos de A. Los nodos E y F son hijos de B, mientras que los nodos G y H son hijos de D.
El árbol general se muestra a continuación utilizando la implementación de C ++:
|_+_|Producción:
El árbol general creado es el siguiente:
10
/
20 30
/
40
# 2) Bosques
Siempre que eliminamos el nodo raíz del árbol y los bordes que unen los elementos del siguiente nivel y la raíz, obtenemos conjuntos de árboles disjuntos como se muestra a continuación.
En la figura anterior, obtuvimos dos bosques al eliminar el nodo raíz A y los tres bordes que conectaban el nodo raíz con los nodos B, C y D.
# 3) Árbol binario
Una estructura de datos de árbol en la que cada nodo tiene como máximo dos nodos secundarios se denomina árbol binario. Un árbol binario es la estructura de datos de árbol más popular y se utiliza en una variedad de aplicaciones como evaluación de expresiones, bases de datos, etc.
La siguiente figura muestra un árbol binario.
En la figura anterior, vemos que los nodos A, B y D tienen dos hijos cada uno. Un árbol binario en el que cada nodo tiene exactamente cero o dos hijos se denomina árbol binario completo. En este árbol, no hay nodos que tengan un hijo.
Un árbol binario completo tiene un árbol binario que está completamente lleno con la excepción del nivel más bajo que se llena de izquierda a derecha. El árbol binario que se muestra arriba es un árbol binario completo.
A continuación se muestra un programa simple para demostrar un árbol binario. Tenga en cuenta que la salida del árbol es la secuencia transversal en orden del árbol de entrada.
|_+_|Producción:
Árbol binario creado:
5 10 15 20 30 40 45
# 4) Árbol de búsqueda binaria
El árbol binario ordenado se denomina árbol de búsqueda binaria. En un árbol de búsqueda binaria, los nodos de la izquierda son menores que el nodo raíz, mientras que los nodos de la derecha son mayores o iguales que el nodo raíz.
A continuación se muestra un ejemplo de árbol de búsqueda binaria.
En la figura anterior, podemos ver que los nodos de la izquierda son todos menores que 20, que es el elemento raíz. Los nodos de la derecha, por otro lado, son mayores que el nodo raíz. El árbol de búsqueda binaria se utiliza en técnicas de búsqueda y clasificación.
# 5) Árbol de expresión
Un árbol binario que se utiliza para evaluar expresiones aritméticas simples se denomina árbol de expresión.
A continuación se muestra un árbol de expresión simple.
En el árbol de expresión de muestra anterior, representamos la expresión (a + b) / (a-b). Como se muestra en la figura anterior, los nodos no hoja del árbol representan los operadores de la expresión mientras que los nodos hoja representan los operandos.
Los árboles de expresión se utilizan principalmente para resolver expresiones algebraicas.
Técnicas de recorrido de árboles
Hemos visto estructuras de datos lineales como matrices, listas enlazadas, pilas, colas, etc. Todas estas estructuras de datos tienen una técnica de desplazamiento común que atraviesa la estructura solo de una manera, es decir, linealmente.
Pero en el caso de los árboles, tenemos diferentes técnicas de recorrido que se enumeran a continuación:
# 1) En orden: En esta técnica de recorrido, primero atravesamos el subárbol izquierdo hasta que no haya más nodos en el subárbol izquierdo. Después de esto, visitamos el nodo raíz y luego procedemos a atravesar el subárbol derecho hasta que no haya más nodos para atravesar en el subárbol derecho. Por lo tanto, el orden de recorrido inOrder es izquierda-> raíz-> derecha.
# 2) Reserva: Para la técnica de recorrido de preorden, procesamos el nodo raíz primero, luego atravesamos todo el subárbol izquierdo y finalmente, atravesamos el subárbol derecho. Por lo tanto, el orden de recorrido del preorden es raíz-> izquierda-> derecha.
# 3) Pedido posterior: En la técnica de recorrido posterior al orden, atravesamos el subárbol izquierdo, luego el subárbol derecho y finalmente el nodo raíz. El orden de recorrido de la técnica postorder es izquierda-> derecha-> raíz.
Si n es el nodo raíz y 'l' y 'r' son los nodos izquierdo y derecho del árbol, respectivamente, entonces los algoritmos de recorrido del árbol son los siguientes:
En orden (lnr) algoritmo:
- Recorra el subárbol izquierdo usando inOrder (subárbol izquierdo).
- Visite el nodo raíz (n).
- Recorra el subárbol derecho usando inOrder (subárbol derecho).
Algoritmo de reserva (nlr):
- Visite el nodo raíz (n).
- Atraviesa el subárbol izquierdo usando preorden (subárbol izquierdo).
- Atraviesa el subárbol derecho usando preorder (subárbol derecho).
Algoritmo de posorden (lrn):
- Recorra el subárbol izquierdo usando postOrder (subárbol izquierdo).
- Atraviesa el subárbol derecho usando postOrder (subárbol derecho).
- Visite el nodo raíz (n).
A partir de los algoritmos anteriores de técnicas transversales, vemos que las técnicas se pueden aplicar a un árbol dado de forma recursiva para obtener el resultado deseado.
Considere el siguiente árbol.
Utilizando las técnicas de recorrido anteriores, la secuencia transversal del árbol anterior se muestra a continuación:
- Transferencia InOrder: 2 3 5 6 10
- Recorrido de preorden: 6 3 2 5 10
- Traslado de PostOrder: 2 5 3 10 6
Conclusión
Los árboles son una estructura de datos jerárquica no lineal que se utiliza en muchas aplicaciones en el campo del software.
A diferencia de las estructuras de datos lineales que solo tienen una forma de atravesar la lista, podemos atravesar árboles de varias maneras. Tuvimos un estudio detallado de las técnicas de recorrido y los diversos tipos de árboles en este tutorial.
=> Eche un vistazo a la guía para principiantes de C ++ aquí
Lectura recomendada
- Estructura de datos de árbol B y árbol B + en C ++
- Estructura de datos de árbol binario en C ++
- Tipos de riesgos en proyectos de software
- Estructura de datos de montón y árbol AVL en C ++
- Tipos de datos de Python
- 20 preguntas sencillas para comprobar sus conocimientos básicos sobre pruebas de software (Cuestionario en línea)
- Tipos de datos C ++
- Operaciones básicas de entrada / salida en C ++