BFSトラバーサルを使用してツリーのノードを表示するPythonプログラム

幅優先探索トラバーサルを使用してツリーのノードを表示する必要がある場合、クラスが作成され、ルートノードの設定、ツリーへの要素の追加、特定の要素の検索、'bfs'（幅優先探索）など。これらのメソッドにアクセスして使用するために、クラスのインスタンスを作成できます。

以下は同じのデモンストレーションです-

例

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

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

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

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

   def bfs_operation(self):
      queue = [self]
      while queue != []:
         popped = queue.pop(0)
         for child in popped.children:
            queue.append(child)
         print(popped.key, end=' ')

my_instance = None

print('Menu (assume no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('bfs')
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
      elif suboperation == 'below':
         position = my_input[3].strip().lower()
         key = int(position)
         ref_node = None
         if my_instance is not None:
            ref_node = my_instance.search_node(key)
         if ref_node is None:
            print('No such key')
            continue
         ref_node.add_node(new_node)

   elif operation == 'bfs':
      if my_instance is None:
         print('The tree is empty')
      else:
         print('Breadth First Search traversal is : ', end='')
         my_instance.bfs_operation()
         print()

   elif operation == 'quit':
      break

出力

Menu (assume no duplicate keys)
add <data> at root
add <data> below <data>
bfs
quit
What operation would you do ? add 6 at root
What operation would you do ? add 4 below 6
What operation would you do ? add 9 below 4
What operation would you do ? bfs
Breadth First Search traversal is : 6 4 9
What operation would you do ? quit

説明

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

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

• 二分木のルート値を設定するのに役立つ「set_root」メソッドが定義されています。

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

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

• 「bfs_operation」という名前のメソッドが定義されています。これは、ツリーで幅優先探索トラバーサルを実行するのに役立ちます。

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

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

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

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