Difference between revisions of "99 questions/Solutions/58"
< 99 questions | Solutions
Jump to navigation
Jump to search
(categorize) |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 2: | Line 2: | ||
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes. |
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes. |
||
+ | |||
+ | An efficient solution, which takes the fact that a tree with an even number of nodes can't be symmetric into consideration: |
||
+ | |||
+ | <haskell> |
||
+ | symCbalTrees n = if n `mod` 2 == 0 then [] else |
||
+ | [ Branch 'x' t (reverseTree t) | t <- cbalTree (n `div` 2)] |
||
+ | |||
+ | reverseTree Empty = Empty |
||
+ | reverseTree (Branch x l r) = Branch x (reverseTree r) (reverseTree l) |
||
+ | </haskell> |
||
+ | |||
+ | Or a simple, but less efficient one: |
||
<haskell> |
<haskell> |
||
symCbalTrees = filter symmetric . cbalTree |
symCbalTrees = filter symmetric . cbalTree |
||
</haskell> |
</haskell> |
||
+ | |||
+ | |||
+ | [[Category:Programming exercise spoilers]] |
Latest revision as of 13:37, 25 December 2016
(**) Generate-and-test paradigm
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
An efficient solution, which takes the fact that a tree with an even number of nodes can't be symmetric into consideration:
symCbalTrees n = if n `mod` 2 == 0 then [] else
[ Branch 'x' t (reverseTree t) | t <- cbalTree (n `div` 2)]
reverseTree Empty = Empty
reverseTree (Branch x l r) = Branch x (reverseTree r) (reverseTree l)
Or a simple, but less efficient one:
symCbalTrees = filter symmetric . cbalTree