同一深度的显示节点不起作用

Question

插入 OPTIMAL 后的二叉搜索树示例：

void wordsAtDepth() {
        int depth = 0;
        int numOfNodes;
        Queue queue = new Queue(32); // Make a new Queue called queue.
        queue.insert(root); // Insert the root into the queue

        // While queue is not empty we will continue the while loop
        while (!queue.isEmpty()) {
            // numOfNodes keeps track of how many times we are going to 
            // continue the for loop in the current while loop.
            numOfNodes = (int) Math.pow(2, depth);
            // for loop will continue until i is equal to or is greater 
            // than numOfNodes.
            for (int i = 0; i < numOfNodes; i++) {
                // Current will equal to the removed element from the 
                // queue.
                Node Current = queue.remove();
                // If Current does not equal null then print current 
                //  and insert its' left and right child.
                // If Current does equal null then do nothing go to the 
                //  next iteration of the for loop
                if(Current != null){
                    System.out.print(Current.cData);
                    queue.insert(Current.leftChild);
                    queue.insert(Current.rightChild);
                }
            }
            // Makes new line every time we finish the while loop. 
            // Which means new line for the next iteration of the
            // while loop to separate the different depths.
            System.out.println(" ");
            depth++;
        }
    }

节点包含字符值。对于单词 OPTIMAl，它打印正确，但对于像 HAPPY 或 SUPERMAN 这样的单词，它们打印不正确。例如：超人：S PU ER AMN SPUERAMNPUERAMN ERAMNAMNNEMNNAMNN AMNNNNAMNNNNNNNN NNNNNNNN

而不是使用 numOfNodes = (int) Math.pow(2, depth); 当我使用 numOfNodes = queue.length() 时代码有效。但我想使用 numOfNodes = (int) Math.pow(2, depth); 因为 for 循环应该循环一个深度的节点数量。由于深度中的节点数为 2^Depth.

Answer 1

如果您期望某个深度的节点数是 2 的幂，那么您必须确保处理您的树不完美的情况，因为那样——即使您的树是完整 -- 底层不会被完全填满。

简单的解决方法似乎是您总是为从队列中弹出的每个条目添加 2 个条目。所以改变这个：

                if(Current != null){
                    System.out.print(Current.cData);
                    queue.insert(Current.leftChild);
                    queue.insert(Current.rightChild);
                }

对此：

                if(Current != null){
                    System.out.print(Current.cData);
                    queue.insert(Current.leftChild);
                    queue.insert(Current.rightChild);
                } else {
                    queue.insert(null);
                    queue.insert(null);
                }