在二叉树BFS [英] BFS in binary tree

问题描述

我试着写codeS为二叉树广度优先搜索。我已经存储的所有数据在队列中，但我无法弄清楚如何前往所有节点和消费他们的孩子。

I'm trying to write the codes for breadth-first search in binary tree. I've stored all the data in a queue, but I can't figure out how to travel to all nodes and consume all their children.

下面是我的code在C：

Here's my code in 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);
   }
}

我已经排队根数据，但它仍然没有工作。
任何人都可以指出我的错误呢？

I've already enqueued the root data, but it's still not working. Can anyone point out my mistake?

推荐答案

一个BFS可以很容易地写不递归。只需使用一个队列订购您的扩展：

A BFS can be easily written without recursion. Just use a queue to order your expansions:

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);
    }
}

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

The key is that you don't need to traverse the tree recursively; you just let your data structure handle the order in which you visit nodes.

请注意，我使用C ++双端队列这里，但任何可以让你把项目的背面和从前面让他们将正常工作。

Note that I'm using the C++ deque here, but anything that lets you put items on the back and get them from the front will work fine.

这篇关于在二叉树BFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！