如何做二叉樹的尾遞歸？

Question

如果你有一個二叉樹，你如何使用尾遞歸迭代（按順序使用）？我知道尾遞歸涉及到迭代時計算新值，然後當您到達基本情況時，您只需返回累積。但是當你必須調用兩次函數調用時，你如何爲樹做這件事？

Answer 1

假設深度優先從左到右遍歷，您不能對左手分支使用尾遞歸，但可以將其用於右分支。

實施例方案的代碼（假設你tree有三個存取器函數，value，left，和right）：

(define (collect-in-order tree) 
    (define (collect node result) 
    (if node 
     (collect (right node) 
       (cons (value node) 
         (collect (left node) result))) 
     result)) 
    (reverse (collect tree '()))) 

的(collect (right node) ...)是在尾部位置，所以這是一個尾調用。

你也可以做一個從右到左遍歷，在這種情況下，它的左側下坡是尾遞歸：

(define (collect-in-order tree) 
    (let collect ((node tree) 
       (result '())) 
    (if node 
     (collect (left node) 
       (cons (value node) 
         (collect (right node) result))) 
     result)))