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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
package BinaryTree;
use strict;
use warnings;
use metaclass;
our $VERSION = '0.02';
BinaryTree->meta->add_attribute('$:uid' => (
reader => 'getUID',
writer => 'setUID',
default => sub {
my $instance = shift;
("$instance" =~ /\((.*?)\)$/);
}
));
BinaryTree->meta->add_attribute('$:node' => (
reader => 'getNodeValue',
writer => 'setNodeValue',
init_arg => ':node'
));
BinaryTree->meta->add_attribute('$:parent' => (
predicate => 'hasParent',
reader => 'getParent',
writer => 'setParent'
));
BinaryTree->meta->add_attribute('$:left' => (
predicate => 'hasLeft',
reader => 'getLeft',
writer => {
'setLeft' => sub {
my ($self, $tree) = @_;
$tree->setParent($self) if defined $tree;
$self->{'$:left'} = $tree;
$self;
}
},
));
BinaryTree->meta->add_attribute('$:right' => (
predicate => 'hasRight',
reader => 'getRight',
writer => {
'setRight' => sub {
my ($self, $tree) = @_;
$tree->setParent($self) if defined $tree;
$self->{'$:right'} = $tree;
$self;
}
}
));
sub new {
my $class = shift;
$class->meta->new_object(':node' => shift);
}
sub removeLeft {
my ($self) = @_;
my $left = $self->getLeft();
$left->setParent(undef);
$self->setLeft(undef);
return $left;
}
sub removeRight {
my ($self) = @_;
my $right = $self->getRight;
$right->setParent(undef);
$self->setRight(undef);
return $right;
}
sub isLeaf {
my ($self) = @_;
return (!$self->hasLeft && !$self->hasRight);
}
sub isRoot {
my ($self) = @_;
return !$self->hasParent;
}
sub traverse {
my ($self, $func) = @_;
$func->($self);
$self->getLeft->traverse($func) if $self->hasLeft;
$self->getRight->traverse($func) if $self->hasRight;
}
sub mirror {
my ($self) = @_;
# swap left for right
my $left = $self->getLeft;
$self->setLeft($self->getRight());
$self->setRight($left);
# and recurse
$self->getLeft->mirror() if $self->hasLeft();
$self->getRight->mirror() if $self->hasRight();
$self;
}
sub size {
my ($self) = @_;
my $size = 1;
$size += $self->getLeft->size() if $self->hasLeft();
$size += $self->getRight->size() if $self->hasRight();
return $size;
}
sub height {
my ($self) = @_;
my ($left_height, $right_height) = (0, 0);
$left_height = $self->getLeft->height() if $self->hasLeft();
$right_height = $self->getRight->height() if $self->hasRight();
return 1 + (($left_height > $right_height) ? $left_height : $right_height);
}
1;
|
