java - 为什么这种深度优先搜索会产生 NullPointerException？

Question

我有一小段代码可以生成任意二叉搜索树的深度优先搜索。这是我的代码:

public void printByDepth()
{
    Queue<BinaryNode<T>> queue = new LinkedList<BinaryNode<T>>();
    BinaryNode<T> current = this;
    queue.add(current);
    while(!queue.isEmpty()){
        current = queue.remove();
        System.out.println(current.element);
        if(current.left != null)
            queue.add(current.left);
        if(current.right != null) // had an extra semicolon here, fixed
            queue.add(current.right);
    }
}

这是一个非常标准的队列方法，但出于某种原因，第 8 行(println(current.element))产生了一个 NPE。我使用的树应该产生以下 DF 输出:F B G A D I C E H。我在纸上完全做到了这一点，在我遍历整个树之前(至少在这种情况下)我永远不应该得到 current = null 或 queue.isEmpty() = true 所以我不确定为什么会这样。所有节点都没有空内容。

此外，有趣的是，如果我将 while 条件更改为 while(current != null) 我没有得到 NPE，但输出是:F B G A D I，它缺少最后一层的元素。

我确定我遗漏了一些简单的东西……有什么提示吗？

编辑:失控的分号 =(谢谢，罗杰。

Answer 1

问题在于:

if(current.right != null);
        queue.add(current.right);

看到 if 上的分号 (;) 了吗？这基本上意味着:如果 current.right 不为空，则什么也不做。之后，始终将 current.right 添加到队列中(即使为 null)。

如果你自动格式化你的代码，这会更容易被看到，因为你的缩进现在错误地暗示 current.right 的添加属于 if 语句。