Pythonでリンクリストを使って二分木（バイナリツリー）を実装する方法

リンクリスト（連結リスト）を利用して二分木データ構造を実装するには、以下のようなメソッドを定義するのが一般的です。

• ルートノードを設定するメソッド
• 中順走査（in-order traversal）を行うメソッド
• ルートノードの左側に要素を挿入するメソッド
• ルートノードの右側に要素を挿入するメソッド
• 指定した値を検索するメソッド

以下に、実際の実装例を示します。

サンプルコード

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

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

    def in_order_traversal(self):
        if self.left is not None:
            self.left.in_order_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.in_order_traversal()

    def insert_left(self, new_node):
        self.left = new_node

    def insert_right(self, new_node):
        self.right = new_node

    def search_val(self, key):
        if self.key == key:
            return self
        if self.left is not None:
            temp = self.left.search_val(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp = self.right.search_val(key)
            return temp
        return None

btree = 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('quit')

while True:
    print('The inorder traversal of binary tree ', end='')
    if btree is not None:
        btree.in_order_traversal()
    print()

    do = input('What would you like to do? ').split()

    operation = do[0].strip().lower()
    if operation == 'insert':
        data = int(do[1])
        new_node = BinaryTree_structure(data)
        sub_op = do[2].strip().lower()
        if sub_op == 'at':
            btree = new_node
        else:
            position = do[4].strip().lower()
            key = int(position)
            ref_node = None
            if btree is not None:
                ref_node = btree.search_val(key)
            if ref_node is None:
                print('No such key exists')
                continue
            if sub_op == 'left':
                ref_node.insert_left(new_node)
            elif sub_op == 'right':
                ref_node.insert_right(new_node)
    elif operation == 'quit':
        break

実行結果

Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
quit
The inorder traversal of binary tree
What would you like to do? insert 45 at root
The inorder traversal of binary tree 45
What would you like to do? insert 78 left of 45
The inorder traversal of binary tree 78 45
What would you like to do? insert 90 right of 45
The inorder traversal of binary tree 78 45 90
What would you like to do? quit

コードの解説

• まず、「BinaryTree_structure」というクラスを作成します。このクラスが二分木の各ノードを表します。

• 「set_root」関数は、木のルート（根）となる値を設定するために使用されます。

• 「in_order_traversal」メソッドは、左の子 → 自身のノード → 右の子 の順序で木を再帰的に走査し、各ノードの値を出力します。この順序は「中順走査」と呼ばれ、二分探索木では昇順に値が表示されるのが特徴です。

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

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

• 「search_val」メソッドは、指定されたキーと一致するノードを左部分木・右部分木に対して再帰的に検索し、見つかった場合はそのノードを返します。該当するノードが存在しない場合はNoneを返します。

• ユーザーには「insert at root（ルートに挿入）」「insert to left of（指定ノードの左に挿入）」「insert to right of（指定ノードの右に挿入）」「quit（終了）」という4つの操作メニューが提示されます。

• ユーザーの入力内容に応じて、それぞれ対応する操作が実行されます。なお、このプログラムは重複するキーが存在しないことを前提としています。

• 各操作の結果は、コンソール上に中順走査の結果として随時表示されます。