recursion - 如何对二叉树进行尾递归？

Question

如果你有一个二叉树，你如何使用尾递归遍历(按顺序使用)它？我知道尾递归涉及您在迭代时计算新值，然后当您达到基本情况时，您只需返回累积值。但是，当您必须两次调用函数时，如何为树执行此操作？

Answer 1

假设深度优先从左到右遍历，则不能对左手分支使用尾递归，但可以对右手分支使用尾递归。

示例 Scheme 代码(假设您的 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)))