Un árbol binario de búsqueda en C

Insertar desciende a izquierda o derecha; buscar sigue el mismo camino.

#include <stdlib.h>

typedef struct Tree {
    int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

Tree *insert(Tree *root, int key) {
    if (root == NULL) {
        Tree *node = malloc(sizeof *node);
        if (node != NULL) {
            node->key = key;
            node->left = NULL;
            node->right = NULL;
        }
        return node;
    }
    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }
    return root;
}

int contains(const Tree *root, int key) {
    while (root != NULL) {
        if (key == root->key) {
            return 1;
        }
        root = (key < root->key) ? root->left : root->right;
    }
    return 0;
}

Cómo funciona

1. Cada subárbol izquierdo guarda claves menores; cada derecho, mayores.
2. La recursión refleja la estructura exactamente.
3. Un recorrido en orden visita las claves ya ordenadas.

Palabras clave y builtins usados aquí

• NULL
• const
• else
• if
• int
• return
• sizeof
• struct
• typedef
• while

El intento, en números

Líneas

35

Caracteres a escribir

600

Tokens

206

Ritmo de tres estrellas

105 tpm

Al ritmo de tres estrellas de 105 tokens por minuto, este intento toma unos 118 segundos.

Escribe este fragmento

Paso 1 de 4 en Árboles, tablas y heaps; paso 11 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →