...

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'