我正在编写二叉树中广度优先搜索的代码,我已经把所有的数据存储在队列中,但是我不知道如何遍历所有的节点并消耗它们所有的子节点。
下面是我的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);
}
}
我已经将根数据加入队列,但是仍然不起作用。有人能指出我的错误吗?
4条答案
按热度按时间nzk0hqpo1#
不用递归就可以很容易地写一个BFS。只需要使用一个队列来排序你的扩展:
关键是不需要递归地遍历树;只需让数据结构处理访问节点的顺序。
请注意,我在这里使用的是C++ deque,但任何允许您将项目放在后面并从前面获取它们的方法都可以很好地工作。
o2rvlv0m2#
首先将
head
节点插入队列。循环将在队列不为空时进行迭代。从头节点开始,在每次迭代中移除一个节点,并将非空查尔兹节点插入队列。在每次迭代中,一个节点退出,其非空子节点被推送。在下一次迭代中,下一个最早发现的顶点,现在位于队列的前面。被取出(按照它们被发现的顺序),然后对它们进行处理以检查它们的子项。当队列中不再有等待选择的已发现顶点时,迭代停止,因此二叉树(图的连通分支)中已发现的所有顶点都被选择。
在你的代码中,你首先传递队列中的节点,然后递归遍历这些查尔兹,这会创建一个DFS模式。如果你必须做递归,你需要检查队列是否为空作为基本条件。也要检查你是如何传递队列的,我认为这可能是不正确的。我建议一个迭代的解决方案。
dfuffjeb3#
您在这里不是执行广度优先遍历,而是将左侧和右侧元素排入队列,然后移动到左侧子树。您将首先耗尽左侧子树,然后移动到右侧子树。
编写一个过程来将节点入队。
tpgth1q74#
这是一个BFS的静态代码,以明确BFS的概念。在这段代码中,我使用了2个数组,一个是节点数组,另一个是边数组。并通过递归打印了一个有向图中每个节点的所有邻居。
这是代码: