Difference between revisions of "99 questions/61 to 69"
(Added solution to 67A.) |
(Added solution to P-68.) |
||
| Line 424: | Line 424: | ||
== Problem 68 == |
== Problem 68 == |
||
| + | Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67. |
||
| − | <Problem description> |
||
| + | a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67. |
||
| ⚫ | |||
| + | |||
| − | Example: |
||
| + | b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements. |
||
| − | <example in lisp> |
||
| + | |||
| + | c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job. |
||
Example in Haskell: |
Example in Haskell: |
||
| ⚫ | |||
| − | <example in Haskell> |
||
| + | Main> let { Just t = stringToTree "a(b(d,e),c(,f(g,)))" ; |
||
| + | po = treeToPreorder t ; |
||
| + | io = treeToInorder t } in preInTree po io >>= print |
||
| + | Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty)) |
||
</pre> |
</pre> |
||
Solution: |
Solution: |
||
<haskell> |
<haskell> |
||
| + | treeToPreorder :: Tree Char -> String |
||
| ⚫ | |||
| + | treeToPreorder = preorder |
||
| − | </haskell> |
||
| + | where preorder Empty = "" |
||
| + | preorder (Branch x l r) = x : preorder l ++ preorder r |
||
| + | |||
| − | <description of implementation> |
||
| + | treeToInorder :: Tree Char -> String |
||
| + | treeToInorder = inorder |
||
| + | where inorder Empty = "" |
||
| + | inorder (Branch x l r) = inorder l ++ x : inorder r |
||
| + | |||
| + | -- Given a preorder string produce a binary tree such that its preorder string |
||
| + | -- is identical to the given one. |
||
| + | preToTree :: String -> Tree Char |
||
| + | preToTree "" = Empty |
||
| + | preToTree (c:cs) = Branch c Empty (preorderToTree cs) |
||
| + | |||
| + | -- Given a preorder and an inorder string with unique node chars produce the |
||
| + | -- corresponding binary tree. |
||
| + | preInTree :: Monad m => String -> String -> m (Tree Char) |
||
| + | preInTree = build |
||
| + | where build [] [] = return Empty |
||
| + | build po@(x:xs) io = do (lio,_:rio) <- return $ break (== x) io |
||
| + | (lpo,rpo) <- return $ splitAt (length lio) xs |
||
| + | l <- build lpo lio |
||
| + | r <- build rpo rio |
||
| + | return $ Branch x l r |
||
| + | build _ _ = fail "woops" |
||
| ⚫ | |||
== Problem 69 == |
== Problem 69 == |
||
Revision as of 09:51, 14 January 2007
This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.
If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.
Binary trees
As defined in problem 54A.
An example tree:
tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty))
(Branch 2 Empty Empty)
Problem 61
Count the leaves of a binary tree
A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.
Example: % count_leaves(T,N) :- the binary tree T has N leaves Example in Haskell: > count_leaves tree4 2
Solution:
count_leaves Empty = 0
count_leaves (Branch a Empty Empty) = 1
count_leaves (Branch a left right) = count_leaves left + count_leaves right
Problem 61A
Collect the leaves of a binary tree in a list
A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list.
Example: % leaves(T,S) :- S is the list of all leaves of the binary tree T Example in Haskell: > leaves tree4 [4, 2]
Solution:
leaves :: Tree a -> [a]
leaves Empty = []
leaves (Branch a Empty Empty) = [a]
leaves (Branch a left right) = leaves left ++ leaves right
Problem 62
Collect the internal nodes of a binary tree in a list An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.
Example: % internals(T,S) :- S is the list of internal nodes of the binary tree T. Example in Haskell: Prelude>internals tree4 Prelude>[1,2]
Solution:
internals :: Tree a -> [a]
internals Empty = []
internals (Branch a Empty Empty) = []
internals (Branch a left right) = [a] ++ (internals left) ++ (internals right)
Problem 62B
Collect the nodes at a given level in a list A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.
Example: % atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L Example in Haskell: Prelude>atlevel tree4 2 Prelude>[2,2]
Solution:
atlevel :: Tree a -> Int -> [a]
atlevel t level = loop t 1
where
loop Empty _ = []
loop (Branch a l r) n
| n == level = [a]
| otherwise = loop l (n+1) ++ loop r (n+1)
Another possibility is to decompose the problem:
levels :: Tree a -> [[a]]
levels Empty = repeat []
levels (Branch a l r) = [a] : zipWith (++) (levels l) (levels r)
atlevel :: Tree a -> Int -> [a]
atlevel t n = levels t !! (n-1)
Problem 63
Construct a complete binary tree
A complete binary tree with height H is defined as follows:
- The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i)
- In level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil's which are not really nodes!) come last.
Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.
We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node X with address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.
Write a predicate complete_binary_tree/2.
Example: % complete_binary_tree(N,T) :- T is a complete binary tree with N nodes. Example in Haskell: Main> complete_binary_tree 4 Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty Empty) Main> is_complete_binary_tree $ Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty) True
Solution:
import Data.List
data Tree a = Empty | Branch a (Tree a) (Tree a)
deriving (Show, Eq)
filled :: Tree a -> [[Bool]]
filled Empty = repeat [False]
filled (Branch _ l r) = [True] : zipWith (++) (filled l) (filled r)
complete_binary_tree :: Int -> Tree Char
complete_binary_tree n = generate_tree 1
where generate_tree x
| x > n = Empty
| otherwise = Branch 'x' (generate_tree (2*x) )
(generate_tree (2*x+1))
is_complete_binary_tree :: Tree a -> Bool
is_complete_binary_tree Empty = True
is_complete_binary_tree t = and $ last_proper : zipWith (==) lengths powers
where levels = takeWhile or $ filled t
-- The upper levels of the tree should be filled.
-- Every level has twice the number of nodes as the one above it,
-- so [1,2,4,8,16,...]
lengths = map (length . filter id) $ init levels
powers = iterate (2*) 1
-- The last level should contain a number of filled spots,
-- and (maybe) some empty spots, but no filled spots after that!
last_filled = map head $ group $ last levels
last_proper = head last_filled && (length last_filled) < 3
Alternative solution which constructs complete binary trees from a given list using local recursion (also includes a lookup function as per the Prolog solution):
completeBinaryTree :: Int -> a -> Tree a
completeBinaryTree n = cbtFromList . replicate n
cbtFromList :: [a] -> Tree a
cbtFromList xs = let (t, xss) = cbt (xs:xss) in t
where cbt ((x:xs):xss) =
let (l, xss') = cbt xss
(r, xss'') = cbt xss'
in (Branch x l r, xs:xss'')
cbt _ = (Empty, [])
lookupIndex :: Tree a -> Integer -> a
lookupIndex t = lookup t . path
where lookup Empty _ = error "index to large"
lookup (Branch x _ _) [] = x
lookup (Branch x l r) (p:ps) = lookup (if even p then l else r) ps
path = reverse . takeWhile (>1) . iterate (`div` 2) . (1+)
Problem 64
Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:
In this layout strategy, the position of a node v is obtained by the following two rules:
- x(v) is equal to the position of the node v in the inorder sequence
- y(v) is equal to the depth of the node v in the tree
Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.
Here is the example tree from the above illustration:
tree64 = Branch 'n'
(Branch 'k'
(Branch 'c'
(Branch 'a' Empty Empty)
(Branch 'h'
(Branch 'g'
(Branch 'e' Empty Empty)
Empty
)
Empty
)
)
(Branch 'm' Empty Empty)
)
(Branch 'u'
(Branch 'p'
Empty
(Branch 's'
(Branch 'q' Empty Empty)
Empty
)
)
Empty
)
Example in Haskell:
> layout tree64
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...
Solution:
type Pos = (Int, Int)
layout :: Tree a -> Tree (a, Pos)
layout t = fst (layoutAux 1 1 t)
where layoutAux x y Empty = (Empty, x)
layoutAux x y (Branch a l r) = (Branch (a, (x',y)) l' r', x'')
where (l', x') = layoutAux x (y+1) l
(r', x'') = layoutAux (x'+1) (y+1) r
The auxiliary function is passed the x-coordinate for the left-most node of the subtree, the y-coordinate for the root of the subtree, and the subtree itself. It returns the subtree annotated with positions, plus the count of Branch nodes in the subtree.
Problem 65
An alternative layout method is depicted in the illustration below:
Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant.
Use the same conventions as in problem P64 and test your function in an appropriate way.
Here is the example tree from the above illustration:
tree65 = Branch 'n'
(Branch 'k'
(Branch 'c'
(Branch 'a' Empty Empty)
(Branch 'e'
(Branch 'd' Empty Empty)
(Branch 'g' Empty Empty)
)
)
(Branch 'm' Empty Empty)
)
(Branch 'u'
(Branch 'p'
Empty
(Branch 'q' Empty Empty)
)
Empty
)
Example in Haskell:
> layout tree65
Branch ('n',(15,1)) (Branch ('k',(7,2)) (Branch ('c',(3,3)) ...
Solution:
layout :: Tree a -> Tree (a, Pos)
layout t = layoutAux x1 1 sep1 t
where d = depth t
ld = leftdepth t
x1 = 2^(d-1) - 2^(d-ld) + 1
sep1 = 2^(d-2)
layoutAux x y sep Empty = Empty
layoutAux x y sep (Branch a l r) =
Branch (a, (x,y))
(layoutAux (x-sep) (y+1) (sep `div` 2) l)
(layoutAux (x+sep) (y+1) (sep `div` 2) r)
depth :: Tree a -> Int
depth Empty = 0
depth (Branch a l r) = max (depth l) (depth r) + 1
leftdepth :: Tree a -> Int
leftdepth Empty = 0
leftdepth (Branch a l r) = leftdepth l + 1
The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself. It returns the subtree annotated with positions.
Problem 66
Yet another layout strategy is shown in the illustration below:
The method yields a very compact layout while maintaining a certain symmetry in every node. Find out the rules and write the corresponding Prolog predicate. Hint: Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree?
Use the same conventions as in problem P64 and P65 and test your predicate in an appropriate way. Note: This is a difficult problem. Don't give up too early!
Which layout do you like most?
Example in Haskell:
> layout tree65
Branch ('n',(5,1)) (Branch ('k',(3,2)) (Branch ('c',(2,3)) ...
Solution:
layout :: Tree a -> Tree (a, Pos)
layout t = t'
where (l, t', r) = layoutAux x1 1 t
x1 = maximum l + 1
layoutAux :: Int -> Int -> Tree a -> ([Int], Tree (a, Pos), [Int])
layoutAux x y Empty = ([], Empty, [])
layoutAux x y (Branch a l r) = (ll', Branch (a, (x,y)) l' r', rr')
where (ll, l', lr) = layoutAux (x-sep) (y+1) l
(rl, r', rr) = layoutAux (x+sep) (y+1) r
sep = maximum (0:zipWith (+) lr rl) `div` 2 + 1
ll' = 0 : overlay (map (+sep) ll) (map (subtract sep) rl)
rr' = 0 : overlay (map (+sep) rr) (map (subtract sep) lr)
-- overlay xs ys = xs padded out to at least the length of ys
-- using any extra elements of ys
overlay :: [a] -> [a] -> [a]
overlay [] ys = ys
overlay xs [] = xs
overlay (x:xs) (y:ys) = x : overlay xs ys
The auxiliary function is passed the x- and y-coordinates for the root of the subtree and the subtree itself. It returns
- a list of distances the laid-out tree extends to the left at each level,
- the subtree annotated with positions, and
- a list of distances the laid-out tree extends to the right at each level.
These distances are usually positive, but may be 0 or negative in the case of a skewed tree. To put two subtrees side by side, we must determine the least even separation so that they do not overlap on any level. Having determined the separation, we can compute the extents of the composite tree.
The definitions of layout and its auxiliary function use local recursion to compute the x-coordinates. This works because nothing else depends on these coordinates.
Problem 67A
A string representation of binary trees
Somebody represents binary trees as strings of the following type:
- a(b(d,e),c(,f(g,)))
a) Write a Prolog predicate which generates this string representation, if the tree is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse; i.e. given the string representation, construct the tree in the usual form. Finally, combine the two predicates in a single predicate tree_string/2 which can be used in both directions.
Example in Prolog
?- tree_to_string(t(x,t(y,nil,nil),t(a,nil,t(b,nil,nil))),S).
S = 'x(y,a(,b))'
?- string_to_tree('x(y,a(,b))',T).
T = t(x, t(y, nil, nil), t(a, nil, t(b, nil, nil)))
Example in Haskell:
Main> stringToTree "x(y,a(,b))" >>= print Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty)) Main> let t = cbtFromList ['a'..'z'] in stringToTree (treeToString t) >>= print . (== t) True
Solution:
treeToString :: Tree Char -> String
treeToString Empty = ""
treeToString (Branch x Empty Empty) = [x]
treeToString (Branch x l r) =
x : '(' : treeToString l ++ "," ++ treeToString r ++ ")"
stringToTree :: (Monad m) => String -> m (Tree Char)
stringToTree "" = return Empty
stringToTree [x] = return $ Branch x Empty Empty
stringToTree str = tfs str >>= \ ("", t) -> return t
where tfs a@(x:xs) | x == ',' || x == ')' = return (a, Empty)
tfs (x:y:xs)
| y == ',' || y == ')' = return (y:xs, Branch x Empty Empty)
| y == '(' = do (',':xs', l) <- tfs xs
(')':xs'', r) <- tfs xs'
return $ (xs'', Branch x l r)
tfs _ = fail "bad parse"
Note that the function stringToTree works in any Monad.
Problem 68
Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67.
a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67.
b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.
c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.
Example in Haskell:
Main> let { Just t = stringToTree "a(b(d,e),c(,f(g,)))" ;
po = treeToPreorder t ;
io = treeToInorder t } in preInTree po io >>= print
Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))
Solution:
treeToPreorder :: Tree Char -> String
treeToPreorder = preorder
where preorder Empty = ""
preorder (Branch x l r) = x : preorder l ++ preorder r
treeToInorder :: Tree Char -> String
treeToInorder = inorder
where inorder Empty = ""
inorder (Branch x l r) = inorder l ++ x : inorder r
-- Given a preorder string produce a binary tree such that its preorder string
-- is identical to the given one.
preToTree :: String -> Tree Char
preToTree "" = Empty
preToTree (c:cs) = Branch c Empty (preorderToTree cs)
-- Given a preorder and an inorder string with unique node chars produce the
-- corresponding binary tree.
preInTree :: Monad m => String -> String -> m (Tree Char)
preInTree = build
where build [] [] = return Empty
build po@(x:xs) io = do (lio,_:rio) <- return $ break (== x) io
(lpo,rpo) <- return $ splitAt (length lio) xs
l <- build lpo lio
r <- build rpo rio
return $ Branch x l r
build _ _ = fail "woops"
Problem 69
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>