二叉树，仅打印一层（广度优先搜索）

Question

我希望了解如何打印二叉树中的特定层级。我在这里看到了许多关于BFS的问题，但没有一个是关于仅打印一层的。

如果我想打印该树的第2层，该如何更改普通的BFS搜索呢？

   6
  / \
 4   8
/ \ / \
1 5 7  9

2级将是1、5、7、9。谢谢!

- nitrnitr

---

跟踪您当前所处的级别，并在达到2级时终止。 - Oliver Charlesworth

这很明显，但我找不到使用常规BFS的方法来实现它。它处理节点队列，但不区分级别。它只是按照BFS顺序入队并处理它们。 我能想到的只有一些奇怪的解决方案，检查每个级别应该具有的节点数量，但当我考虑非满树时，它就会崩溃。 - nitrnitr

一种方法是将{level,node}的元组入队，而不仅仅是{node}。 - Oliver Charlesworth

Answer 1

你的节点需要有一个 level 属性。然后当你在树上遍历时，你可以询问：

if (level == 2) //or whatever level you wish
{
    ...
}

这是一个好的例子: 在特定层级上查找二叉树中的所有节点 (面试题) 如果节点上没有层级，并且您无法更改它，则可以将其作为全局变量放在进行检查的方法中 - 这不是首选但是另一种解决方案。我还没有检查过这个答案的代码，但我相信它应该非常接近解决方案。

e.g:

int level = 0;

     public void PrintOneLevelBFS(int levelToPrint)    
     {      
        Queue q = new Queue();
        q.Enqueue(root); //Get the root of the tree to the queue.

        while (q.count > 0)
        {
            level++; //Each iteration goes deeper - maybe the wrong place to add it (but somewhere where the BFS goes left or right - then add one level).
            Node node = q.DeQueue();

            if (level == levelToPrint)
            {
                ConsoleWriteLine(node.Value) //Only write the value when you dequeue it
            }

            if (node.left !=null)
            {
                q.EnQueue(node.left); //enqueue the left child
            }
            if (n.right !=null)
            {
                q.EnQueue(node.right); //enqueue the right child
            }
         }
     }

- Misha Zaslavsky

---

谢谢Misha，这是一个好的解决方案，但如果节点上没有那个属性怎么办呢？ 我在计算机科学大学，我认为这可能是一个可能的测试练习。 - nitrnitr

嗯，我不认为它会起作用。每次循环运行时它会增加级别（1个循环=1个节点，因此不是每个级别都增加）。 - nitrnitr

是的，这就是为什么你应该考虑把级别放在正确的位置，而且如果你保持相同的级别，那么你不应该添加它，也许在进行level++之前可以再进行一次检查。 - Misha Zaslavsky

Answer 2

我从一位教授那里得到了一个类似问题的答案。

在二叉搜索树中，找到特定层级上最小的数字。（GenericTree和GenericQueue是本课程的具体类。此外，我翻译了整个练习，因此有些东西可能听起来很奇怪或不正确:P

public int calculateMinimum( BinaryTree<Integer> tree, int n ){
    GenericQueue<BinaryTree<Integer>> queue = new GenericQueue<BinaryTree<Integer>>();
    queue.push(tree);
    queue.push(new BinaryTree<Integer>(-1));
    int nActual = 0; //actual level
    while (!queue.isEmpty()){
        tree = queue.pop();
        if (nActual == n){
            int min = tree.getRootData();
            while (!queue.isEmpty()){
                tree = queue.pop();
                if (!tree.getRootData().equals(-1) && (tree.getRootData()<min))
                    min = tre.getRootData();
            }
            return min;
        }
        if (!tree.getLeftChild().getRootData() == null))
            queue.push(tree.getLeftChild());
        if (!tree.getRightChild().getRootData() == null))
            queue.push(tree.getRightChild());
        if ((tree.getRootData().equals(-1) && (!queue.isEmpty())){
            nActual++;
            queue.push(new BinaryTree<Integer>(-1));
        }
    }
    return -1;
}                

- nitrnitr