【Python】二分木の左側の部分木（サブツリー）のノードのみを出力するプログラム

二分木（バイナリツリー）の左側の部分木（サブツリー）に含まれるノードだけを出力したい場合、ルートノードの設定、中順走査（in-order traversal）の実行、ルートノードの右側・左側への要素の挿入など、必要な操作をメソッドとして持つクラスを作成するのが効果的です。クラスのインスタンスを生成し、それらのメソッドを呼び出すことで、目的の処理を簡単に実現できます。

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

サンプルコード

class BinaryTree_struct:
    def __init__(self, data=None):
        self.key = data
        self.left = None
        self.right = None

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

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

    def insert_at_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 print_left_part(self):
        if self.left is not None:
            self.left.inorder_traversal()

my_instance = None

print('メニュー（キーの重複は想定していません）')
print('insert <データ> at root')
print('insert <データ> left of <データ>')
print('insert <データ> right of <データ>')
print('left')
print('quit')

while True:
    my_input = input('実行する操作を入力してください : ').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('そのキーは存在しません')
                continue
            if suboperation == 'left':
                ref_node.insert_at_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_at_right(new_node)

    elif operation == 'left':
        print('左側の部分木のノード : ', end='')
        if my_instance is not None:
            my_instance.print_left_part()
            print()

    elif operation == 'quit':
        break

実行結果

メニュー（キーの重複は想定していません）
insert <データ> at root
insert <データ> left of <データ>
insert <データ> right of <データ>
left
quit
実行する操作を入力してください : insert 5 at root
実行する操作を入力してください : insert 6 left of 5
実行する操作を入力してください : insert 8 right of 5
実行する操作を入力してください : left
左側の部分木のノード : 6 
実行する操作を入力してください : quit

解説

• 必要な属性を持つ「BinaryTree_struct」クラスを作成します。
• 「__init__」コンストラクタで、左右の子ノードを「None」に初期化します。
• 「set_root」メソッドは、二分木のルートの値を設定するために使用します。
• 「insert_at_right」メソッドは、ツリーの右側のノードに要素を追加します。
• 「insert_at_left」メソッドは、ツリーの左側のノードに要素を追加します。
• 「inorder_traversal」メソッドは、木を中順（左→根→右）で走査し、ノードの値を出力します。
• 「search_elem」メソッドは、指定したキーを持つノードを再帰的に検索します。
• 「print_left_part」メソッドは、ルートの左の子ノードに対して「inorder_traversal」を呼び出すことで、左側の部分木のノードだけをコンソールに表示します。ルート自身や右側の部分木は出力されない点がポイントです。
• インスタンス変数「my_instance」を「None」で初期化します。
• ユーザーから実行したい操作を入力として受け取ります。
• 入力されたコマンドに応じて挿入・表示・終了の各処理が実行され、結果がコンソールに出力されます。

このように、クラスベースで二分木を構築しておけば、部分的な走査や表示といった柔軟な操作も簡単に追加できます。木構造を扱うプログラムでは、走査の単位（全体か部分か）を意識してメソッドを設計することが重要です。