Here is a JavaScript Implementation that fakes Breadth First Traversal with Depth First recursion. I'm storing the node values at each depth inside an array, inside of a hash. If a level already exists(we have a collision), so we just push to the array at that level. You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices. You can return nodes, values, convert to a Linked List, or whatever you want. I'm just returning values for the sake of simplicity.

BinarySearchTree.prototype.breadthFirstRec = function() {

    var levels = {};

    var traverse = function(current, depth) {
        if (!current) return null;
        if (!levels[depth]) levels[depth] = [current.value];
        else levels[depth].push(current.value);
        traverse(current.left, depth + 1);
        traverse(current.right, depth + 1);
    };

    traverse(this.root, 0);
    return levels;
};


var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:  
{ '0': [ 20 ],
  '1': [ 8, 22 ],
  '2': [ 4, 12, 24 ],
  '3': [ 10, 14 ] } */

下面是一个使用迭代方法的实际广度优先遍历的示例。

BinarySearchTree.prototype.breadthFirst = function() {

    var result = '',
        queue = [],
        current = this.root;

    if (!current) return null;
    queue.push(current);

    while (current = queue.shift()) {
        result += current.value + ' ';
        current.left && queue.push(current.left);
        current.right && queue.push(current.right);
    }
    return result;
};

console.log('Breadth First: ', bst.breadthFirst());
//Breadth First:  20 8 22 4 12 24 10 14

我必须实现以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;
}

我已经用c++做了一个程序，它是在联合和不联合图工作。

    #include <queue>
#include "iostream"
#include "vector"
#include "queue"

using namespace std;

struct Edge {
    int source,destination;
};

class Graph{
    int V;
    vector<vector<int>> adjList;
public:

    Graph(vector<Edge> edges,int V){
        this->V = V;
        adjList.resize(V);
        for(auto i : edges){
            adjList[i.source].push_back(i.destination);
            //     adjList[i.destination].push_back(i.source);
        }
    }
    void BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q);
    void BFSRecursivelyJointandDisjointGraph(int s);
    void printGraph();


};

void Graph :: printGraph()
{
    for (int i = 0; i < this->adjList.size(); i++)
    {
        cout << i << " -- ";
        for (int v : this->adjList[i])
            cout <<"->"<< v << " ";
        cout << endl;
    }
}


void Graph ::BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q) {
    if (q.empty())
        return;
    int v = q.front();
    q.pop();
    cout << v <<" ";
    for (int u : this->adjList[v])
    {
        if (!discovered[u])
        {
            discovered[u] = true;
            q.push(u);
        }
    }
    BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);

}

void Graph ::BFSRecursivelyJointandDisjointGraph(int s) {
    vector<bool> discovered(V, false);
    queue<int> q;

    for (int i = s; i < V; i++) {
        if (discovered[i] == false)
        {
            discovered[i] = true;
            q.push(i);
            BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);
        }
    }
}

int main()
{

    vector<Edge> edges =
            {
                    {0, 1}, {0, 2}, {1, 2}, {2, 0}, {2,3},{3,3}
            };

    int V = 4;
    Graph graph(edges, V);
 //   graph.printGraph();
    graph.BFSRecursivelyJointandDisjointGraph(2);
    cout << "\n";




    edges = {
            {0,4},{1,2},{1,3},{1,4},{2,3},{3,4}
    };

    Graph graph2(edges,5);

    graph2.BFSRecursivelyJointandDisjointGraph(0);
    return 0;
}

愚蠢的方式:

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}

二进制(或n-ary)树的BFS可以在没有队列的情况下递归完成，如下所示(在Java中):

public class BreathFirst {

    static class Node {
        Node(int value) {
            this(value, 0);
        }
        Node(int value, int nChildren) {
            this.value = value;
            this.children = new Node[nChildren];
        }
        int value;
        Node[] children;
    }

    static void breathFirst(Node root, Consumer<? super Node> printer) {
        boolean keepGoing = true;
        for (int level = 0; keepGoing; level++) {
            keepGoing = breathFirst(root, printer, level);
        }
    }

    static boolean breathFirst(Node node, Consumer<? super Node> printer, int depth) {
        if (depth < 0 || node == null) return false;
        if (depth == 0) {
            printer.accept(node);
            return true;
        }
        boolean any = false;
        for (final Node child : node.children) {
            any |= breathFirst(child, printer, depth - 1);
        }
        return any;
    }
}

按升序遍历打印数字1-12的示例:

public static void main(String... args) {
    //            1
    //          / | \
    //        2   3   4
    //      / |       | \
    //    5   6       7  8
    //  / |           | \
    // 9  10         11  12

    Node root = new Node(1, 3);
    root.children[0] = new Node(2, 2);
    root.children[1] = new Node(3);
    root.children[2] = new Node(4, 2);
    root.children[0].children[0] = new Node(5, 2);
    root.children[0].children[1] = new Node(6);
    root.children[2].children[0] = new Node(7, 2);
    root.children[2].children[1] = new Node(8);
    root.children[0].children[0].children[0] = new Node(9);
    root.children[0].children[0].children[1] = new Node(10);
    root.children[2].children[0].children[0] = new Node(11);
    root.children[2].children[0].children[1] = new Node(12);

    breathFirst(root, n -> System.out.println(n.value));
}

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

首先，@Tanzelax的回答是:

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

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

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

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

这里的直觉是:

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