如何在树中使用递归

我是数据结构中树概念的新手。我可以为简单树问题写一个线性代码，但当我尝试将其转换为递归代码时，我非常挣扎。而且我无法为复杂树问题编写递归代码。但我知道树是如何工作的。当我尝试将线性代码转换为递归问题时，我遇到了问题“查找树的高度” 我可以绘制它并想象纸上的流。但我不能写递归。如何在树中使用递归

来源

2017-03-03 s-o-i-a

不知道到底你的问题是什么，但递归适用于树正是它工作在别处以同样的方式。关键是识别一个重复/重复的逻辑，然后将其编码为一个自称的函数。 –

您需要先学习inorder.preorder.postorder遍历和它们。对于每个代码，代码只有4行，然后在遍历期间输入的每个新级别添加计数器 – minigeek

这里的关键是要理解树的每个节点本身都是树。事实上，这可以让你实现递归算法。如您所知，任何递归算法都需要两部分：

停止标准。在这种情况下，我们将定义一个空（空）树的高度为0.
递归部分。在这种情况下，我们可以说树的高度是1加上其最深的孩子的高度。

因此，例如，如果我们在Java中实现这一点：

public static int height(Node n) { 
    if (n == null) { 
     return 0; 
    } 
    return 1 + Math.max(height(n.getLeft()), height(n.getRight())); 
}

来源

2017-03-03 17:58:27 Mureinik

任何节点的高度，是其“最高”子节点+1的高度。因此，从根开始，您递归调用每个子节点上的查找高度函数，选择最大值，加1并返回那个价值。基本情况将是没有孩子的节点，在这种情况下返回0.

来源

2017-03-03 17:54:35 Joe

如何在树中使用递归

回答

相关问题