入力としてインオーダーまたはポストオーダートラバーサルの場合にバイナリツリーを構築する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」関数があります。

• バイナリツリーのルートを設定するのに役立つ「set_root」メソッドがあります。

• 「inorder_traversal」という名前の別のメソッドは、順序どおりのトラバーサルを実行します。つまり、左→ノード→右です。

• 「post_order_traversal」という名前の別のメソッドが定義されており、ポストオーダー、つまり左→右→ノードでツリーをトラバースするのに役立ちます。

• 「construct_btree」という名前のメソッドが定義されています。これは、以前に指定された要素を使用してバイナリツリーを構築するのに役立ちます。

• 「search_elem」という名前のメソッドが定義されており、特定の要素の検索に役立ちます。

• 「BinaryTree_struct」クラスのオブジェクトが作成されます。

• 「construct_btree」メソッドは、以前に指定された要素を取得してバイナリツリーを構築するために使用されます。

• ポストオーダートラバーサルとインオーダートラバーサルはこのツリーで実行されます。

• 関連する出力がコンソールに表示されます。