BFS（幅優先探索）で二分木のミラーコピーを作成して表示するPythonプログラム

木構造のミラーコピー（左右を反転させた複製）を作成し、それを幅優先探索（BFS）で表示したいケースは少なくありません。本記事では、ルート要素の設定、左側の子ノードへの挿入、右側の子ノードへの挿入、特定要素の検索、BFS走査などを行うメソッドを備えた二分木クラスを定義します。クラスのインスタンスを生成すれば、これらのメソッドを自由に呼び出せるようになります。

以下に具体的な実装例を示します。

サンプルコード

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_to_left(self, new_node):
        self.left = new_node

    def insert_to_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 copy_mirror(self):
        mirror = BinaryTree_struct(self.key)
        if self.right is not None:
            mirror.left = self.right.copy_mirror()
        if self.left is not None:
            mirror.right = self.left.copy_mirror()
        return mirror

    def bfs(self):
        queue = [self]
        while queue != []:
            popped = queue.pop(0)
            if popped.left is not None:
                queue.append(popped.left)
            if popped.right is not None:
                queue.append(popped.right)
            print(popped.key, end=' ')

my_instance = None

print('Menu (this assumes no duplicate keys)')
print('insert  at root')
print('insert  left of ')
print('insert  right of ')
print('mirror')
print('quit')

while True:
    my_input = input('What operation would you do ? ').split()

    operation = my_input[0].strip().lower()
    if operation == 'insert':
        data = int(my_input[1])
        new_node = BinaryTree_struct(data)
        suboperation = my_input[2].strip().lower()
        if suboperation == 'at':
            my_instance = new_node
        else:
            position = my_input[4].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
            if suboperation == 'left':
                ref_node.insert_to_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_to_right(new_node)

    elif operation == 'mirror':
        if my_instance is not None:
            print('Creating a mirror copy...')
            mirror = my_instance.copy_mirror()
            print('The breadth first search traversal of original tree is : ')
            my_instance.bfs()
            print()
            print('The breadth first traversal of mirror is : ')
            mirror.bfs()
            print()
    elif operation == 'quit':
        break

実行結果

Menu (this assumes no duplicate keys)
insert  at root
insert  left of 
insert  right of 
mirror
quit
What operation would you do ? insert 6 at root
What operation would you do ? insert 9 left of 6
What operation would you do ? insert 4 right of 6
What operation would you do ? mirror
Creating a mirror copy...
The breadth first search traversal of original tree is :
6 9 4
The breadth first traversal of mirror is :
6 4 9
What operation would you do ?quit
Use quit() or Ctrl-D (i.e. EOF) to exit

解説

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

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

• 「set_root」メソッドは、ルートノードに値を設定するために使用します。

• 「insert_to_left」メソッドは、木の左側のノードに要素を追加します。

• 「insert_to_right」メソッドは、木の右側のノードに要素を追加します。

• 「search_elem」メソッドは、指定した値を持つ要素を再帰的に検索します。

• 「copy_mirror」メソッドは、元の二分木を左右反転させたコピーを再帰的に生成します。

• 「bfs」メソッドは、キューを利用して木全体を幅優先順序で走査し、各ノードの値を出力します。

• インスタンスを生成し、初期状態として「None」を代入しておきます。

• ユーザーから実行したい操作の入力を受け付けます。

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

• 処理結果がコンソールに表示されます。

なお、「copy_mirror」メソッドは各ノードごとに左右の子を入れ替えながら新しいノードを生成していくため、ノード数を n とすると計算量は O(n) になります。また、「bfs」メソッドではリストの pop(0) を使っていますが、ノード数が多い場合は標準ライブラリの collections.deque を使い popleft() で取り出すと O(1) で操作でき、より効率的に動作します。