功能把一个GenTree到二叉树

鉴于以下数据结构，创建该给定GenTree的功能，把它变成BinTree：功能把一个GenTree到二叉树

每个为了NodeG在二叉树一个NodeB节点匹配;
NodeB的左边儿子匹配NodeG的第一个儿子;
的NodeB右子是如下NodeG（这意味着，为了NodeG的父母的童装之间的下一个节点）

视觉示例（GenTree左，BinTree右）

下一节点

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)

。我无法弄清楚如何使主函数的辅助函数（aux）工作。

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)

的最后一行代码是不工作，和一个我不明白

来源

2017-04-17 victor.ja

在我看来，你的问题有点不确定。 “GenTree”比“BinTree”更大，因为他们有更多的东西：NodeG有很多孩子，而NodeB只有两个孩子。当你遇到不适合NodeB的'NodeG'时，你的代码应该做什么？你需要想出一些扁平化策略 –

在问题的深入解释中增加了更多内容，并且提供了函数应该如何工作的可视化示例 –

我不知道应该把它返回，如果该节点是一个EmptyG，例如一个：

1 
/| \ 
E 2 3

我是这样做的aux (EmptyG:xs)= EmptyB但它没有多大意义。在这种情况下的问题是在a中放置什么值，所以您不会丢失树的其余部分（xs）。

反正这个代码工作的情况下，没有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)

从你的例子：

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

它产生：

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

其中，如果我没有在手工操作时搞乱了，是理想的结果。

来源

2017-04-17 19:09:04 moondaisy

功能把一个GenTree到二叉树

回答

相关问题