/
binary_tree_2.p6
85 lines (71 loc) · 1.65 KB
/
binary_tree_2.p6
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
use v6;
role BinaryTree[::Type] { }
role Node[::Type, \l, \r, \n] does BinaryTree[Type] {
has BinaryTree[Type] $.left = l;
has BinaryTree[Type] $.right = r;
has Type $.node = n;
}
role Tip[::Type] does BinaryTree[Type] {
}
sub mkNode ($T,$l,$r,$v) {
Node[$T,$l,$r,$v].new;
}
sub mkTip ($T) {
Tip[$T];
}
my BinaryTree[Int] $t1= Tip[Int];#[Int];
my BinaryTree[Int] $t2=
mkNode(Int,
mkNode(Int,
mkNode(Int,
Tip[Int],
Tip[Int],
22),
Tip[Int],
55),
mkNode(Int,
mkNode(Int,
Tip[Int],
Tip[Int],
33),
Tip[Int],
11),
44
);
say $t2;
multi sub new-from-list(::T,[]) {
Tip[Int].new
}
multi sub new-from-list(::T,\el) {
my \middle-index = el.elems div 2;
my \left = el[0 .. middle-index - 1];
my \middle = el[middle-index];
my \right = el[middle-index + 1 .. *];
Node[T,
new-from-list(T,left),
new-from-list(T,right),
middle
].new;
}
multi sub visit-preorder(Node \n,&cb) {
cb n.node;
for n.left, n.right -> \branch {
visit-preorder(branch,&cb);# if defined $branch;
}
}
multi sub visit-preorder(Tip,&cb) {
# cb T;
}
multi sub visit-postorder(Node \n,&cb) {
for n.left, n.right ->\branch {
visit-postorder(branch,&cb);# if defined $branch;
}
cb n.node;
}
multi sub visit-postorder(Tip,&cb) {
# cb T;
}
my BinaryTree[Int] \t = new-from-list(Int,[4, 5, 6]);
say t.raku;
visit-preorder(t,&say);
visit-postorder(t,&say);