blob: 047f6caee395d17f3005cb8073dd0e2c93f2132f (
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
|
-- Ex1
data BTree a = Nil | Node a (BTree a) (BTree a)
deriving (Eq,Show,Read)
size :: BTree a -> Int
size Nil = 0
size (Node n bt1 bt2) = 1 + size bt1 + size bt2
cntheight :: BTree a -> Int
cntheight Nil = 0
cntheight (Node n bt1 bt2) = 1 + max (height bt1) (height bt2)
height :: BTree a -> Int
height bt = cntheight bt - 1
sumTree :: BTree Int -> Int
sumTree Nil = 0
sumTree (Node n bt1 bt2) = n + sumTree bt1 + sumTree bt2
sumLeaves :: BTree Int -> Int
sumLeaves Nil = 0
sumLeaves (Node n bt1 bt2)
| bt1 == Nil && bt2 == Nil = n
| otherwise = sumLeaves bt1 + sumLeaves bt2
inorder :: BTree a -> [a]
inorder Nil = []
inorder (Node n bt1 bt2) = inorder bt1 ++ [n] ++ inorder bt2
t1 :: BTree Int -- 5
t1 = Node 5 (Node 2 Nil -- / \
(Node 3 Nil Nil)) -- 2 6
(Node 6 Nil Nil) -- \
-- 3
t2 :: BTree Int -- 5
t2 = Node 5 (Node 3 Nil Nil) -- / \
(Node 4 (Node 5 Nil Nil) -- 3 4
(Node 7 Nil Nil)) -- / \
-- 5 7
-- Ex2
getLevel :: Int -> BTree a -> [a]
getLevel _ Nil = []
getLevel l (Node n bt1 bt2)
| l == 0 = [n]
| otherwise = getLevel (l - 1) bt1 ++ getLevel (l - 1) bt2
-- Ex3
avg :: [Int] -> Double
avg [] = 0
avg l = fromIntegral(sum l) / fromIntegral(length l)
average :: BTree Int -> Double
average bt = avg (inorder bt)
-- Ex4
mirrorTree :: BTree a -> BTree a
mirrorTree Nil = Nil
mirrorTree (Node n bt1 bt2) = (Node n (mirrorTree bt2) (mirrorTree bt1))
main :: IO()
main = do
print("t1: " ++ show (size t1) ++ " " ++ show (height t1) ++ " " ++ show(sumTree t1) ++ " " ++ show(sumLeaves t1) ++ " " ++ show(inorder t1))
print("t2: " ++ show (size t2) ++ " " ++ show (height t2) ++ " " ++ show(sumTree t2) ++ " " ++ show(sumLeaves t2) ++ " " ++ show(inorder t2))
print(show(getLevel 0 t1) ++ show(getLevel 1 t1) ++ show(getLevel 2 t1))
print(show(getLevel 0 t2) ++ show(getLevel 1 t2) ++ show(getLevel 2 t2))
print(average t1)
print(average t2)
print(inorder(mirrorTree t1))
print(inorder(mirrorTree t2))
|
