Lección 11 · 11 de 20

Un árbol binario de búsqueda · C

Construya en C un árbol binario de búsqueda que cuenta palabras: inserción recursiva, búsqueda, recorrido en orden y liberación del árbol.

C · Un árbol binario de búsqueda en DMarlon Studio: el código del ejemplo y su salida en la terminal

En un árbol binario de búsqueda cada nodo tiene dos hijos, left y right, y una regla: las palabras menores van a la izquierda y las mayores, a la derecha. Gracias a esa regla, buscar baja por una sola rama y en cada nivel descarta la mitad del árbol, si está equilibrado.

insert es recursiva. Si llega a un hueco (n == NULL), crea el nodo con calloc, que deja count a 0 e hijos a NULL, y copia la palabra. Después compara con strcmp: si es menor, inserta en el subárbol izquierdo; si es mayor, en el derecho; si es igual, suma uno a count. Un nodo recién creado pasa así de 0 a 1, y una palabra repetida como fig llega a 3.

find hace lo mismo sin recursión: mientras no encuentre la palabra, baja a la izquierda o a la derecha. Devuelve el nodo o NULL, como con lime.

in_order visita primero el subárbol izquierdo, después el nodo y por último el derecho: un recorrido en orden, que escribe las palabras ordenadas alfabéticamente sin haber ordenado nada. La raíz es melon porque fue la primera palabra insertada.

free_tree libera en postorden: primero los dos hijos y después el nodo. Al revés, al liberar el nodo se perderían los punteros a sus hijos.

Código · main.c

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct Node { char word[16]; int count; struct Node *left, *right; } Node;Node *insert(Node *n, const char *word) {  // smaller to the left, bigger to the right    if (n == NULL) {  // empty spot found: the new node goes here        if (!(n = calloc(1, sizeof *n))) exit(EXIT_FAILURE);  // count 0, children NULL        snprintf(n->word, sizeof n->word, "%s", word);    }    int cmp = strcmp(word, n->word);    if (cmp < 0) n->left = insert(n->left, word);    else if (cmp > 0) n->right = insert(n->right, word);    else n->count++;  // the word is here: new (0 -> 1) or repeated    return n;}const Node *find(const Node *n, const char *word) {  // one branch per level    while (n && strcmp(word, n->word) != 0) n = strcmp(word, n->word) < 0 ? n->left : n->right;    return n;}void in_order(const Node *n) {  // left, node, right: alphabetical order    if (n) { in_order(n->left); printf("  %-6s x%d\n", n->word, n->count); in_order(n->right); }}void free_tree(Node *n) { if (n) { free_tree(n->left); free_tree(n->right); free(n); } }int main(void) {    const char *words[] = {"melon", "fig", "pear", "apple", "kiwi", "fig", "plum", "apple", "fig"};    Node *root = NULL;  // an empty tree    for (int i = 0; i < 9; i++) root = insert(root, words[i]);    in_order(root);    printf("Root: %s, kiwi: %s, lime: %s\n", root->word,           find(root, "kiwi") ? "found" : "missing", find(root, "lime") ? "found" : "missing");    free_tree(root);  // children first, then the node itself    return 0;}

Salida · cc main.c -o main && ./main

  apple  x2
  fig    x3
  kiwi   x1
  melon  x1
  pear   x1
  plum   x1
Root: melon, kiwi: found, lime: missing

Para recordar

Menores a la izquierda, mayores a la derecha.
Buscar e insertar recorren una sola rama.
El recorrido en orden da los datos ordenados.
Se libera en postorden: hijos primero, nodo después.

Ejercicio

Escriba int height(const Node *n) (0 para NULL, y 1 más la altura del hijo más alto) y compare la altura del árbol con la que sale si inserta las palabras ya ordenadas.