【Python】中順走査・後順走査の結果から二分木を構築するプログラムの書き方

二分木を構築する際、後順走査（ポストオーダートラバーサル）と中順走査（インオーダートラバーサル）の結果を入力として受け取るケースはよくあります。本記事では、ルート要素の設定や各種走査を行うメソッドを持つクラスを定義し、そのインスタンスを使って二分木を構築する方法を解説します。

以下に実際のサンプルコードを示します。

サンプルコード

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 inorder_traversal(self):
      if self.left is not None:
         self.left.inorder_traversal()
      print(self.key, end=' ')
      if self.right is not None:
         self.right.inorder_traversal()

   def post_order_traversal(self):
      if self.left is not None:
         self.left.post_order_traversal()
      if self.right is not None:
         self.right.post_order_traversal()
      print(self.key, end=' ')

def construct_btree(post_ord, in_ord):
   if post_ord == [] or in_ord == []:
      return None
   key = post_ord[-1]
   node = BinaryTree_struct(key)
   index = in_ord.index(key)
   node.left = construct_btree(post_ord[:index], in_ord[:index])
   node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
   return node

post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]

my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print()

実行結果

The input for post-order traversal is : 1 2 3 4 5
The input for in-order traversal is : 5 4 3 2 1
Binary tree has been constructed...
Verification in process..
Post-order traversal is... 1 2 3 4 5
In-order traversal is... 5 4 3 2 1

コードの解説

• 必要な属性を持つ「BinaryTree_struct」クラスを作成します。

• __init__メソッドでは、左ノードと右ノードを「None」で初期化します。

• set_rootメソッドは、二分木のルートを設定するために使用します。

• inorder_traversalメソッドは、「左 → ノード → 右」の順で走査を行う中順走査を実装しています。

• post_order_traversalメソッドは、「左 → 右 → ノード」の順で走査を行う後順走査を実装しています。

• construct_btree関数は、指定された走査結果をもとに二分木を再帰的に構築します。

• ユーザーからの入力を受け取り、split()で分割した上で整数のリストに変換します。

• construct_btree関数を呼び出して二分木を構築し、その結果を変数に格納します。

• 構築された木に対して後順走査と中順走査を実行し、正しく復元できたかどうかを検証します。

• 結果がコンソールに出力されます。

木の構築ロジックのポイント

このアルゴリズムの鍵となるのは、後順走査の最後の要素が必ず根（ルート）になるという二分木の性質です。construct_btree関数では、まず後順走査リストの末尾の要素をキーとして取得し、それが中順走査リストのどこにあるかを index() で特定します。中順走査は「左 → ノード → 右」の順で訪問するため、その位置より左側の要素が左部分木、右側の要素が右部分木に対応します。この処理を再帰的に繰り返すことで、元の二分木を完全に復元できる仕組みです。