Pythonで二分木の最大値を求める！中順走査（In-order Traversal）を使った実装方法

木構造（ツリー）の中から最大値を求めたい場合には、二分木クラスを作成し、「根要素を設定するメソッド」「再帰を用いて中順走査（インオーダートラバーサル）を行うメソッド」などを定義しておくと便利です。

クラスのインスタンスを生成すれば、これらのメソッドにアクセスして自由に利用できるようになります。

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

中順走査（In-order Traversal）とは

中順走査とは、二分木を巡回する代表的な手法の一つで、「左の子ノード → 自分自身（親ノード） → 右の子ノード」の順番で各ノードを訪問します。本記事では、この走査の過程で訪れたノードの値を順次比較することで、木全体の最大値を求めています。

サンプルコード

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_largest(self):
        largest = []
        self.inorder_largest_helper_fun(largest)
        return largest[0]

    def inorder_largest_helper_fun(self, largest):
        if self.left is not None:
            self.left.inorder_largest_helper_fun(largest)
        if largest == []:
            largest.append(self.key)
        elif largest[0] < self.key:
            largest[0] = self.key
        if self.right is not None:
            self.right.inorder_largest_helper_fun(largest)

    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
        temp = None
        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

my_instance = None

print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('largest')
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 == 'largest':
        if my_instance is None:
            print('The tree is empty')
        else:
            print('The largest element is : {}'.format(my_instance.inorder_traversal_largest()))

    elif operation == 'quit':
        break

実行結果

Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
largest
quit
What operation would you do ? insert 8 at root
What operation would you do ? insert 9 left of 8
What operation would you do ? insert 4 right of 8
What operation would you do ? largest
The largest element is : 9
What operation would you do ? quit

コードの解説

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

• __init__（イニシャライザ）は、左ノードと右ノードを「None」で初期化する役割を担います。

• 「set_root」メソッドは、二分木の根（ルート）の値を設定するために使用します。

• 「inorder_traversal_largest」メソッドは、再帰処理によって中順走査を実行し、最大値を返します。

• 実際の走査処理は、補助関数（ヘルパー関数）である「inorder_largest_helper_fun」が担当します。リストの先頭要素に常に現時点での最大値を保持し続けることで、走査完了時に最大値だけが残る仕組みです。

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

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

• 「search_elem」メソッドは、キーを指定して該当するノードを探索するために定義されています。

• 「BinaryTree_Struct」クラスのオブジェクトを生成し、操作対象となる木として扱います。

• whileループにより、ユーザーから実行したい操作を対話形式で受け取ります。

• 入力されたコマンド（insert / largest / quit）に応じて、それぞれ対応する処理が実行されます。

• 処理結果はコンソールに出力され、「quit」が入力されるまで操作を繰り返すことができます。

計算量について

この方法では、最大値を確定させるためにすべてのノードを一度ずつ訪問する必要があるため、時間計算量はO(n)（nはノード数）となります。なお、木が二分探索木（BST）である場合は、中順走査を行うと値が昇順に並ぶという性質があるため、最後に訪問するノードの値がそのまま最大値になります。