如果你有一棵二叉树,你如何使用尾递归迭代(按顺序使用)它?我知道尾递归涉及您在迭代时计算新值,然后当您到达基本情况时,您只需返回累积值。但是,当您必须调用函数调用两次时,如何为树执行此操作?
问问题
4461 次
1 回答
8
假设深度优先从左到右遍历,您不能将尾递归用于左侧分支,但您可以将其用于右侧分支。
示例方案代码(假设您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)))
于 2013-02-11T04:05:41.867 回答