perl实现二叉树

q986

　　最开始写的代码，每个结点用一个匿名哈希来表示，可惜运行时错误。。。代码如下



use strict ;
use warnings ;
sub create_tree {
    my $n8 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 8 ,
    } ;
    my $n6 = {
        'left' => undef ,
        'right' => \$n8 ,
        'value' => 6 ,
    };
    my $n5 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 5 ,
    };
    my $n7 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 7 ,
    };
    my $n2 = {
        'left' => \$n5 ,
        'right' => \$n6 ,
        'value' => 2 ,
    };
    my $n4 = {
        'left' => \$n7 ,
        'right' => undef ,
        'value' => 4 ,
    };
    my $n1 = {
        'left' => \$n2 ,
        'right' => \$n4 ,
        'value' => 1 ,
    };
    return $n1 ;
}
sub print_tree {
    my $root = shift ;
    if ($root) {
        print $root->{value}, "\n" ;
        if ($root->{left}) {
            &print_tree($root->{left}) ;
        }
        if($root->{right}) {
            &print_tree($root->{right}) ;
        }
    }
}
sub main {
    my $root = &create_tree() ;
    &print_tree($root) ;
}
&main() ;
1 ;
　　修改一下就可以了，因为$n8, $n6等本来就是引用，当他们作为其他结点的叶子结点时，不用再加\了，修改如下：



use strict ;
use warnings ;
sub create_tree {
    my $n8 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 8 ,
    } ;
    my $n6 = {
        'left' => undef ,
        'right' => $n8 ,
        'value' => 6 ,
    };
    my $n5 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 5 ,
    };
    my $n7 = {
        'left' => undef ,
        'right' => undef ,
        'value' => 7 ,
    };
    my $n2 = {
        'left' => $n5 ,
        'right' => $n6 ,
        'value' => 2 ,
    };
    my $n4 = {
        'left' => $n7 ,
        'right' => undef ,
        'value' => 4 ,
    };
    my $n1 = {
        'left' => $n2 ,
        'right' => $n4 ,
        'value' => 1 ,
    };
    return $n1 ;
}
sub print_tree {
    my $root = shift ;
    if ($root) {
        print $root->{value}, "\n" ;
        if ($root->{left}) {
            &print_tree($root->{left}) ;
        }
        if($root->{right}) {
            &print_tree($root->{right}) ;
        }
    }
}
sub main {
    my $root = &create_tree() ;
    &print_tree($root) ;
}
&main() ;
1
　　心血来潮，又试了另外一种方法，结点用实名哈希表示，当结点作为其他结点的子结点时，用引用表示，此法虽不简洁，但可运行



use strict ;
use warnings ;
sub create_tree {
    my %n8 = (
        'left' => undef ,
        'right' => undef ,
        'value' => 8 ,
    ) ;
    my %n6 = (
        'left' => undef ,
        'right' => \%n8 ,
        'value' => 6 ,
    );
    my %n5 = (
        'left' => undef ,
        'right' => undef ,
        'value' => 5 ,
    );
    my %n7 = (
        'left' => undef ,
        'right' => undef ,
        'value' => 7 ,
    );
    my %n2 = (
        'left' => \%n5 ,
        'right' => \%n6 ,
        'value' => 2 ,
    );
    my %n4 = (
        'left' => \%n7 ,
        'right' => undef ,
        'value' => 4 ,
    );
    my %n1 = (
        'left' => \%n2 ,
        'right' => \%n4 ,
        'value' => 1 ,
    );
    return \%n1 ;
}
sub print_tree {
    my $root = shift ;
    if ($root) {
        print $root->{value}, "\n" ;
        if ($root->{left}) {
            &print_tree($root->{left}) ;
        }
        if($root->{right}) {
            &print_tree($root->{right}) ;
        }
    }
}
sub main {
    my $root = &create_tree() ;
    &print_tree($root) ;
}
&main() ;
1
　　一时兴起，又试了一种方法，此法更简单，直接按树形构造哈希表。



use strict ;
use warnings ;
sub create_tree {
    my %root = (
        'left' => {
            'left' => {
                'left' => undef,
                'right' => undef,
                'value' => 5,
            },
            'right' => {
                'left' => undef,
                'right' => {
                    'left' => undef,
                    'right' => undef,
                    'value' => 8,
                },
                'value' => 6,
            },
            'value' => 2,
        },
        'right' => {
            'left' => {
                'left' => undef,
                'right' => undef,
                'value' => 7,
            },
            'right' => undef,
            'value' => 4,
        },
        'value' => 1,
    ) ;
    return \%root;
}
sub print_tree {
    my $root = shift ;
    if ($root) {
        print $root->{value}, "\n" ;
        &print_tree($root->{left}) ;
        &print_tree($root->{right}) ;
    }
}
sub main {
    my $root = &create_tree() ;
    &print_tree($root) ;
}
&main() ;
1
　　闲来无事，又写了一种方法：这应该是最好的方法了。



use strict ;
use warnings ;
sub node {
    my ($left, $right, $value) = @_ ;
    my $self = {
        'left' => $left,
        'right' => $right,
        'value' => $value,
    } ;
    return $self ;
}
sub create_tree {
    my $n8 = &node(undef, undef, 8) ;
    my $n6 = &node(undef, $n8, 6) ;
    my $n5 = &node(undef, undef, 5) ;
    my $n2 = &node($n5, $n6, 2) ;
    my $n7 = &node(undef, undef, 7) ;
    my $n4 = &node($n7, undef, 4) ;
    my $n1 = &node($n2, $n4, 1) ;
    return $n1;
}
sub print_tree {
    my $root = shift ;
    if ($root) {
        print $root->{value}, "\n" ;
        &print_tree($root->{left}) ;
        &print_tree($root->{right}) ;
    }
}
sub main {
    my $root = &create_tree() ;
    &print_tree($root) ;
}
&main() ;
1 ;
　　还有其他方法么？

　　== THE END ==