Árbol binario de búsqueda

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izq = None
        self.der = None


def insertar(n, x):
    """Inserta x y devuelve la raíz del subárbol (así se engancha el nodo nuevo a su padre)."""
    if n is None:
        return Nodo(x)                          # hueco libre: aquí va
    if x < n.valor:
        n.izq = insertar(n.izq, x)              # menores a la izquierda
    elif x > n.valor:
        n.der = insertar(n.der, x)              # mayores a la derecha
    return n                                    # (los repetidos no se insertan)


def contiene(n, x):
    while n is not None:
        if x == n.valor:
            return True
        n = n.izq if x < n.valor else n.der     # como en la búsqueda binaria
    return False


def inorden(n, l):                              # izquierda, nodo, derecha
    if n is None:
        return
    inorden(n.izq, l)
    l.append(n.valor)
    inorden(n.der, l)


def preorden(n, l):                             # nodo, izquierda, derecha
    if n is None:
        return
    l.append(n.valor)
    preorden(n.izq, l)
    preorden(n.der, l)


def altura(n):
    return 0 if n is None else 1 + max(altura(n.izq), altura(n.der))


raiz = None
for x in [50, 30, 70, 20, 40, 60, 80, 45]:
    raiz = insertar(raiz, x)
en_orden, pre = [], []
inorden(raiz, en_orden)
preorden(raiz, pre)
print("Inorden (ordenado):", en_orden)
print("Preorden:", pre)
print("Altura:", altura(raiz))
print("¿Contiene 45?", "sí" if contiene(raiz, 45) else "no", "· ¿Contiene 65?", "sí" if contiene(raiz, 65) else "no")

class Nodo {
    constructor(valor) {
        this.valor = valor;
        this.izq = null;
        this.der = null;
    }
}

/** Inserta x y devuelve la raíz del subárbol (así se engancha el nodo nuevo a su padre). */
function insertar(n, x) {
    if (n === null) return new Nodo(x);                // hueco libre: aquí va
    if (x < n.valor) n.izq = insertar(n.izq, x);       // menores a la izquierda
    else if (x > n.valor) n.der = insertar(n.der, x);  // mayores a la derecha
    return n;                                          // (los repetidos no se insertan)
}

function contiene(n, x) {
    while (n !== null) {
        if (x === n.valor) return true;
        n = x < n.valor ? n.izq : n.der;               // como en la búsqueda binaria
    }
    return false;
}

function inorden(n, l) {                               // izquierda, nodo, derecha
    if (n === null) return;
    inorden(n.izq, l);
    l.push(n.valor);
    inorden(n.der, l);
}

function preorden(n, l) {                              // nodo, izquierda, derecha
    if (n === null) return;
    l.push(n.valor);
    preorden(n.izq, l);
    preorden(n.der, l);
}

const altura = (n) => (n === null ? 0 : 1 + Math.max(altura(n.izq), altura(n.der)));

let raiz = null;
for (const x of [50, 30, 70, 20, 40, 60, 80, 45]) raiz = insertar(raiz, x);
const enOrden = [], pre = [];
inorden(raiz, enOrden);
preorden(raiz, pre);
const lista = (l) => "[" + l.join(", ") + "]";
console.log("Inorden (ordenado): " + lista(enOrden));
console.log("Preorden: " + lista(pre));
console.log("Altura: " + altura(raiz));
console.log(`¿Contiene 45? ${contiene(raiz, 45) ? "sí" : "no"} · ¿Contiene 65? ${contiene(raiz, 65) ? "sí" : "no"}`);

using System;
using System.Collections.Generic;

class Nodo {
    public int Valor;
    public Nodo? Izq, Der;
    public Nodo(int valor) { Valor = valor; }
}

class Program {
    // Inserta x y devuelve la raíz del subárbol (así se engancha el nodo nuevo a su padre).
    static Nodo Insertar(Nodo? n, int x) {
        if (n == null) return new Nodo(x);                 // hueco libre: aquí va
        if (x < n.Valor) n.Izq = Insertar(n.Izq, x);       // menores a la izquierda
        else if (x > n.Valor) n.Der = Insertar(n.Der, x);  // mayores a la derecha
        return n;                                          // (los repetidos no se insertan)
    }

    static bool Contiene(Nodo? n, int x) {
        while (n != null) {
            if (x == n.Valor) return true;
            n = x < n.Valor ? n.Izq : n.Der;               // como en la búsqueda binaria
        }
        return false;
    }

    static void Inorden(Nodo? n, List<int> l) {            // izquierda, nodo, derecha
        if (n == null) return;
        Inorden(n.Izq, l);
        l.Add(n.Valor);
        Inorden(n.Der, l);
    }

    static void Preorden(Nodo? n, List<int> l) {           // nodo, izquierda, derecha
        if (n == null) return;
        l.Add(n.Valor);
        Preorden(n.Izq, l);
        Preorden(n.Der, l);
    }

    static int Altura(Nodo? n) => n == null ? 0 : 1 + Math.Max(Altura(n.Izq), Altura(n.Der));

