Difference between revisions of "99 questions/Solutions/58"

From HaskellWiki
Jump to: navigation, search
 
(another solution)
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>

Revision as of 03:34, 25 August 2012

(**) 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