Grafos y árboles

Podemos utilizar los registros que acabamos de ver para representar árboles y, de modo más general, grafos. Cada nodo será un registro que apuntará a sus vecinos según la topología del grafo correspondiente.

Figura 3.3: Ejemplo de árbol binario.

Os muestro un ejemplo muy sencillo para un nodo de un árbol binario, donde cada nodo tiene a lo sumo dos hijos, el derecho y el izquierdo:

my $nodoBin = {
	VALOR => $valor,
	IZQ => $rizq,        # referencia al nodo hijo izquierdo
	DER => $rder         # referencia al nodo hijo derecho
};

Si un nodo puede conectarse a un número indeterminado de nodos, entonces es mejor incluir las referencias a esos nodos en un arreglo.

Os muestro aquí un sencillo programa para manipular árboles binarios de búsqueda, tomado de aquí. ¿Podéis entender el código?¿Qué tiene de especial la subrutina search?

#!/usr/bin/perl -w
# bintree - binary tree demo program
use strict;
my($root, $n);

# first generate 20 random inserts
while ($n++ < 20) { insert($root, int(rand(1000)))}

# now dump out the tree all three ways
print "Pre order:  ";  pre_order($root);  print "\n";
print "In order:   ";  in_order($root);   print "\n";
print "Post order: ";  post_order($root); print "\n";

# prompt until EOF
for (print "Search? "; <>; print "Search? ") { 
    chomp;
    my $found = search($root, $_);
    if ($found) { print "Found $_ at $found, $found->{VALUE}\n" }
    else        { print "No $_ in tree\n" }
}

exit;

#########################################

# insert given value into proper point of
# provided tree.  If no tree provided, 
# use implicit pass by reference aspect of @_
# to fill one in for our caller.
sub insert {
    my($tree, $value) = @_;
    unless ($tree) {
        $tree = {};                         # allocate new node
        $tree->{VALUE}  = $value;
        $tree->{LEFT}   = undef;
        $tree->{RIGHT}  = undef;
        $_[0] = $tree;              # $_[0] is reference param!
        return;
    }
    if    ($tree->{VALUE} > $value) { insert($tree->{LEFT},  $value) }
    elsif ($tree->{VALUE} < $value) { insert($tree->{RIGHT}, $value) }
    else                            { warn "dup insert of $value\n"  }
                                    # XXX: no dups
}

# recurse on left child, 
# then show current value, 
# then recurse on right child.
sub in_order {
    my($tree) = @_;
    return unless $tree;
    in_order($tree->{LEFT});
    print $tree->{VALUE}, " ";
    in_order($tree->{RIGHT});
}

# show current value, 
# then recurse on left child, 
# then recurse on right child.
sub pre_order {
    my($tree) = @_;
    return unless $tree;
    print $tree->{VALUE}, " ";
    pre_order($tree->{LEFT});
    pre_order($tree->{RIGHT});
}

# recurse on left child, 
# then recurse on right child,
# then show current value. 
sub post_order {
    my($tree) = @_;
    return unless $tree;
    post_order($tree->{LEFT});
    post_order($tree->{RIGHT});
    print $tree->{VALUE}, " ";
}

# find out whether provided value is in the tree.
# if so, return the node at which the value was found.
# cut down search time by only looking in the correct
# branch, based on current value.
sub search {
    my($tree, $value) = @_;
    return unless $tree;
    if ($tree->{VALUE} == $value) {
        return $tree;
    }
    search($tree->{ ($value < $tree->{VALUE}) ? "LEFT" : "RIGHT"}, $value)
}