Java中使用递归的二叉搜索树

Question

我希望有人能给我解释一下我应该如何完成这两种方法。我愿意自己做这项工作，并且不想偷懒。话虽如此，问题来了：

2种方法： 递归地需要

1. 统计二叉树的节点数，
2. 统计右孩子的数量

我已经实现了以下代码：

public class IntBSTNode
{

    protected int key;
    protected IntBSTNode left, right;

    public IntBSTNode()
    {
        left = right =null;
    }

    public IntBSTNode(int el)
    {
        this(el, null, null);
    }

    public IntBSTNode( int el, IntBSTNode lt, IntBSTNode rt)
    {
        key = el;
        left =lt;
        right = rt;
    }
}

Answer 1

http://en.wikipedia.org/wiki/Recursion

要使递归工作，您需要一个基础案例，以及一组减少到基本案例的案例和行动。

为了计算二叉树中的节点数量，我们可以使用“节点不存在”的基本情况，以及“节点确实存在”的其他情况。

对于另一种情况，（节点确实存在）我们将节点数加 1，将树的每个子树（左和右）中的节点数添加到总计数中。我们如何找到子树中的节点数？只需将我们用于第一个节点的相同条件集应用于子节点即可。

通过反复分解树的子节点，我们可以获得树中节点的总数。

举个例子：

     N1
     /\ 
   N2   N3
   /\    \
 N4  N5   N6

让我们调用我们的计数方法 countNodes()。

countNodes 的伪代码

int countNodes(Node parent):
    if parent:
        return 1 + countNodes(parent.left) + countNodes(parent.right)
    else:
        return 0

countNodes 将首先检查您传递给它的节点是否存在。

如果不存在（基本情况），则返回 0 [从逻辑上讲，这是有道理的，因为如果该节点不存在，则其子树中就不存在不存在的节点]

如果该节点存在，您将返回 1 + 中节点数的总和子树。要查找子树中的节点数，我们只需在每个子节点上调用 countNodes() 方法。

在上面的示例树中，我们从 N1 开始。我们看到 N1 存在，所以我们现在需要找到的是：

1 + 左子树中的节点数 + 右子树中的节点数。

N1 的子树是：

  Left         Right
   N2            N3
   /\             \
 N4  N5            N6

我们首先调用 countNodes( ) N2（N1 的左子树）上的方法。

N2 存在，所以现在我们正在寻找

1 + N2 左子树中的节点数 + N2 右子树中的节点数

N2 的子树是：

Left     Right
 N4       N5

在 N4 上调用 countNodes() 我们正在寻找

1 + N4 左子树中的节点数 + N4 右子树中的节点数

N4 的左节点为 null，因此当在 N4 的左节点上调用 countNodes() 时，它将返回 0（基本情况）。

N4 的右侧节点也为 null，因此右侧节点的 countNodes() 也将返回 0

N4 的挂起操作可以完成，并且您有 1 + 0 + 0 （非基本情况返回值）

现在 N2 的挂起操作看起来像

1 + 1 + 节点数右子树

在 N5 上调用 countNodes() 会得到与 N4 相同的值，因此 N2 的返回值变为：

1 + 1 + 1

N2 将 3 返回给 N1待处理操作使其看起来像：

1 + 3 + #nodes in right subtree

# nodes in N3 subtree is:
countNodes() on N3 returns 1 + countNodes->null (base) + countNodes()->N6

# nodes in N6 subtree is
countNodes() on N6 returns 1 + countNodes->null (base) + countNodes()->null (base)
return value = 1

# nodes in N3 subtree is 1 + 0 + 1
returns 2

finally the call on N1's countNodes() can complete with 

1 + 3 + 2

countNodes() on N1 returns 6

要计算树中的所有正确节点，您可以使用以下伪代码：

int countRightNodes(Node parent):
    if !parent:
        return 0

    if has right node:
        return 1 + (# of right nodes in left subtree) + (# of right nodes in right subtree)
    else:
        return (# of right nodes in left subtree)

Answer 2

递归的意义在于将一个复杂的问题简化，直到它变得微不足道，并使用这个简单问题的解决方案来找到更复杂问题的解决方案，等等，直到可以解决您的实际问题。

在您的情况1）中，复杂的问题是“查找整棵树中的节点数”。但我们可以简化它，说它是 numberOfNodesLeftSubtree + numberOfNodesRightSubtree + 1。然后我们可以写：

public int nbNodes(Node root){
    int count = 1 // our actual node
    if(root.left != null){
        count += nbNodes(root.left);
    }
    if(root.right != null){
        count += nbNodes(root.right);
    }

    return count;
}

就这么简单。

Answer 3

递归思考需要一些练习，但如果做得好，它几乎看起来很神奇。我们需要计算树中的节点数量，所以让我们想想这意味着什么。考虑任何节点及其子树。该子树中的节点数将等于左子树中的节点数加上右子树中的节点数，再加一（对于相关节点）。因此，如果我们假设我们已经有一个可以对子树中的节点进行计数的方法，那么我们可以对该方法进行两次调用。我们还必须担心基本情况，一旦我们有了递归就可以发挥其魔力。