role BinaryTree[::Type] {
has Type $.node;
has BinaryTree[Type] $.lchild;
has BinaryTree[Type] $.rchild;
method create(::?CLASS::U: *@list) {
my $middle = @list.elems div 2;
my @lchilds = @list[0 .. $middle - 1];
my $midchild = @list[$middle];
my @rchilds = @list[$middle + 1 .. * - 1];
self.bless(
node => $midchild,lchild => @lchilds ?? self.create(@lchilds) !! $?CLASS,rchild => @rchilds ?? self.create(@rchilds) !! $?CLASS,);
}
method preorder(&callback) {
callback $!node;
for $!rchild,$!lchild -> $child {
$child.preorder(&callback) if $child.defined;
}
}
}
`(
4
3 2
1 6 5 8
)
my $tree = BinaryTree[Int].create(1,3,6,4,5,2,8);
my $a = 5; # 要寻找的a的值
my $b = 8; # 要寻找的b的值
my $ab; # 是否找到a
my $bb; # 是否找到b
my @adistance; # 路径记录
my @bdistance; # 路径记录
my $print = -> array { for array { print " " ~ .node; }; say ""; };
sub dinstance-search($tree){
return if ?$ab && ?$bb;
if $tree.rchild.defined {
@adistance.push: $tree unless ?$ab;
@bdistance.push: $tree unless ?$bb;
dinstance-search($tree.rchild);
}
if $tree.lchild.defined {
@adistance.push: $tree unless ?$ab;
@bdistance.push: $tree unless ?$bb;
dinstance-search($tree.lchild);
}
{
say "access tree node: " ~ $tree.node;
#$print(@adistance);
if !?$ab {
if $a eq $tree.node {
$ab = True;
return;
}
@adistance.pop;
}
if !?$bb {
if $b eq $tree.node {
$bb = True;
return;
}
@bdistance.pop;
}
}
}
dinstance-search($tree);
say "a ---> ";
$print(@adistance);
say "b ---> ";
$print(@bdistance);
