-
Notifications
You must be signed in to change notification settings - Fork 320
/
ch-2.pl
122 lines (103 loc) · 2.5 KB
/
ch-2.pl
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
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };
my %node;
for my $i (
qw{
1/1 1/2 2/1
1/3 3/2 2/3
3/1 1/4 4/3
3/5 5/2 2/5
5/3 3/4 4/1
}
)
{
$node{$i} = Node->new($i);
}
$node{'1/1'}->left( $node{'1/2'} ); # 1
$node{'1/1'}->right( $node{'2/1'} ); # 1
$node{'1/2'}->left( $node{'1/3'} ); # 2
$node{'1/2'}->right( $node{'3/2'} ); # 2
$node{'1/3'}->left( $node{'1/4'} ); # 3
$node{'1/3'}->right( $node{'4/3'} ); # 3
$node{'2/1'}->left( $node{'2/3'} ); # 2
$node{'2/1'}->right( $node{'3/1'} ); # 2
$node{'2/3'}->left( $node{'2/5'} ); # 3
$node{'2/3'}->right( $node{'5/3'} ); # 3
$node{'3/1'}->left( $node{'3/4'} ); # 3
$node{'3/1'}->right( $node{'4/1'} ); # 3
$node{'3/2'}->left( $node{'3/5'} ); # 3
$node{'3/2'}->right( $node{'5/2'} ); # 3
for my $n ( sort keys %node ) {
my $node = $node{$n};
my $parent = '';
my $grandparent = '';
if ( defined $node->parent ) {
$parent = $node->parent->value;
if ( defined $node->parent->parent ) {
$grandparent = $node->parent->parent->value;
}
}
say <<"END";
INPUT: \$member = "$n"
OUTPUT: parent = "$parent" and grandparent = "$grandparent"
END
}
package Node;
sub new ( $class, $value = 0 ) {
my $self = {};
$self->{value} = $value;
$self->{left} = undef;
$self->{right} = undef;
$self->{horizontal} = undef;
$self->{parent} = undef;
return bless $self, $class;
}
sub value ( $self, $value = undef ) {
if ( defined $value ) {
$self->{value} = $value;
}
else {
return $self->{value};
}
}
sub is_root ( $self ) {
return defined $self->{parent} ? 0 : 1;
}
sub is_leaf ( $self ) {
return ( !defined $self->{left} && !defined $self->{right} )
? 1
: 0;
}
sub left ( $self, $node = undef ) {
if ( defined $node ) {
$self->{left} = $node;
$node->{parent} = $self;
}
else {
return $self->{left};
}
}
sub right ( $self, $node = undef ) {
if ( defined $node ) {
$self->{right} = $node;
$node->{parent} = $self;
}
else {
return $self->{right};
}
}
sub horizontal ( $self, $node = undef ) {
if ( defined $node ) {
$self->{horizontal} = $node;
$node->{parent} = $self;
}
else {
return $self->{horizontal};
}
}
sub parent ($self ) {
return $self->{parent};
}