use strict;
use feature qw(say);
my($root, $n);
# Primero generamos 20 inserciones aleatorias
while ($n++ < 20) { insertar($root, int(rand(1000)))}
#Mostrar el número de nodos que se generaron
print "Nodos totales ($n)\n";
# ahora vaciar el árbol de las tres maneras
print "Preorden: "; pre_orden($root); print "\n";
print "En orden: "; en_orden($root); print "\n";
print "Post orden: "; post_orden($root); print "\n";
for (print "¿Buscar? "; <>; print "¿Buscar? ") {
chomp;
my $Encontrado = buscar($root, $_);
if ($Encontrado) { print "Encontrado $_ en $Encontrado, $Encontrado->{VALOR}\n" }
else { print "No está $_ en el árbol\n" }
}
exit;
# inserta el valor dado en el punto apropiado del árbol proporcionado.
# Si no se proporciona ningún árbol, usamos el aspecto implícito de pasar
# por referencia de @_ para rellenar uno para nuestro llamador.
sub insertar {
my($arbol, $valor) = @_;
unless ($arbol) {
$arbol = {}; # asignar un nuevo nodo
$arbol->{VALOR} = $valor;
$arbol->{IZQUIERDA} = undef;
$arbol->{DERECHA} = undef;
$_[0] = $arbol; # $_[0] es el parámetro de referencia!
return;
}
if ($arbol->{VALOR} > $valor) { insertar($arbol->{IZQUIERDA}, $valor) }
elsif ($arbol->{VALOR} < $valor) { insertar($arbol->{DERECHA}, $valor) }
else { warn "insertar dup del $valor\n" }
# XXX: no dups
}
# Recurrir a la izquierda del hijo,
# luego mostrar el valor actual,
# luego recurre al hijo de la derecha.
sub en_orden {
my($arbol) = @_;
return unless $arbol;
en_orden($arbol->{IZQUIERDA});
print $arbol->{VALOR}, " ";
en_orden($arbol->{DERECHA});
}
# mostrar el valor actual,
# luego recurre al hijo de la izquierda,
# luego recurre al hijo de la derecha.
sub pre_orden {
my($arbol) = @_;
return unless $arbol;
print $arbol->{VALOR}, " ";
pre_orden($arbol->{IZQUIERDA});
pre_orden($arbol->{DERECHA});
}
# Recurre al hijo de la izquierda,
# luego recurre al hijo de la derecha,
# luego mostrar el valor actual.
sub post_orden {
my($arbol) = @_;
return unless $arbol;
post_orden($arbol->{IZQUIERDA});
post_orden($arbol->{DERECHA});
print $arbol->{VALOR}, " ";
}
# averigua si el valor proporcionado está en el árbol.
# si es así, devuelve el nodo en el que se encontró el valor.
# reducir el tiempo de búsqueda buscando sólo en la rama correcta
# basándose en el valor actual.
# mostrar el valor actual
sub buscar {
my($arbol, $valor) = @_;
return unless $arbol;
if ($arbol->{VALOR} == $valor) {
return $arbol;
}
buscar($arbol->{ ($valor < $arbol->{VALOR}) ? "IZQUIERDA" : "DERECHA"}, $valor)
}
