c - 二叉树中的 BFS

Question

我正在尝试为二叉树中的广度优先搜索编写代码。我已将所有数据存储在一个队列中，但我不知道如何前往所有节点并使用它们的所有子节点。

这是我在 C 中的代码:

void breadthFirstSearch (btree *bt, queue **q) {
   if (bt != NULL) {

      //store the data to queue if there is

      if (bt->left != NULL) enqueue (q, bt->left->data);
      if (bt->right != NULL) enqueue (q, bt->right->data);

      //recursive

      if (bt->left != NULL) breadthFirstSearch (bt->left, q);
      if (bt->right != NULL) breadthFirstSearch (bt->right, q);
   }
}

我已经将根数据加入队列，但它仍然无法正常工作。 谁能指出我的错误？

Answer 1

无需递归即可轻松编写 BFS。只需使用队列来订购您的扩展:

void BFS(btree *start)
{
    std::deque<btree *> q;
    q.push_back(start);
    while (q.size() != 0)
    {
        btree *next = q.front();
        // you may want to print the current node here or do other processing
        q.pop_front();
        if (next->left)
            q.push_back(next->left);
        if (next->right)
            q.push_back(next->right);
    }
}

关键是不需要递归遍历树；您只需让您的数据结构处理您访问节点的顺序。

请注意，我在这里使用的是 C++ 双端队列，但任何让您将项目放在后面并从前面获取它们的东西都可以正常工作。