Edición didáctica en español. El código y sus salidas conservan el original.
Árbol binario de búsqueda en C
Inserta y busca claves usando el orden de los subárboles.
En un árbol binario de búsqueda, las claves menores se colocan en un subárbol y las mayores en el otro. Define una política para duplicados y mantenla en todas las operaciones. Un recorrido en orden visita las claves en orden creciente.
La búsqueda compara la clave con el nodo actual y elige un solo hijo. Su coste depende de la altura: O(log N) en un árbol equilibrado, pero O(N) si los datos forman una cadena. Un árbol binario de búsqueda simple no se equilibra automáticamente.
Comprueba asignaciones y libera los hijos antes del nodo padre. Prueba claves ordenadas, duplicadas y ausentes; observa cómo cambia la forma del árbol.
Código C
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode {
int val;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
/* Return 0 on allocation failure without changing existing nodes. */
int insert(BSTNode **root, int val) {
if (*root == NULL) {
BSTNode *node = malloc(sizeof *node);
if (node == NULL) return 0;
node->val = val;
node->left = node->right = NULL;
*root = node;
return 1;
}
if (val < (*root)->val) return insert(&(*root)->left, val);
if (val > (*root)->val) return insert(&(*root)->right, val);
return 1; /* Ignore duplicate keys. */
}
void inorder(const BSTNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
}
void freeBST(BSTNode *root) {
if (root != NULL) {
freeBST(root->left);
freeBST(root->right);
free(root);
}
}
int main(void) {
BSTNode *root = NULL;
const int keys[] = {50, 30, 20, 40, 70, 60, 80};
for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++) {
if (!insert(&root, keys[i])) {
fputs("Unable to allocate a BST node.\n", stderr);
freeBST(root);
return EXIT_FAILURE;
}
}
printf("BST In-Order Sorted Traversal: ");
inorder(root);
printf("\n");
freeBST(root);
return EXIT_SUCCESS;
}Salida esperada
BST In-Order Sorted Traversal: 20 30 40 50 60 70 80
Preguntas frecuentes
¿Por qué el código y la salida siguen en inglés?
Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.