Estructuras No Lineales

Árboles Binarios de Búsqueda (BST)

Nodos, punteros, referencias e in-order traversal en C, Java, JavaScript y Python.

1. Propiedad Fundamental del BST

En un BST, para todo nodo X: los valores del subárbol izquierdo son menores (< X) y los del subárbol derecho son mayores (> X). El recorrido In-Order produce los elementos ordenados.

ESTRUCTURA DE UN NODO

Valor / KeyDato del nodo

Puntero / Ref IzquierdaSubárbol < Key

Puntero / Ref DerechaSubárbol > Key

2. C: struct Node con Punteros

En C se define con `struct Node` y punteros auto-referenciados `struct Node *left, *right`.

bst.c

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* createNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = val; n->left = n->right = NULL;
    return n;
}

3. Java: Clase TreeNode

Java maneja las conexiones del árbol mediante referencias a objetos en el Heap.

BST.java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

4. JavaScript: Clases ES6

JS implementa la estructura con clases de ES6 y punteros `null` para hojas.

bst.js

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

5. Python: Recorrido In-Order Recursivo

El recorrido In-Order (Izquierda ➔ Raíz ➔ Derecha) visita los nodos de menor a mayor valor.

bst.py

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def in_order(root):
    if root:
        in_order(root.left)
        print(root.val)
        in_order(root.right)

6. Inspector de Árbol BST

Árbol con Raíz 10, Izq 5, Der 15

Recorrido In-Order ➔ 5, 10, 15 (Secuencia Ordenada)