ポストオーダーを使用して深さ優先探索トラバーサルを実装する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 ? insert 9 below 5
What operation would you do ? insert 2 below 9
What operation would you do ? dfs
The post-order traversal is : 5
What operation would you do ? quit

説明

• 必要な属性を持つ「Tree_struct」クラスが作成されます。

• 空のリストを作成するために使用される「init」関数があります。

• ツリーに要素を追加するのに役立つ「add_elem」メソッドがあります。

• ポストオーダートラバーサルを実行する「postorder_traversal」という名前の別のメソッド。

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

• インスタンスが作成され、「なし」に割り当てられます。

• 実行する必要のある操作に対してユーザー入力が行われます。

• ユーザーの選択に応じて、操作が実行されます。

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