c - 广度优先搜索构建的树是二叉树吗？

Question

我正在学习广度优先搜索。我想问:广度优先搜索构建的树(即BFS树，其中我们存储每个节点的前身)是二叉树吗？

Answer 1

广度优先搜索构建的树不一定是二叉树。

根据 Wikipedia ,二叉树是一种树数据结构，其中每个节点至多有两个子节点。

BFS 构建的树的节点可能包含任意数量的子节点。

示例:

以下是获得的树:

下图的广度优先搜索:

这里，BFS 树中的节点Franfurt 有3 个 child ，因此违反了二叉树 的定义。

因此，BFS构造的树不一定是二叉树。