在Java中尝试在二叉搜索树上实现级别顺序遍历

Question

好的，我正在尝试创建一个方法，它将返回一个基本二叉搜索树的级别顺序，该二叉搜索树在其节点中携带int值。我已经想出了大多数其他方法，比如插入、后序和预序，但我一直遇到与level order方法相同的问题

以下是代码：

private DoubleStackQueue<Node> queue = new DoubleStackQueue<Node>();
//this is a queue that uses two stacks, one for the front and one for the back.
//it works just like a queue.
public String levelOrder(){  
    s = "";  //The s is a private String that is implemented earlier
    queue.add(this);  
    while (!queue.isEmpty())  
    {  
        Node node = (Node)queue.remove();  
        if (!(node.equals(null))) {s += ""+node.getVal();}  
        if (!(left.equals(null))) {queue.add(node.left);}  
        if (!(right.equals(null))) {queue.add(node.right);}  
    }  
    return s;  
}

我遇到的主要问题是，当程序到达一个叶节点时，它仍然会将其子节点添加到队列中，即使没有子节点，也只有null，因此我将得到一个在实际项前面有两个null的队列。我最初的if语句是（left！=null）之类的，但这也不起作用。我只是想弄清楚，当没有孩子的时候，如何让程序识别。我需要做什么

Answer 1

几点意见：

1. 主要问题是，在比较中使用left和right而不是node.left和node.right

2. 要与空值进行比较，请使用if (var != null)。不要使用equals()。如果变量为null，则不能对其调用方法，因为这将触发NullPointerExceptions。

3. 一旦你修复了你的代码，你就永远不会把null插入队列。您添加的第一个对象是this，它保证为非null，随后在将项目插入队列之前总是检查null。这意味着你的第一次检查是不必要的

4. 演员阵容应该是不必要的。你的编译器应该警告你这一点

结果：

queue.add(this);

while (!queue.isEmpty())  
{  
    Node node = queue.remove();

    s += "" + node.getVal();

    if (node.left  != null) { queue.add(node.left);  }
    if (node.right != null) { queue.add(node.right); }
}  

Answer 2

看看这个问题：Level-order tree traversal 我相信这和你想达到的目标是一样的，不是吗？这是一个非常经典的问题，所以根据我的经验，它已经被反复讨论过了