計算樹中的節點

與f＃戰鬥 - 戰鬥是在樹的領域 - 專門計算節點的數量。這真是令人感興趣，因爲我希望最終在F＃中編寫代碼的程序涉及多路樹，不幸的是它已經開始了一些麻煩的開始 - 我希望你能夠幫助！計算樹中的節點

99 f＃系列中的問題61，要求計算二叉樹的葉子。該解決方案（如下）計算節點，但我的問題是不理解

雙遞歸是如何工作的環左（LACC樂趣 - >循環的權利..）
什麼cont (branchF x lacc racc)是，我印象是續是「ABC」的功能，但這種只需要兩個參數...
loop t id id爲單位類型 - 我不明白這是怎麼暗示

基本上不理解這一點，或者它在樹中流動的順序（調試&步驟沒有證明有用）如果有更簡單的例子，預讀的建議等，那麼請指導我。

任何幫助非常感謝，問題的解決方案代碼如下：

乾杯

type 'a Tree = Empty | Branch of 'a * 'a Tree * 'a Tree 

let foldTree branchF emptyV t = 
    let rec loop t cont = 
     match t with 
     | Empty -> 
      cont emptyV 
     | Branch (x, left, right) -> 
      loop left (fun lacc -> 
       loop right (fun racc -> 
        cont (branchF x lacc racc))) 
    loop t id 

let counLeaves tree = 
    foldTree (fun abc lc rc -> 
     if lc + rc = 0 then 1 
     else 1 + lc + rc) 0 tree 

let Tree1 = Branch ('x', Branch ('x', Empty, Empty),Branch ('x', Empty, Branch ('x', Empty, Branch ('x', Empty, Empty)))) 


let result = counLeaves Tree1

來源

2013-02-26 dusiod

我不知道我在寫什麼解決方案時想的是什麼，但是Lee很害怕，而counvaves中的「if」沒有做任何事情。解決辦法應該是讓countraves tree = tree |> foldTree（fun_lc rc - > 1 + lc + rc）0.如果你想知道更多關於摺疊和延續的知識。我在這裏推薦Brian McNamara在Catamorphisms上的系列文章[鏈接]（http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/）。那是我得到fodlTree功能的地方。 – 2013-02-28 21:32:21

嗨塞薩爾，只是想說謝謝你發佈了99個問題系列 - 真的很棒的學習工具 - 特別是多種解決方案。乾杯! – dusiod 2013-03-05 19:22:37

鑑於沒有人回答你關於id的問題，「id」是身份運算符。你可以用（fun x - > x）替換id來獲得同樣的效果。看到這裏：http://msdn.microsoft.com/en-us/library/ee353607.aspx此外，這個代碼有一些可怕的錯誤 - 我創建了一個簡單的4節點樹，它告訴我的大小是32！一旦我找出所有的細微差別，我會發佈一個正確的實現（我正在工作）。 – 2014-01-13 01:23:24

顧名思義，foldTree在定製Tree類型定義了摺疊功能。

定義foldTree的幼稚的方式可以是：

let rec foldTreeNaive accFun init = function 
    | Empty -> init 
    | Branch (x, left, right) -> 
     let lacc = foldTreeNaive accFun init left 
     let racc = foldTreeNaive accFun init right 
     accFun x lacc racc

具有這種功能的問題是，它可能潛在作出非常深刻的遞歸調用，如果被摺疊在樹深，因爲遞歸調用必須在可以調用累加器函數之前完成一個節點。例如，以下導致堆棧溢出異常：

let unbalanced = [1..100000] |> List.fold (fun t i -> Branch(i, t, Empty)) Empty 
let nodeCount = foldTreeNaive (fun _ lc rc -> lc + rc + 1) 0 unbalanced

的常用方法，以避免這種堆棧溢出是使函數尾遞歸，但因爲有兩個遞歸調用，使這似乎不可能在這種情況下，代替在列表摺疊時需要的一個。

foldTree是使用本地loop函數定義的。此功能很有趣，因爲它使用continuation passing style定義。在CPS中，每個函數都需要一個額外的「延續」函數，這個函數傳遞計算結果並負責決定接下來會發生什麼。請注意，loop是尾遞歸，因此避免了foldTreeNaive的溢出問題。

的類型loop功能的是：

Tree<'a> -> ('b -> 'c) -> 'c

其中「a是樹中的節點的類型，」 b是蓄壓式，和「c是延續函數的結果。

在葉節點的情況下，延續傳遞給傳遞給foldTree函數的空的累加器值。

在Branch的情況下摺疊非空樹時，摺疊的結果取決於左側和右側子樹的結果。這是遞歸完成的，首先通過摺疊左側子樹，然後右側。在過去的左子樹遞歸調用，loop必須建立一個新的延續來接收結果，這是

(fun lacc -> 
    loop right (fun racc -> 
     cont (branchF x lacc racc))

功能。這個延續的作用是對正確的子樹進行遞歸調用，並通過另一個延續來接收該摺疊的結果。當該延續被調用時，左側和右側子樹的結果可在lacc和racc中獲得。此時，可以使用當前節點的值以及左側和右側子樹的結果調用節點的累加函數。然後將該函數的結果傳遞給傳遞給loop的原始延續。

的loop功能然後由foldTree功能在調用線：

loop t id

這裏，id是將接收摺疊的樹的根節點的結果的延續。由於這是所需的值，所以id只是不加修改地返回它的參數。

您可能還會發現this description of fold for binary trees有用。

來源

2013-02-27 09:34:51 Lee

計算樹中的節點

回答

相關問題