java - 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

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

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 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)