如何对二叉树进行尾递归? [英] How to do tail recursion for a binary tree?

问题描述

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

If you have a binary tree, how can you iterate through (using in order) it using tail recursion? I know that tail recursion involves you to calculate the new value as you iterate, and then when you reach the base case, you just return the accumulation. But how do you do this for a tree, when you have to call the function call twice?

推荐答案

假设深度优先从左到右遍历，您不能对尾部分支使用尾递归，但可以将尾部递归用于右分支.手分支.

Assuming a depth-first left-to-right traversal, you cannot use tail recursion for the left-hand branch, but you can use it for the right-hand branch.

示例方案代码(假设您的tree具有三个访问器功能，value，left和right):

Example Scheme code (assuming that your tree has three accessor functions, value, left, and 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) ...)处于尾部位置，所以这是尾部呼叫.

The (collect (right node) ...) is in tail position, so that is a tail call.

您还可以执行从右到左的遍历，在这种情况下，是尾部递归的向左下降:

You can also do a right-to-left traversal, in which case it's the leftward descents that are tail-recursive:

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

这篇关于如何对二叉树进行尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！