blob: 355fa6667cdeacb2e5751899b87e15ca6f004642 (
plain) (
blame)
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
|
-- Ex1
data BTree a = Nil | Node a (BTree a) (BTree a)
sumTree :: BTree Int -> Int
sumTree Nil = 0
sumTree (Node n bt1 bt2) = n + sumTree bt1 + sumTree bt2
instance Eq a => Eq (BTree a) where
Nil == Nil = True
(Node n1 bt11 bt12) == (Node n2 bt21 bt22) = (n1 == n2) && (bt11 == bt21) && (bt12 == bt22)
-- Ex2
getLevelsTree :: BTree a -> BTree (a,Int)
getLevelsTree bt = calc bt 0
where
calc Nil _ = Nil
calc (Node n bt1 bt2) l = (Node (n,l) (calc bt1 (l + 1)) (calc bt2 (l + 1)))
-- Ex3
mapTree :: (a -> b) -> BTree a -> BTree b
mapTree _ Nil = Nil
mapTree f (Node n bt1 bt2) = (Node (f n) (mapTree f bt1) (mapTree f bt2))
-- Ex4
data Color = Red | Green | Blue
deriving (Read, Show, Eq)
maxDepthBlueNode :: BTree Color -> Int
maxDepthBlueNode bt = calc 0 bt
where
calc _ Nil = 0
calc l (Node col bt1 bt2)
| col == Blue = max l $ max (calc (l+1) bt1) (calc (l+1) bt2)
| otherwise = max (calc (l+1) bt1) (calc (l+1) bt2)
-- Ex5
maxDepthNode :: BTree Color -> Color -> Int
maxDepthNode bt col = calc col 0 bt
where
calc _ _ Nil = 0
calc clr l (Node col bt1 bt2)
| col == clr = max l $ max (calc clr (l+1) bt1) (calc clr (l+1) bt2)
| otherwise = max (calc clr (l+1) bt1) (calc clr (l+1) bt2)
-- Ex6
data NTree a = NNil | NNode a [NTree a]
size :: NTree a -> Int
size NNil = 0
size (NNode e ch) = foldr (\el acc -> acc + size el) 1 ch
-- Ex7
l1 NNil _ = 0
l1 (NNode elem _) e = abs (elem - e)
isGracious :: NTree Int -> Bool
isGracious NNil = True
isGracious (NNode e ch) = all even (map (\n -> l1 n e) ch) && all isGracious ch
-- main
inorder :: BTree a -> [a]
inorder Nil = []
inorder (Node n bt1 bt2) = inorder bt1 ++ [n] ++ inorder bt2
t1 :: BTree Int -- 1
t1 = Node 1 (Node 2 (Node 5 Nil Nil) -- / \
Nil) -- 2 3
(Node 3 (Node 7 Nil Nil) -- / / \
(Node 6 Nil Nil)) -- 5 7 6
colorTree :: BTree Color -- Blue
colorTree = Node Blue (Node Red (Node Green Nil Nil) Nil) -- / \
(Node Red (Node Blue (Node Green Nil Nil) -- Red Red
(Node Red Nil Nil)) -- / /
Nil) -- Green Blue
-- / \
-- Green Red
nTree1 :: NTree Int -- 1
nTree1 = NNode 1 [(NNode 2 [(NNode 3 [NNil]), -- / \
(NNode 4 [NNil]), -- 2 6
(NNode 5 [NNil])]), -- /|\ |
(NNode 6 [(NNode 7 [NNil])])] -- 3 4 5 7
nTree2 :: NTree Int -- 0
nTree2 = NNode 0 [(NNode 6 [NNil]), -- / \
(NNode 4 [(NNode 8 [NNil]), -- 6 4
(NNode 2 [NNil]), -- /|\
(NNode 12 [NNil])])] -- 8 2 12
main :: IO()
main = do
print(show(sumTree t1) ++ show(t1 == t1))
print(inorder(getLevelsTree t1))
print(inorder(mapTree (show) t1))
print(maxDepthBlueNode colorTree)
print(maxDepthNode colorTree Red)
print(size nTree1)
print(show(isGracious nTree1) ++ " " ++ show(isGracious nTree2))
|
