(我假设这只是某种思维练习，或者甚至是一个恶作剧的家庭作业/面试问题，但是我想我可以想象一些奇怪的场景，由于某种原因不允许有任何堆空间[一些非常糟糕的自定义内存管理器?一些奇怪的运行时/操作系统问题?当你仍然可以访问堆栈时…)

宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(这是一个堆栈，因此得名)作为辅助存储(队列)几乎是注定要失败的，除非您对调用堆栈做了一些不应该做的愚蠢可笑的事情。

同样，您尝试实现的任何非尾递归本质上都是向算法添加堆栈。这使得它不再在二叉树上进行广度优先搜索，因此传统BFS的运行时和诸如此类的东西不再完全适用。当然，您总是可以简单地将任何循环转换为递归调用，但这并不是任何有意义的递归。

However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.

我必须实现以BFS顺序输出的堆遍历。它实际上不是BFS，但完成了相同的任务。

private void getNodeValue(Node node, int index, int[] array) {
    array[index] = node.value;
    index = (index*2)+1;

    Node left = node.leftNode;
    if (left!=null) getNodeValue(left,index,array);
    Node right = node.rightNode;
    if (right!=null) getNodeValue(right,index+1,array);
}

public int[] getHeap() {
    int[] nodes = new int[size];
    getNodeValue(root,0,nodes);
    return nodes;
}

我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列Q是通过引用传递的，那么你可以得到下面这个愚蠢的尾部递归函数:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

下面的方法使用DFS算法来获取特定深度的所有节点——这与对该级别进行BFS相同。如果您找到树的深度，并对所有级别执行此操作，结果将与BFS相同。

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

找到树的深度是小菜一碟:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

我想在上面的答案中加上我的观点，如果语言支持生成器之类的东西，bfs可以协递归地完成。

首先，@Tanzelax的回答是:

宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的

实际上，普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行，因此它给了我们产生下一层节点的子节点的机会，而无需深入研究节点的更深层次的后代。

下面的代码是Python中的递归bfs。

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

这里的直觉是:

BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列，BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤

(我假设这只是某种思维练习，或者甚至是一个恶作剧的家庭作业/面试问题，但是我想我可以想象一些奇怪的场景，由于某种原因不允许有任何堆空间[一些非常糟糕的自定义内存管理器?一些奇怪的运行时/操作系统问题?当你仍然可以访问堆栈时…)

宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(这是一个堆栈，因此得名)作为辅助存储(队列)几乎是注定要失败的，除非您对调用堆栈做了一些不应该做的愚蠢可笑的事情。

同样，您尝试实现的任何非尾递归本质上都是向算法添加堆栈。这使得它不再在二叉树上进行广度优先搜索，因此传统BFS的运行时和诸如此类的东西不再完全适用。当然，您总是可以简单地将任何循环转换为递归调用，但这并不是任何有意义的递归。

However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.