バイナリツリーの幅を最初に印刷する深さの最初の反復深化アルゴリズム

Question

私はプログラマーではないが、私の個人的なプロジェクトの一環として、バイナリツリーを印刷することができる再帰的な解決策があるかどうかを知りたい幅の広い順番、レベル順？私は反復深さの最初のアルゴリズムを使用できることを理解していますか？以下のバイナリツリーの

#Helper method 
def getChildren(node): 
    children=[] 
    hasLeft = node.left is not None 
    hasRight = node.right is not None 
    if not hasLeft and not hasRight: 
     return [] 
    if hasLeft: 
     children.append(node.left) 
    if hasRight: 
     children.append(node.right) 
    return children 

def DLS(node, depth): 
    """Depth Limited Search""" 
    if (depth == 0): 
     return node 
    elif (depth > 0): 
     print node.value, 
     children = getChildren(node) 
     for child in children: 
      DLS(child, depth-1) 
    else: 
     return False 

： (1)3 (2)2 (4)1 (8)1 (9)0 (5)1 (3)1 (6)1 (7)0 None

最初のレベルの順序が、プリオーダーの深さではありません。私は、このトラバーサル出力を取得しています
(1)3
(2)2 (3)1
(4)1 (5)1 (6)1 (7)0
(8)1 (9)0

。

DLS関数の深さを反復する必要がありますか？バイナリツリーのレベルオーダープリントアウトを実装するにはどうすればよいですか？データ構造の観点から

感謝 アレックス

Answer 1

、深さ優先と幅優先の間の違いは、深さ優先スタックを使用し、幅優先キューを使用しています。

深い意味では、「あなたが最後に処理した結果を処理する」という考え方です。したがって、スタックを使用すると、プッシュされた最後のノードが常にポップされ、正しい動作が得られます。

幅優先は、「選択したノードのすべての結果を最初に処理し、次に進む」という考え方です。だから最初に結果を見つけ出し（そしてそれらを保存する）、あなたがそれらを見つけた順にそれらを処理し始めるだけです。これをサポートする最も簡単なデータ構造はキューです。

問題は、再帰でスタック（呼び出しスタック）を使用することです。つまり、データ構造は見えませんが、実際はそこにあります。呼び出しをキューに入れる（単純な）方法はないため、明示的なキューを使用せずに幅優先探索をコードに変換することはできません。

キューで幅優先の実装についての情報が必要な場合は、Wikipediaをチェックアウトすることをお勧めします。