algorithm - 提出树遍历递归算法的分步方法？

Question

我试图直观地理解如何创建递归函数(用于任何事物)，但主要用于遍历树以检查该树是否满足特定条件。

举个随机的例子，计算二叉树中不是根或叶的节点数？我如何着手递归地思考这个问题并最终提出一个伪代码解决方案？以前，我会通过绘制不同的场景并创建伪代码来解释我提出的案例来开始解决这样的问题，但我觉得(并且确实)在这里和那里遗漏了一些逻辑。

有什么建议吗？

Answer 1

一般来说，递归就是找到一个重复的模式并将其外推到一个更通用的解决方案。根据维基百科:

"Recursion is the process of repeating items in a self-similar way.”

但这是一个相当模糊和不具体的定义。让我们来看例子。

---

二叉树是一种高度重复的结构。考虑这个(几乎)最小的例子:

现在，假设您要访问该树中的每个节点，假设您是从根节点开始的。这看起来很简单:

visit(l_child) 
already in root   
visit(r_child) 

          already in root 
             /      \
            /        \
visit(l_child)       visit(r_child)

所以基本上你是:

 starting in the root → 
 visiting the left child → 
 getting back to the root → 
 visiting the right child → 
 getting back to the root. 

看看另一个二叉树的例子:

如您所见，它与之前的结构非常相似。现在，让我们访问每个彩色节点:

visit(l_subtree) 
already in root     
visit(r_subtree) 

这是完全相同的模式。既然我们知道如何遍历子树，我们就可以想到一个更通用的算法:

inorder(node):
    if node == null:   //we've reached the bottom of a binary tree
        return 0
    inorder(node.l_child)
    do_something(node)
    inorder(node.r_child)

这就是整个中序遍历算法。我敢肯定，您可以自己弄清楚如何为前序和后序编写伪代码。

如果递归对你来说仍然不直观，你可以查看这个 fractals example .