Árbol binario en C
En C, un árbol binario es una instancia de una estructura de datos de árbol con un nodo principal que puede tener un número máximo de dos nodos secundarios; 0, 1 o 2 nodos descendientes. Cada nodo en un árbol binario tiene un valor propio y dos punteros a sus hijos, un puntero para el hijo izquierdo y otro para el hijo derecho.
Declaración de árbol binario
A árbol binario se puede declarar en C usando un objeto llamado estructura que representa uno de los nodos del árbol.
estructura nodo {
tipo de datos var_name ;
estructura nodo * izquierda ;
estructura nodo * bien ;
} ;
Arriba hay una declaración de uno árbol binario nombre de nodo como un nodo. Tiene tres valores; uno es la variable de almacenamiento de datos y los otros dos son los punteros al niño. (hijo izquierdo y derecho del nodo padre).
Datos del árbol binario
Incluso para grandes conjuntos de datos, utilizando un árbol binario hace que la búsqueda sea más fácil y rápida. El número de ramas de los árboles no está limitado. A diferencia de una matriz, los árboles de cualquier tipo se pueden hacer y aumentar según lo que se requiera de un individuo.
Implementación de árbol binario en C
La siguiente es una guía paso a paso para implementar un Árbol binario Cª.
Paso 1: declarar un árbol de búsqueda binario
Cree un nodo de estructura que tenga tres tipos de datos, como datos, *hijo_izquierdo y *hijo_derecho, donde los datos pueden ser de tipo entero, y los nodos *hijo_izquierdo y *hijo_derecho pueden declararse como NULL o no.
estructura nodo{
En t datos ;
estructura nodo * niño_derecho ;
estructura nodo * niño_izquierdo ;
} ;
Paso 2: crear nuevos nodos en el árbol de búsqueda binaria
Cree un nuevo nodo creando una función que acepte un número entero como argumento y proporcione el puntero al nuevo nodo creado con ese valor. Utilice la función malloc() en C para la asignación de memoria dinámica para el nodo creado. Inicialice el elemento secundario izquierdo y derecho en NULL y devuelva el nombre de nodo.
estructura nodo * crear ( datos de tipo de datos )
{
estructura nodo * nombre del nodo = malloc ( tamaño de ( estructura nodo ) ) ;
nombre del nodo -> datos = valor ;
nombre del nodo -> niño_izquierdo = nombre del nodo -> niño_derecho = NULO ;
devolver nombre del nodo ;
}
Paso 3: Inserte los niños derecho e izquierdo en el árbol binario
Cree las funciones insert_left e insert_right que aceptarán dos entradas, que son el valor que se insertará y el puntero al nodo al que se conectarán ambos elementos secundarios. Llame a la función de creación para crear un nuevo nodo y asigne el puntero devuelto al puntero izquierdo del hijo izquierdo o al puntero derecho del hijo derecho del padre raíz.
estructura nodo * insertar_izquierda ( estructura nodo * raíz , datos de tipo de datos ) {raíz -> izquierda = crear ( datos ) ;
devolver raíz -> izquierda ;
}
estructura nodo * insert_right ( estructura nodo * raíz , datos de tipo de datos ) {
raíz -> bien = crear ( datos ) ;
devolver raíz -> bien ;
}
Paso 4: Mostrar nodos de árbol binario usando métodos transversales
Podemos mostrar árboles usando tres métodos de recorrido en C. Estos métodos de recorrido son:
1: Recorrido de pedido anticipado
En este método transversal, atravesaremos los nodos en una dirección desde parent_node->left_child->right_child .
vacío hacer un pedido ( nodo * raíz ) {si ( raíz ) {
imprimir ( '%d \norte ' , raíz -> datos ) ;
display_pre_order ( raíz -> izquierda ) ;
display_pre_order ( raíz -> bien ) ;
}
}
2: Recorrido posterior al pedido
En este método transversal, atravesaremos los nodos en una dirección desde el hijo_izquierdo->hijo_derecho->nodo_padre-> .
vacío display_post_order ( nodo * raíz ) {si ( árbol binario ) {
display_post_order ( raíz -> izquierda ) ;
display_post_order ( raíz -> bien ) ;
imprimir ( '%d \norte ' , raíz -> datos ) ;
}
}
3: Recorrido en orden
En este método transversal, atravesaremos los nodos en una dirección desde nodo_izquierdo->hijo_raíz->hijo_derecho .
vacío mostrar_en_orden ( nodo * raíz ) {si ( árbol binario ) {
mostrar_en_orden ( raíz -> izquierda ) ;
imprimir ( '%d \norte ' , raíz -> datos ) ;
mostrar_en_orden ( raíz -> bien ) ;
}
}
Paso 5: realizar la eliminación en el árbol binario
Podemos borrar lo creado Árbol binario eliminando ambos elementos secundarios con la función de nodo principal en C de la siguiente manera.
vacío eliminar_t ( nodo * raíz ) {si ( raíz ) {
eliminar_t ( raíz -> izquierda ) ;
eliminar_t ( raíz -> bien ) ;
gratis ( raíz ) ;
}
}
Programa C del árbol de búsqueda binaria
La siguiente es la implementación completa del árbol de búsqueda binario en la programación C:
#include#include
estructura nodo {
En t valor ;
estructura nodo * izquierda , * bien ;
} ;
estructura nodo * nodo1 ( En t datos ) {
estructura nodo * tmp = ( estructura nodo * ) malloc ( tamaño de ( estructura nodo ) ) ;
tmp -> valor = datos ;
tmp -> izquierda = tmp -> bien = NULO ;
devolver tmp ;
}
vacío imprimir ( estructura nodo * nodo_raíz ) // mostrando los nodos!
{
si ( nodo_raíz != NULO ) {
imprimir ( nodo_raíz -> izquierda ) ;
imprimir ( '%d \norte ' , nodo_raíz -> valor ) ;
imprimir ( nodo_raíz -> bien ) ;
}
}
estructura nodo * insertar_nodo ( estructura nodo * nodo , En t datos ) // insertando nodos!
{
si ( nodo == NULO ) devolver nodo1 ( datos ) ;
si ( datos < nodo -> valor ) {
nodo -> izquierda = insertar_nodo ( nodo -> izquierda , datos ) ;
} demás si ( datos > nodo -> valor ) {
nodo -> bien = insertar_nodo ( nodo -> bien , datos ) ;
}
devolver nodo ;
}
En t principal ( ) {
imprimir ( '¡Implementación en C del árbol de búsqueda binaria! \norte \norte ' ) ;
estructura nodo * padre = NULO ;
padre = insertar_nodo ( padre , 10 ) ;
insertar_nodo ( padre , 4 ) ;
insertar_nodo ( padre , 66 ) ;
insertar_nodo ( padre , 45 ) ;
insertar_nodo ( padre , 9 ) ;
insertar_nodo ( padre , 7 ) ;
imprimir ( padre ) ;
devolver 0 ;
}
En el código anterior, primero declaramos un nodo usando estructura . Luego inicializamos un nuevo nodo como ' nodo1 ” y asignar memoria dinámicamente usando malloc() en C con datos y dos punteros escriba niños usando el nodo declarado. Después de esto, mostramos el nodo por imprimirf() función y llámela en el principal() función. Entonces el nodo_inserción() se crea la función, donde si los datos del nodo son NULL, entonces nodo1 se retira, de lo contrario, los datos se colocan en el nodo (padre) del niño izquierdo y derecho. El programa inicia su ejecución desde el principal() función, que genera un nodo usando algunos nodos de muestra como hijos y luego usa métodos transversales en orden para imprimir el contenido del nodo.
Producción
Conclusión
Los árboles se emplean con frecuencia para mantener los datos en forma no lineal. árboles binarios son tipos de arboles donde cada nodo (padre) tiene dos descendientes el hijo izquierdo y el hijo derecho. A árbol binario es un método versátil de transferir y almacenar datos. Es más eficiente en comparación con Linked-List en C. En el artículo anterior, hemos visto el concepto de un Árbol binario con la implementación paso a paso de un Árbol de búsqueda binaria Cª.