假設我使用的是使用以下結構的樹：
data Tree a = LEAF a | NODE a (Tree a) (Tree a)
deriving (Show, Read, Eq)
我將如何創建一個函式，該函式能夠將在每個等效節點/葉子上找到的值相加，而無需匯入任何庫（讓我使用 Prelude 庫），并且與
function :: Num a => Tree a -> Tree a -> Tree a
例如，假設輸入是
left = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
right = NODE 1 (NODE 2 (LEAF 3) (LEAF 6)) (NODE 7 (NODE 8 (LEAF 10) (LEAF 11)) (LEAF 9))
merge_trees left right
那么輸出應該是
NODE 2
(NODE 4 (NODE 6 (LEAF 4) (LEAF 5)) (LEAF 12))
(NODE 14 (NODE 16 (LEAF 10) (LEAF 11)) (LEAF 18))
任何和所有的幫助將不勝感激。
uj5u.com熱心網友回復：
如果我們仔細考慮引數的不同組合，這真的很簡單merge_trees。
- 一片葉子，一片葉子。
- 左邊是葉子，右邊是節點。
- 左邊是一個節點，右邊是一個葉子。
- 左邊一個節點，右邊一個節點。
第一種情況非常簡單。
merge_trees (LEAF a) (LEAF b) = LEAF (a b)
第二種和第三種情況只需要我們將葉子的值加到節點的值上，其余的節點不變回傳。
merge_trees (LEAF a) (NODE b l r) = NODE (a b) l r
merge_trees (NODE b l r) (LEAF a) = NODE (a b) l r
最后一個選項需要最多的作業，但基本上很簡單。我們將兩個節點的值相加，并用該值構造一個新節點，并將遞回應用于merge_trees兩個節點的相應分支的結果。
merge_trees (NODE a l r) (NODE b l' r') = NODE v l'' r''
where
v = a b
l'' = merge_trees l l'
r'' = merge_trees r r'
Prelude> left = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
Prelude> right = NODE 1 (NODE 2 (LEAF 3) (LEAF 6)) (NODE 7 (NODE 8 (LEAF 10) (LEAF 11)) (LEAF 9))
Prelude> merge_trees left right
NODE 2 (NODE 4 (NODE 6 (LEAF 4) (LEAF 5)) (LEAF 12)) (NODE 14 (NODE 16 (LEAF 10) (LEAF 11)) (LEAF 18))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/432681.html