Problem 69: Dotstring representation of binary trees.
The first part of the problem is straightforward preorder traversal:
tree2ds :: Tree Char -> String
tree2ds Empty = "."
tree2ds (Branch v l r) = v : tree2ds l ++ tree2ds r
For the second part, constructing a tree from a preorder sequence is unambiguous. Why? Didn’t problem 68 ask us to construct a tree with the same preorder sequence as the given, and why didn’t it state clearly to construct the same tree? As an exercise, prove that the dotstring representation can help us construct the same tree, a stricter problem statement than “all trees with the same preorder sequence”.
ds2tree :: String -> (Tree Char, String)
ds2tree "" = (Empty, "")
ds2tree ( c : cs )
| c == '.' = (Empty, cs)
| otherwise = (Branch c l r, rrest)
where (l, lrest) = ds2tree cs
(r, rrest) = ds2tree lrest
Problem 70: Count the nodes of a multiway tree.
Oooh, multiway trees, neat!
nnodes :: Tree a -> Int
nnodes (Node _ ts) = 1 + sum ( map nnodes ts )
and to construct a multiway tree from a node string, & vice versa:
tree_to_string :: Tree Char -> String
tree_to_string (Node v ts) = v : concatMap tree_to_string ts ++ "^"
-- Little helper to grab a range [m, n) from a sequence:
take_range str m n = take (n - m) $ drop m str
string_to_tree :: String -> Tree Char
string_to_tree ( c : '^' : cs) = Node c []
string_to_tree ( c : cs) = Node c ns
where
-- The indices in `levels` where zeroes appear:
zeroes = map fst $ filter ((==) 0 . snd) $ zip [0,1..] levels
-- `levels` is numbering the level we're on after 'processing' each node
-- in the string, with -1 signifying the end (above the root):
levels = scanl (+) 0 $ map (\v -> if v == '^' then -1 else 1) cs
-- Think of `ns` as leaves we need to hang:
ns = map (string_to_tree . uncurry (take_range cs)) $ zip (init zeroes) (tail zeroes)
Problem 71: Determine the internal path length of a tree.
Not too hard, after all:
ipl :: Tree a -> Int
ipl = ipl' 0
where ipl' d (Node _ ts) = d + sum ( map (ipl' (d+1) ) ts)
Problem 72: Construct the bottom-up order sequence of the tree nodes.
Problem description looks like a DFS where children nodes are grouped, so that’s exactly what we’ll do:
bottom_up :: Tree a -> [a]
bottom_up (Node v ts) = concatMap bottom_up ts ++ [v]
We’ll leave problem 73 for the next time. Cheerio!
« Past Future »