summaryrefslogtreecommitdiff
path: root/61-69
diff options
context:
space:
mode:
Diffstat (limited to '61-69')
-rw-r--r--61-69/61.hs7
-rw-r--r--61-69/61a.hs7
-rw-r--r--61-69/62.hs5
-rw-r--r--61-69/62a.hs9
-rw-r--r--61-69/63.hs27
-rw-r--r--61-69/64.hs10
-rw-r--r--61-69/65.hs16
7 files changed, 81 insertions, 0 deletions
diff --git a/61-69/61.hs b/61-69/61.hs
new file mode 100644
index 0000000..50bacae
--- /dev/null
+++ b/61-69/61.hs
@@ -0,0 +1,7 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+countLeaves :: Tree a -> Int
+
+countLeaves Empty = 0
+countLeaves (Branch _ Empty Empty) = 1
+countLeaves (Branch _ l r) = countLeaves l + countLeaves r
diff --git a/61-69/61a.hs b/61-69/61a.hs
new file mode 100644
index 0000000..c7c3662
--- /dev/null
+++ b/61-69/61a.hs
@@ -0,0 +1,7 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+leaves :: Tree a -> [a]
+
+leaves Empty = []
+leaves (Branch x Empty Empty) = [x]
+leaves (Branch _ l r) = leaves l ++ leaves r
diff --git a/61-69/62.hs b/61-69/62.hs
new file mode 100644
index 0000000..a1344c6
--- /dev/null
+++ b/61-69/62.hs
@@ -0,0 +1,5 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+internals Empty = []
+internals (Branch _ Empty Empty) = []
+internals (Branch x l r) = x:internals l ++ internals r
diff --git a/61-69/62a.hs b/61-69/62a.hs
new file mode 100644
index 0000000..a3a068b
--- /dev/null
+++ b/61-69/62a.hs
@@ -0,0 +1,9 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+atLevel :: Tree a -> Int -> [a]
+
+atLevel Empty _ = []
+atLevel (Branch x l r) n
+ | n == 1 = [x]
+ | n > 1 = atLevel l (n - 1) ++ atLevel r (n - 1)
+ | otherwise = []
diff --git a/61-69/63.hs b/61-69/63.hs
new file mode 100644
index 0000000..3227cea
--- /dev/null
+++ b/61-69/63.hs
@@ -0,0 +1,27 @@
+import Data.List (foldl')
+
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+completeBinaryTree :: Int -> Tree Char
+completeBinaryTree' :: Int -> Tree Char
+
+-- This one is very slow because it simulates adding n nodes one by one to form
+-- a complete binary tree. Although the time complexity is O(nlogn) for
+-- generating a tree of size n, the use of floating point operations still
+-- slows down the function a lot.
+
+completeBinaryTree n = foldl' (\acc m -> addNode acc m) Empty [0..n-1]
+ where addNode Empty _ = Branch 'x' Empty Empty
+ addNode (Branch x l r) m
+ | i >= ln = Branch x l $ addNode r (i - 1)
+ | otherwise = Branch x (addNode l (m - ln)) r
+ where lvl = floor $ logBase 2 $ fromIntegral $ m + 1
+ i = m - (2 ^ lvl - 1)
+ ln = 2 ^ (lvl - 1)
+
+-- This one just grows a heap of size n, which is exactly a complete binary
+-- tree, and the time complexity is O(n).
+completeBinaryTree' n = gen 1
+ where gen x
+ | x > n = Empty
+ | otherwise = Branch 'x' (gen $ x * 2) (gen $ x * 2 + 1)
diff --git a/61-69/64.hs b/61-69/64.hs
new file mode 100644
index 0000000..7b7aedd
--- /dev/null
+++ b/61-69/64.hs
@@ -0,0 +1,10 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+layout :: Tree Char -> Tree (Char, (Int, Int))
+
+layout t = fst $ draw t 1 1
+ where draw Empty x _ = (Empty, x)
+ draw (Branch v l r) x y =
+ (Branch (v, (x', y)) lt rt, x'')
+ where (lt, x') = draw l x (y + 1)
+ (rt, x'') = draw r (x' + 1) (y + 1)
diff --git a/61-69/65.hs b/61-69/65.hs
new file mode 100644
index 0000000..179b972
--- /dev/null
+++ b/61-69/65.hs
@@ -0,0 +1,16 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+layout :: Tree Char -> Tree (Char, (Int, Int))
+
+layout t = draw t (1 + 2 ^ (dep - 1) - 2 ^ (dep - ldep)) 1 (2 ^ (dep - 2))
+ where depth Empty = 0
+ depth (Branch _ l r) = 1 + max (depth l) (depth r)
+ ldepth Empty = 0
+ ldepth (Branch _ l _) = 1 + ldepth l
+ dep = depth t
+ ldep = ldepth t
+ draw Empty _ _ _ = Empty
+ draw (Branch v l r) x y h = Branch (v, (x, y)) lt rt
+ where h' = h `div` 2
+ lt = draw l (x - h) (y + 1) h'
+ rt = draw r (x + h) (y + 1) h'