【Python】ポストオーダー（後順走査）で深さ優先探索トラバーサルを実装するプログラム

木構造に対して後順走査（ポストオーダートラバーサル）を用いた深さ優先探索（DFS）を実装するには、要素の追加、特定要素の検索、後順走査の実行といった機能を備えたツリークラスを定義します。クラスのインスタンスを生成すれば、これらのメソッドを自由に呼び出して操作できるようになります。

以下に、具体的な実装例を示します。

後順走査（ポストオーダー）とは

後順走査とは、「すべての子ノードを先に訪問し、その後に自分自身（親ノード）を訪問する」という順序で木をたどる手法です。二分木では「左の子 → 右の子 → 親」の順になりますが、本記事のように子の数が任意である一般木の場合は「すべての子 → 自分自身」の順で処理を行います。

サンプルコード

次のPythonプログラムは、対話形式でノードの追加と、後順走査による深さ優先探索を実行できる例です。

class Tree_Struct:
    def __init__(self, key=None):
        self.key = key
        self.children = []

    def add_elem(self, node):
        self.children.append(node)

    def search_elem(self, key):
        if self.key == key:
            return self
        for child in self.children:
            temp = child.search_elem(key)
            if temp is not None:
                return temp
        return None

    def postorder_traversal(self):
        for child in self.children:
            child.postorder_traversal()
        print(self.key, end=' ')

my_instance = None

print('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('dfs')
print('quit')

while True:
    my_input = input('What operation would you do ? ').split()

    operation = my_input[0].strip().lower()
    if operation == 'add':
        data = int(my_input[1])
        new_node = Tree_Struct(data)
        suboperation = my_input[2].strip().lower()
        if suboperation == 'at':
            my_instance = new_node
        else:
            position = my_input[3].strip().lower()
            key = int(position)
            ref_node = None
            if my_instance is not None:
                ref_node = my_instance.search_elem(key)
            if ref_node is None:
                print('No such key exists')
                continue
            ref_node.add_elem(new_node)

    elif operation == 'dfs':
        print('The post-order traversal is : ', end='')
        my_instance.postorder_traversal()
        print()

    elif operation == 'quit':
        break

実行例

Menu (this assumes no duplicate keys)
add <data> at root
add <data> below <data>
dfs
quit
What operation would you do ? add 5 at root
What operation would you do ? add 9 below 5
What operation would you do ? add 2 below 9
What operation would you do ? dfs
The post-order traversal is : 2 9 5
What operation would you do ? quit

コードの解説

• 必要な属性を持つ「Tree_Struct」クラスを定義しています。

• 「__init__」コンストラクタは、ノードのキーを設定するとともに、子ノードを格納するための空のリストを初期化します。

• 「add_elem」メソッドは、引数として渡されたノードを自分の子として追加します。

• 「search_elem」メソッドは、指定されたキーを持つノードを再帰的に検索し、見つかった場合はそのノードを返します。

• 「postorder_traversal」メソッドは、まずすべての子ノードに対して再帰的に自身を呼び出し、その後に現在のノードのキーを出力することで、後順走査を実現しています。

• インスタンス変数「my_instance」は最初「None」で初期化されており、ルートノードを追加した時点で実際の木を参照するようになります。

• whileループ内でユーザー入力を受け付け、「add」「dfs」「quit」の各コマンドに応じた処理を実行します。

• 指定したキーが木の中に存在しない場合は「No such key exists」と表示され、その操作はスキップされます。

• 最終的な結果はコンソールに出力されます。

まとめ

このように、再帰を活用した後順走査は、すべての子ノードの処理を完了させてから親ノードを処理するため、依存関係のある階層データの処理や式木の評価など、さまざまな場面に応用できます。上記のコードはそのままコピーして実行できるので、ぜひ手元で動かして挙動を確認してみてください。