再帰を用いた二分木の深さ優先探索（DFS）を実装するPythonプログラム

木構造に対して再帰を使って深さ優先探索（DFS）を実行したい場合、まず二分木を表すクラスを定義し、その中にノードの挿入・検索・走査を行うためのメソッドを実装します。

深さ優先探索は、ある枝の先端まで一気にたどってから戻りながら（バックトラックしながら）他の枝を探索していく手法です。以下では、対話型のメニューを持つサンプルプログラムでその動作を確認できます。

コード例

class BinaryTree_struct:
   def __init__(self, key=None):
      self.key = key
      self.left = None
      self.right = None

   def set_root(self, key):
      self.key = key

   def insert_at_left(self, new_node):
      self.left = new_node

   def insert_at_right(self, new_node):
      self.right = new_node

   def search_elem(self, key):
      if self.key == key:
         return self
      if self.left is not None:
         temp = self.left.search_elem(key)
         if temp is not None:
            return temp
      if self.right is not None:
         temp = self.right.search_elem(key)
         return temp
      return None

   def depth_first_search(self):
      print('entering {}...'.format(self.key))
      if self.left is not None:
         self.left.depth_first_search()
      print('at {}...'.format(self.key))
      if self.right is not None:
         self.right.depth_first_search()
      print('leaving {}...'.format(self.key))

btree_instance = None

print('メニュー（キーの重複は不可）')
print('insert <データ> at root')
print('insert <データ> left of <キー>')
print('insert <データ> right of <キー>')
print('dfs')
print('quit')

while True:
   my_input = input('操作を選択してください: ').split()

   op = my_input[0].strip().lower()
   if op == 'insert':
      data = int(my_input[1])
      new_node = BinaryTree_struct(data)
      sub_op = my_input[2].strip().lower()
      if sub_op == 'at':
         btree_instance = new_node
      else:
         position = my_input[4].strip().lower()
         key = int(position)
         ref_node = None
         if btree_instance is not None:
            ref_node = btree_instance.search_elem(key)
         if ref_node is None:
            print('そのキーは存在しません。')
            continue
         if sub_op == 'left':
            ref_node.insert_at_left(new_node)
         elif sub_op == 'right':
            ref_node.insert_at_right(new_node)
   elif op == 'dfs':
      print('深さ優先探索の走査結果:')
      if btree_instance is not None:
         btree_instance.depth_first_search()
      print()

   elif op == 'quit':
      break

実行結果

メニュー（キーの重複は不可）
insert <データ> at root
insert <データ> left of <キー>
insert <データ> right of <キー>
dfs
quit
操作を選択してください: insert 5 at root
操作を選択してください: insert 6 left of 5
操作を選択してください: insert 8 right of 5
操作を選択してください: dfs
深さ優先探索の走査結果:
entering 5...
entering 6...
at 6...
leaving 6...
at 5...
entering 8...
at 8...
leaving 8...
leaving 5...
操作を選択してください: quit

プログラムの解説

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

• コンストラクタ「__init__」では、ノードのキーを受け取り、左右の子ノードを「None」で初期化します。

• 「set_root」メソッドは、木の根（ルート）となるキーを設定するために用意されています。

• 「insert_at_left」メソッドは、指定したノードの左側に新しいノードを追加します。

• 「insert_at_right」メソッドは、指定したノードの右側に新しいノードを追加します。

• 「search_elem」メソッドは、左部分木→右部分木の順に再帰的にたどり、目的のキーを持つノードを検索します。見つからなければ「None」を返します。

• 「depth_first_search」メソッドは、二分木の深さ優先探索を実行します。「entering（入る）」「at（通過）」「leaving（出る）」を出力することで、再帰の呼び出しと戻りの流れが視覚的にわかるようになっています。

• クラスのインスタンス変数を作成し、初期値として「None」を代入しておきます。

• メニューを表示し、ユーザーに実行したい操作を入力してもらいます。

• 入力されたコマンドに応じて、挿入・探索・DFS走査などの対応する処理が実行されます。

• 処理結果は随時コンソールに出力され、「quit」が入力されるまで操作を繰り返せます。

このように、再帰を利用すると深さ優先探索のコードをシンプルかつ直感的に記述できます。各ノードで「自分より深い部分をすべて処理してから戻る」という構造が、そのまま関数の再帰呼び出しに対応している点がポイントです。