編寫一個函數來計算樹的左側脊柱

我需要一些幫助來弄清楚如何在Haskell中創建leftSpine函數。基本上，它應該把所有最左邊的葉子放到列表中，但是每當我運行我的代碼時，我都會得到一個空的列表。任何幫助，將不勝感激。編寫一個函數來計算樹的左側脊柱

這是我的代碼。

data Tree x = Leaf | Node (Tree x) x (Tree x) 
    deriving Show 

leftSpine :: Tree x -> [x] 
leftSpine Leaf = [] 
leftSpine (Node lt x rt) = (leftSpine lt)

這裏是我的代碼來測試它。

leftSpine (Node (Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)) 
       4 
       (Node (Node Leaf 5 Leaf) 6 (Node Leaf 7 Leaf)))

應該等於[4,2,1]但它只是出來作爲[]。

來源

2012-02-07 Zantengetsu

leftSpine :: Tree x -> [x] 
leftSpine Leaf = [] 
leftSpine (Node lt x rt) = x:leftSpine lt

你實際上並沒有將任何東西放入列表中。區別在於x:leftSpine lt而不是leftSpine lt。

來源

2012-02-07 01:41:54

我不敢相信我看不到！我做了改變，運行了代碼並且完美地工作。非常感謝！ – Zantengetsu 2012-02-07 02:01:50

它發生在我們所有人身上。別擔心。 – 2012-02-07 02:02:39

您的代碼清楚地表明結果始終是空列表。

第一個案例說明葉子的左脊柱是空的列表。好吧到目前爲止。

第二種情況說節點的左脊柱恰好是節點左子節點的左脊柱。

所以，如果我們想要找到一棵樹的左脊柱，我們將繼續追蹤我們到達的節點的左邊的孩子，知道答案完全等於下一個左孩子的左脊柱。要麼我們最終找到一片葉子，結果是空的列表，或者樹是無限的，我們永遠不會返回結果。你的代碼中沒有任何東西可以返回任何東西。

編寫這種遞歸函數的關鍵是要找出答案是什麼的基本情況（Leaf，在這裏），然後對非基本情況（Node，在這裏），你需要了解如何將子解決方案與本地信息結合起來，以生成完整的解決方案。

在這種情況下，Leaf的左側脊柱很容易，因爲根本沒有數據。那麼如何結合Node lt x rt和leftSpine lt的信息來獲得整棵樹的左脊柱？

來源

2012-02-07 01:57:45 Ben

編寫一個函數來計算樹的左側脊柱

回答

相關問題