功能把一個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到二叉樹

回答

相關問題