之前用struct实现的Tree不够灵活,重新使用hash来实现,更加灵活而且可以更改节点,进而实现平衡二叉树。
以下为程序代码:
use Data::Dumper;
my $tree = {};
add($tree,$_) for (5,7,1,4,9,6,100,20,30,21,60);
print Dumper $tree;
LMR($tree,$tree->{root});
RML($tree,$tree->{root});
sub add{
??? my ($tree,$value) = @_;
??? return if exists $tree->{$value};
?? ?
??? if (! exists $tree->{root}){
??????? $tree->{$value} = undef;
??????? $tree->{root} = $value;
??????? return
??? }
?? ?
??? my $tmp = $tree->{root};
??? while(defined $tmp){
??????? if ($value < $tmp){
??????????? if (exists $tree->{$tmp}->{left}){
??????????????? $tmp = $tree->{$tmp}->{left}
??????????? }
??????????? else{
??????????????? $tree->{$value} = undef;
??????????????? $tree->{$tmp}->{left} = $value;
??????????????? return
??????????? }
??????? }
??????? elsif($value > $tmp){
??????????? if (exists $tree->{$tmp}->{right}){
??????????????? $tmp = $tree->{$tmp}->{right}
??????????? }
??????????? else{
??????????????? $tree->{$value} = undef;
??????????????? $tree->{$tmp}->{right} = $value;
??????????????? return
??????????? }
??????? }
??? }
}
sub LMR{
??? my ($tree,$root) = @_;
?? ?
??? if (exists $tree->{$root}->{left}){
??????? LMR($tree,$tree->{$root}->{left})
??? }
??? print "$root ";
??? if (exists $tree->{$root}->{right}){
??????? LMR($tree,$tree->{$root}->{right})
??? }?????? ?
}
sub RML{
??? my ($tree,$root) = @_;
?? ?
??? if (exists $tree->{$root}->{right}){
??????? RML($tree,$tree->{$root}->{right})
??? }
??? print "$root ";
??? if (exists $tree->{$root}->{left}){
??????? RML($tree,$tree->{$root}->{left})
??? }
}