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

Question

我正在研究广度优先搜索。我想问：由广度优先搜索构造的树（即BFS树，我们存储每个节点的前身）是二叉树吗？

Answer 1

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

根据维基百科，二叉树是一种树数据结构，其中每个节点最多有两个子节点。

由 构造的树的节点BFS可能包含any number of Child nodes。

示例：

以下是获得的树：

通过Breadth First Search下图：

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

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