CODEWITHSUNDEEP
algorithmhaskell
victor.ja
victor.ja

Reputation: 888

Function to turn a GenTree to a Binary Tree

Given the following data structures, create a function which given a GenTree, turns it into a BinTree:

Visual example ( GenTree left, BinTree right)

    1                       1
/ |  |  \                  / \
2 3  4   5                2   E  
    /|\                  / \
   6 7 8                E   3
                           / \
                          E   4
                             / \
                            6   5
                           / \
                          E   7
                             / \
                            E   8  

data GenTree a = EmptyG | NodeG a [GenTree a]
                                         deriving (Show)

data BinTree a = EmptyB | NodeB (BinTree a) a (BinTree a)
                                                     deriving (Show)

. I can't figure out how to make the helper function (aux) of the main function work.

g2b :: (GenTree a) -> (BinTree a)

g2b EmptyG = EmptyB
g2b (NodeG x ts) = NodeB (aux ts) x EmptyB

aux :: [GenTree a] -> (BinTree a)

aux [] = EmptyB
aux (NodeG x xs) : xss = NodeB (aux xs) x (aux xss) ((NodeG x xs) xss)

The last line of code is the one that doesn't work and the one I can't understand

Upvotes: 2

Views: 160

Answers (1)

moondaisy
moondaisy

Reputation: 4491

I'm not sure what should it return if the node is an EmptyG, for example:

   1
 / | \
E  2  3

I did it like this aux (EmptyG:xs)= EmptyB but it doesn't make much sense. The problem in this case is what value to put in a so you don't lose the rest of the tree (xs).

Anyway this code works for the cases with no EmptyG:

aux :: [GenTree a] -> (BinTree a)
aux [] = EmptyB
aux (EmptyG:xs)= EmptyB  
aux ((NodeG x []):xs) = NodeB (EmptyB) x (aux xs)
aux ((NodeG x ys):xs) = NodeB (aux ys) x (aux xs)

From your example:

(NodeG 1 [NodeG 2 [], NodeG 3 [], NodeG 4 [NodeG 6 [], NodeG 7 [], NodeG 8 []], NodeG 5[]])

It produces:

NodeB (NodeB EmptyB 2 (NodeB EmptyB 3 (NodeB (NodeB EmptyB 6 (NodeB EmptyB 7 (NodeB EmptyB 8 EmptyB))) 4 (NodeB EmptyB 5 EmptyB)))) 1 EmptyB

Which, if I didn't mess up while doing it by hand, is the desired outcome.

Upvotes: 3

Related Questions