algorithm - 将 GenTree 转换为二叉树的函数

Question

给定以下数据结构，创建一个给定 GenTree 的函数，将其转换为 BinTree:

• 每个NodeG顺序匹配二叉树中的一个NodeB节点；
• NodeB的左儿子匹配NodeG的第一个儿子；
• NodeB 的右儿子是 NodeG 之后的下一个节点(这意味着，下一个节点在 NodeG 的子节点之间)的 parent )

视觉示例(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)

最后一行代码是行不通的，也是看不懂的

Answer 1

如果节点是 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

如果我在手工操作时没有搞砸，这就是我想要的结果。