Breadth first numbering

gistfile1.hs

data Tree a         = EndNode  | Leaf | Node a (Tree a) (Tree a)
data FlatTree       = FlatLeaf | FlatNode                        deriving (Show)
data NumberedTree a = NumLeaf  | NumNode Integer                 deriving (Show)

instance (Show a) => Show (Tree a) where
  show = showTreeIndented 0
    where showTreeIndented indentation Leaf                    = concat (take indentation $ repeat "  ") ++ "[]\n"
          showTreeIndented indentation (Node value left right) = concat (take indentation $ repeat "  ") ++ (show value) ++ "\n" ++ showTreeIndented (indentation + 1) left ++ showTreeIndented (indentation + 1) right


tree = Node "a"
        (Node "b"
          Leaf
          (Node "c"
            Leaf
            Leaf))
        (Node "d"
          (Node "e"
            Leaf
            Leaf)
          Leaf)

treeToList []                         = []
treeToList (EndNode:rest)             = FlatLeaf : treeToList rest
treeToList (Leaf:rest)                = FlatLeaf : treeToList (rest ++ [EndNode, EndNode])
treeToList (Node _ left right : rest) = FlatNode : treeToList (rest ++ [left, right])

numberList _          []              = []
numberList nextNumber (FlatLeaf:rest) = NumLeaf : numberList nextNumber rest
numberList nextNumber (FlatNode:rest) = NumNode nextNumber : numberList (nextNumber + 1) rest

numberListToTree index nodes = case nodes !! index of
                                 NumLeaf   -> Leaf
                                 NumNode a -> Node a (numberListToTree leftChildIndex nodes) (numberListToTree rightChildIndex nodes)
                                 where leftChildIndex  = index * 2 + 1
                                       rightChildIndex = index * 2 + 2

numberTree = numberListToTree 0 . numberList 1 . treeToList . (: [])

main = do
  print tree
  print $ numberTree tree