如何做二叉树的尾递归？

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)))