    static void Main() {
        Nodo? raiz = null;
        foreach (int x in new[] { 50, 30, 70, 20, 40, 60, 80, 45 }) raiz = Insertar(raiz, x);
        var enOrden = new List<int>();
        var pre = new List<int>();
        Inorden(raiz, enOrden);
        Preorden(raiz, pre);
        Console.WriteLine(
quot;Inorden (ordenado): [{string.Join(", ", enOrden)}]");
        Console.WriteLine(
quot;Preorden: [{string.Join(", ", pre)}]");
        Console.WriteLine(
quot;Altura: {Altura(raiz)}");
        Console.WriteLine(
quot;¿Contiene 45? {(Contiene(raiz, 45) ? "sí" : "no")} · ¿Contiene 65? {(Contiene(raiz, 65) ? "sí" : "no")}");
    }
}

<?php
class Nodo {
    public ?Nodo $izq = null;
    public ?Nodo $der = null;
    public function __construct(public int $valor) { }
}

/** Inserta $x y devuelve la raíz del subárbol (así se engancha el nodo nuevo a su padre). */
function insertar(?Nodo $n, int $x): Nodo {
    if ($n === null) return new Nodo($x);                      // hueco libre: aquí va
    if ($x < $n->valor) $n->izq = insertar($n->izq, $x);       // menores a la izquierda
    elseif ($x > $n->valor) $n->der = insertar($n->der, $x);   // mayores a la derecha
    return $n;                                                 // (los repetidos no se insertan)
}

function contiene(?Nodo $n, int $x): bool {
    while ($n !== null) {
        if ($x === $n->valor) return true;
        $n = $x < $n->valor ? $n->izq : $n->der;               // como en la búsqueda binaria
    }
    return false;
}

function inorden(?Nodo $n, array &$l): void {                  // izquierda, nodo, derecha
    if ($n === null) return;
    inorden($n->izq, $l);
    $l[] = $n->valor;
    inorden($n->der, $l);
}

function preorden(?Nodo $n, array &$l): void {                 // nodo, izquierda, derecha
    if ($n === null) return;
    $l[] = $n->valor;
    preorden($n->izq, $l);
    preorden($n->der, $l);
}

function altura(?Nodo $n): int {
    return $n === null ? 0 : 1 + max(altura($n->izq), altura($n->der));
}

$raiz = null;
foreach ([50, 30, 70, 20, 40, 60, 80, 45] as $x) $raiz = insertar($raiz, $x);
$enOrden = [];
$pre = [];
inorden($raiz, $enOrden);
preorden($raiz, $pre);
echo "Inorden (ordenado): [" . implode(", ", $enOrden) . "]\n";
echo "Preorden: [" . implode(", ", $pre) . "]\n";
echo "Altura: " . altura($raiz) . "\n";
echo "¿Contiene 45? " . (contiene($raiz, 45) ? "sí" : "no") . " · ¿Contiene 65? " . (contiene($raiz, 65) ? "sí" : "no") . "\n";

def borrar(n, x):
    """Borra x del subárbol n y devuelve la nueva raíz de ese subárbol."""
    if n is None:
        return None                           # no estaba
    if x < n.valor:
        n.izq = borrar(n.izq, x)
    elif x > n.valor:
        n.der = borrar(n.der, x)
    else:
        if n.izq is None:                     # casos 1 y 2: sin hijos o con uno,
            return n.der                      # el hijo ocupa su lugar
        if n.der is None:
            return n.izq
        sucesor = n.der                       # caso 3: dos hijos
        while sucesor.izq is not None:        # el menor de la derecha
            sucesor = sucesor.izq
        n.valor = sucesor.valor               # copia su valor aquí
        n.der = borrar(n.der, sucesor.valor)  # y lo borra de la derecha
    return n

/** Borra x del subárbol n y devuelve la nueva raíz de ese subárbol. */
function borrar(n, x) {
    if (n === null) return null;                      // no estaba
    if (x < n.valor) n.izq = borrar(n.izq, x);
    else if (x > n.valor) n.der = borrar(n.der, x);
    else {
        if (n.izq === null) return n.der;             // casos 1 y 2: sin hijos o con uno,
        if (n.der === null) return n.izq;             // el hijo ocupa su lugar
        let sucesor = n.der;                          // caso 3: dos hijos
        while (sucesor.izq !== null) sucesor = sucesor.izq;   // el menor de la derecha
        n.valor = sucesor.valor;                      // copia su valor aquí
        n.der = borrar(n.der, sucesor.valor);         // y lo borra de la derecha
    }
    return n;
}

// Borra x del subárbol n y devuelve la nueva raíz de ese subárbol.
static Nodo? Borrar(Nodo? n, int x) {
    if (n == null) return null;                       // no estaba
    if (x < n.Valor) n.Izq = Borrar(n.Izq, x);
    else if (x > n.Valor) n.Der = Borrar(n.Der, x);
    else {
        if (n.Izq == null) return n.Der;              // casos 1 y 2: sin hijos o con uno,
        if (n.Der == null) return n.Izq;              // el hijo ocupa su lugar
        Nodo sucesor = n.Der;                         // caso 3: dos hijos
        while (sucesor.Izq != null) sucesor = sucesor.Izq;   // el menor de la derecha
        n.Valor = sucesor.Valor;                      // copia su valor aquí
        n.Der = Borrar(n.Der, sucesor.Valor);         // y lo borra de la derecha
    }
    return n;
}

/** Borra $x del subárbol $n y devuelve la nueva raíz de ese subárbol. */
function borrar(?Nodo $n, int $x): ?Nodo {
    if ($n === null) return null;                     // no estaba
    if ($x < $n->valor) $n->izq = borrar($n->izq, $x);
    elseif ($x > $n->valor) $n->der = borrar($n->der, $x);
    else {
        if ($n->izq === null) return $n->der;         // casos 1 y 2: sin hijos o con uno,
        if ($n->der === null) return $n->izq;         // el hijo ocupa su lugar
        $sucesor = $n->der;                           // caso 3: dos hijos
        while ($sucesor->izq !== null) $sucesor = $sucesor->izq;   // el menor de la derecha
        $n->valor = $sucesor->valor;                  // copia su valor aquí
        $n->der = borrar($n->der, $sucesor->valor);   // y lo borra de la derecha
    }
    return $n;
}