About

• binarytree

• depth first search

Code

假设有一二叉树，给出AB两个点，求AB的最短路径。
代码只是一个演示，可以寻找到达两个节点的路径

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);