エンジニア実践的基礎: BST 深さ優先探索

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

深さ優先探索とは？

深さ優先探索は木やグラフの走査方の一つです。ルートノードからリーフまで走査して、隣接ノードに移り、全てのノードを走査します。ペンキで壁を縦に塗りながら全体を埋めるイメージです。

縦に走査する際に、どの時点でノードを参照するかによって「inorder」「preoder」「postorder」の３つの方法があります。

inorder は左部分木→親ノード→右部分木の順で参照します。

def preorder(root):
    if not root:
        return    
    preorder(root.left)
    print(root.val) // 参照
    preorder(root.right)

preorder は親ノード→左部分木→右部分木の順に参照します。

def preorder(root):
    if not root:
        return    
    print(root.val)
    preorder(root.left)
    preorder(root.right)

postorder は左部分木→右部分木→親ノードの順に参照します。

def postorder(root):
    if not root:
        return    
    postorder(root.left)
    postorder(root.right)
    print(root.val)

最後にそれぞれの走査方の活用例を紹介します。

BST で inorder で走査すると小さい順に値を参照できます。preoder は根から順にノードを参照するので木構造の再構築に使えます。postorder はファイルシステムのディレクトリを削除する際、子ディレクトリやファイルを先に削除し、最後に親ディレクトリを削除するという処理に利用されます。