algorithm - 二分木での事前注文トラバーサルは、深さ優先検索と同じですか?

Question

事前注文トラバーサルと DFS は、葉ノードまで深さ方向にトラバースする両方の場合と同じように思えます。私が間違っている場合、誰かが私を修正してもらえますか?

前もって感謝します！

Answer 1

プレオーダーはDFSの一種です。

深さ優先トラバーサルには、プレオーダー、インオーダー、ポストオーダーの 3 種類があります。

詳細については、こちらをご覧ください。

Answer 2

そうではありません。事前注文には、左ノードにアクセスしてから右ノードにアクセスする厳密な方法があります。ただし、DFS の場合は厳密な方法がないため、どちらでもかまいません。したがって、スタックに何をプッシュするかに基づいて、複数のトラバーサルが存在します。

Answer 3

おそらく、深さ優先アルゴリズムの定義と実装に依存します。DefaultMutableTreeNodeJava Swing の JTree コンポーネントのクラスには、ツリー トラバーサルに使用される次の列挙メソッドがあります。

• depthFirstEnumeration()
• postorderEnumeration()
• preorderEnumeration()
• widthFirstEnumeration()

Java Swing の実装でdepthFirstEnumerationは、 は と同じpostOrderEnumerationです。私のテストと公式ドキュメントは これを確認しています。

他の人は、深さ優先の意味を別の方法で定義できます。たとえば、ウィキペディアの記事では、事前順トラバーサルと事後順トラバーサルは深さ優先トラバーサルの特定のタイプであると述べています。これは、深さ優先トラバーサルが具体的なトラバーサル アルゴリズムではないことを意味します。