c - 幅優先探索によって構築された木は二分木ですか?

Question

幅優先探索を勉強しています。質問したいのですが、幅優先探索によって構築されたツリー (つまり、各ノードの先行ノードを格納する BFS ツリー) はバイナリ ツリーですか?

Answer 1

Breadth First Search によって構築された Tree は、必ずしもBinary Tree ではありません。

ウィキペディアによると、バイナリ ツリーは、各ノードが最大 2 つの子ノードを持つツリー データ構造です。

によって構築されたツリーのノードには、BFSが含まれる場合がありますany number of Child nodes。

例：

以下は得られたツリーです：

Breadth First Search次のグラフによる:

ここで、FranfurtBFS ツリーのノードには3 つの子があるため、バイナリ ツリーの定義に違反しています。

したがって、によって構築されたツリーBFSは、必ずしもバイナリ ツリーではありません。