binary tree data structure c
Este tutorial detallado sobre el árbol binario en C ++ explica los tipos, la representación, el recorrido, las aplicaciones y la implementación de árboles binarios en C ++:
Un árbol binario es una estructura de datos de árbol ampliamente utilizada. Cuando cada nodo de un árbol tiene como máximo dos nodos secundarios, el árbol se denomina árbol binario.
Entonces, un árbol binario típico tendrá los siguientes componentes:
- Un subárbol izquierdo
- Un nodo raíz
- Un subárbol derecho
=> Tenga cuidado con la lista completa de tutoriales de C ++ de esta serie.
Lo que vas a aprender:
- Árbol binario en C ++
- Tipos de árbol binario
- Representación de árbol binario
- Implementación de árbol binario en C ++
- Recorrido de árbol binario
- Aplicaciones del árbol binario
- Conclusión
- Lectura recomendada
Árbol binario en C ++
A continuación se muestra una representación pictórica de un árbol binario:
En un árbol binario dado, el número máximo de nodos en cualquier nivel es 2l-1donde 'l' es el número de nivel.
Por lo tanto, en el caso del nodo raíz en el nivel 1, el número máximo de nodos = 21-1= 20= 1
Como cada nodo en un árbol binario tiene como máximo dos nodos, el número máximo de nodos en el siguiente nivel será, 2 * 2l-1.
cómo abrir archivos .dat en windows
Dado un árbol binario de profundidad o altura de h, el número máximo de nodos en un árbol binario de altura h = 2h– 1.
Por lo tanto, en un árbol binario de altura 3 (mostrado arriba), el número máximo de nodos = 23-1 = 7.
Ahora analicemos los distintos tipos de árboles binarios.
Tipos de árbol binario
A continuación se muestran los tipos más comunes de árboles binarios.
# 1) Árbol binario completo
Un árbol binario en el que cada nodo tiene 0 o 2 hijos se denomina árbol binario completo.
Arriba se muestra un árbol binario completo en el que podemos ver que todos sus nodos excepto los nodos hoja tienen dos hijos. Si L es el número de nodos hoja y 'l' es el número de nodos internos o no hojas, entonces para un árbol binario completo, L = l + 1.
# 2) Árbol binario completo
Un árbol binario completo tiene todos los niveles llenos excepto el último nivel y el último nivel tiene todos sus nodos tanto como a la izquierda.
El árbol que se muestra arriba es un árbol binario completo. Un ejemplo típico de un árbol binario completo es un montón binario que discutiremos en los tutoriales posteriores.
# 3) Árbol binario perfecto
Un árbol binario se denomina perfecto cuando todos sus nodos internos tienen dos hijos y todos los nodos hoja están en el mismo nivel.
Un ejemplo de árbol binario que se muestra arriba es un árbol binario perfecto ya que cada uno de sus nodos tiene dos hijos y todos los nodos hoja están en el mismo nivel.
Un árbol binario perfecto de altura h tiene 2h- 1 número de nodos.
# 4) Un árbol degenerado
Un árbol binario donde cada nodo interno tiene solo un hijo se llama árbol degenerado.
El árbol que se muestra arriba es un árbol degenerado. En lo que respecta al rendimiento de este árbol, los árboles degenerados son los mismos que las listas vinculadas.
# 5) Árbol binario equilibrado
Un árbol binario en el que la profundidad de los dos subárboles de cada nodo nunca difiere en más de 1 se denomina árbol binario equilibrado.
El árbol binario que se muestra arriba es un árbol binario balanceado, ya que la profundidad de los dos subárboles de cada nodo no es más de 1. Los árboles AVL que vamos a discutir en nuestros tutoriales posteriores son un árbol balanceado común.
Representación de árbol binario
A un árbol binario se le asigna memoria de dos formas.
# 1) Representación secuencial
Esta es la técnica más sencilla para almacenar una estructura de datos de árbol. Se utiliza una matriz para almacenar los nodos del árbol. El número de nodos en un árbol define el tamaño de la matriz. El nodo raíz del árbol se almacena en el primer índice de la matriz.
En general, si un nodo se almacena en el ithubicación, entonces su hijo izquierdo y derecho se almacena en 2i y 2i + 1 ubicación respectivamente.
Considere el siguiente árbol binario.
La representación secuencial del árbol binario anterior es la siguiente:
En la representación anterior, vemos que el hijo izquierdo y derecho de cada nodo se almacena en las ubicaciones 2 * (ubicación_nodo) y 2 * (ubicación_nodo) +1 respectivamente.
Por ejemplo, la ubicación del nodo 3 en la matriz es 3. Por lo tanto, su hijo izquierdo se colocará en 2 * 3 = 6. Su hijo derecho estará en la ubicación 2 * 3 +1 = 7. Como podemos ver en la matriz, los hijos de 3 que son 6 y 7 se colocan en las ubicaciones 6 y 7 de la matriz.
La representación secuencial del árbol es ineficaz ya que la matriz que se utiliza para almacenar los nodos del árbol ocupa mucho espacio en la memoria. A medida que el árbol crece, esta representación se vuelve ineficaz y difícil de manejar.
Este inconveniente se supera almacenando los nodos del árbol en una lista vinculada. Tenga en cuenta que si el árbol está vacío, la primera ubicación que almacena el nodo raíz se establecerá en 0.
# 2) Representación de lista vinculada
En este tipo de representación, se utiliza una lista vinculada para almacenar los nodos del árbol. Varios nodos están dispersos en la memoria en ubicaciones no contiguas y los nodos están conectados usando la relación padre-hijo como un árbol.
El siguiente diagrama muestra una representación de lista enlazada para un árbol.
ejemplo de interfaz abstracta en java
Como se muestra en la representación anterior, cada nodo de lista vinculado tiene tres componentes:
- Puntero izquierdo
- Parte de datos
- Puntero derecho
El puntero izquierdo tiene un puntero al hijo izquierdo del nodo; el puntero derecho tiene un puntero al hijo derecho del nodo, mientras que la parte de datos contiene los datos reales del nodo. Si no hay hijos para un nodo dado (nodo hoja), los punteros izquierdo y derecho para ese nodo se establecen en nulo como se muestra en la figura anterior.
Implementación de árbol binario en C ++
A continuación, desarrollamos un programa de árbol binario utilizando una representación de lista enlazada en C ++. Usamos una estructura para declarar un solo nodo y luego, usando una clase, desarrollamos una lista vinculada de nodos.
|_+_|Producción:
Árbol binario creado:
5 10 15 20 30 40 45
Recorrido de árbol binario
Ya hemos hablado de los recorridos en nuestro tutorial básico sobre árboles. En esta sección, implementemos un programa que inserta nodos en el árbol binario y también demuestra los tres recorridos, es decir, en orden, preorden y posorden, para un árbol binario.
|_+_| Producción:
Traversal en orden:
A B C D E F G
Cruce de pedidos por correo:
G F E D C B A
Recorrido de reserva:
A B C D E F G
Aplicaciones del árbol binario
Un árbol binario se utiliza en muchas aplicaciones para almacenar datos.
Algunas de las aplicaciones importantes de los árboles binarios se enumeran a continuación:
- Árboles de búsqueda binaria: Los árboles binarios se utilizan para construir un árbol de búsqueda binario que se utiliza en muchas aplicaciones de búsqueda como conjuntos y mapas en muchas bibliotecas de idiomas.
- Árboles de hachís: Se utiliza para verificar hashes principalmente en aplicaciones de firma de imágenes especializadas.
- Muchísimo: Los montones se utilizan para implementar colas de prioridad que se utilizan para enrutadores, procesadores de programación en el sistema operativo, etc.
- Codificación de Huffman: El árbol de codificación de Huffman se utiliza en algoritmos de compresión (como la compresión de imágenes), así como en aplicaciones criptográficas.
- Árbol de sintaxis: Los compiladores a menudo construyen árboles de sintaxis que no son más que árboles binarios para analizar las expresiones utilizadas en el programa.
Conclusión
Los árboles binarios son estructuras de datos ampliamente utilizadas en la industria del software. Los árboles binarios son los árboles cuyos nodos tienen como máximo dos nodos secundarios. Hemos visto varios tipos de árboles binarios como un árbol binario completo, un árbol binario completo, un árbol binario perfecto, un árbol binario degenerado, un árbol binario equilibrado, etc.
Los datos del árbol binario también se pueden atravesar usando técnicas de cruce en orden, preorden y posorden que hemos visto en nuestro tutorial anterior. En la memoria, un árbol binario se puede representar mediante una lista enlazada (memoria no contigua) o matrices (representación secuencial).
La representación de listas enlazadas es más eficiente en comparación con las matrices, ya que las matrices ocupan mucho espacio.
=> Vea los mejores tutoriales de capacitación de C ++ aquí.
Lectura recomendada
- Estructura de datos de montón y árbol AVL en C ++
- Estructura de datos de árbol B y árbol B + en C ++
- Estructura de datos de cola en C ++ con ilustración
- Estructura de datos de pila en C ++ con ilustración
- Estructura de datos de lista enlazada circular en C ++ con ilustración
- Estructura de datos de lista vinculada en C ++ con ilustración
- Introducción a las estructuras de datos en C ++
- Estructura de datos de cola de prioridad en C ++ con ilustración