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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
use v6d;
###############################################################################
=begin comment
Perl Weekly Challenge 094, Task #2: Binary Tree to Linked List
=end comment
###############################################################################
#--------------------------------------#
# Copyright © 2021 PerlMonk Athanasius #
#--------------------------------------#
#==============================================================================
unit class BinaryTree;
#==============================================================================
#------------------------------------------------------------------------------
my class Node
#------------------------------------------------------------------------------
{
has Any $.value;
has Node $.parent is rw;
has Node $.left is rw;
has Node $.right is rw;
}
has Node $!root;
#------------------------------------------------------------------------------
submethod BUILD( Any:D :$value )
#------------------------------------------------------------------------------
{
$!root = Node.new( value => $value, parent => Nil,
left => Nil, right => Nil );
}
#------------------------------------------------------------------------------
method append-node( UInt:D $depth, UInt:D $sequence, Str:D $value --> Bool:D )
#------------------------------------------------------------------------------
{
my Node $parent = $!root;
my UInt $m = 2 ** $depth;
my UInt $seq = $sequence;
my UInt $level = $depth;
while $level > 1
{
$m = ($m / 2).Int;
if $seq < $m
{
$parent.left.defined or return False;
$parent = $parent.left;
}
else
{
$parent.right.defined or return False;
$parent = $parent.right;
$seq -= $m;
}
--$level;
}
my Node $new-node = Node.new( value => $value, parent => $parent,
left => Nil, right => Nil );
if $seq == 0
{
$parent.left = $new-node;
}
else
{
$parent.right = $new-node;
}
return True;
}
#------------------------------------------------------------------------------
method traverse-preorder( Callable:D $visit )
#------------------------------------------------------------------------------
{
if $!root.defined
{
preorder( $!root, $visit );
}
}
#------------------------------------------------------------------------------
sub preorder( Node:D $node, Callable:D $visit )
#------------------------------------------------------------------------------
{
$visit( $node.value );
preorder( $node.left, $visit ) if $node.left\.defined;
preorder( $node.right, $visit ) if $node.right.defined;
}
##############################################################################
|
