blob: 9616ad6c66e9cf2a0d4dae3ddf4199217939f3dd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#! /usr/bin/env raku
unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose), :g(:$graph));
my $sum = $tree.words.grep( * ~~ /\d/ ).sum;
say ": Sum: $sum" if $verbose;
class BinaryNode
{
has Numeric $.value is rw;
has BinaryNode $.left is rw;
has BinaryNode $.right is rw;
}
my @btree = $tree.split("|")>>.words;
my @old-nodes;
my @new-nodes;
for @btree.reverse -> $row
{
my @current = @$row;
@old-nodes = @new-nodes;
@new-nodes = ();
for @current -> $value
{
if $value eq "*"
{
@new-nodes.push("*");
next;
}
my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*";
my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*";
@new-nodes.push(BinaryNode.new(value => $value.Int,
left => $left // Nil,
right => $right // Nil));
}
}
my $btree = @new-nodes[0];
say ": { $btree.raku }\n" if $verbose;
traverse($btree);
say ": { $btree.raku }\n" if $verbose;
graph($btree) if $graph;
sub traverse ($current)
{
$current.value = $sum - $current.value;
traverse($current.left) if $current.left.defined;
traverse($current.right) if $current.right.defined;
}
sub graph ($graph)
{
say 'digraph foogrph {';
say ' node [shape = record,height=.1];';
do-it($graph);
say '}';
sub do-it ($current)
{
say " node{ $current.value }[label = \"<left> |<center> { $current.value }|<right> \"];";
if $current.left.defined
{
say " \"node{ $current.value }\":left -> \"node{ $current.left.value }\":center;";
do-it($current.left);
}
if $current.right.defined
{
say " \"node{ $current.value }\":right -> \"node{ $current.right.value }\":center;";
do-it($current.right);
}
}
}
|
