Pythonで二分木を双方向リンクリストに変換する方法｜サンプルコード付き解説

二分木を双方向リンクリスト(ダブルリンクリスト)へ変換するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータ(data)と、隣接するノードへの参照(left・right)という属性を持たせます。

続いて、初期化用の関数を持つリンクリスト管理クラスを作成し、ヘッド(head)を「None」で初期化します。

双方向リンクリストとは

双方向リンクリストでは、各ノードが前後両方向へのポインタを持ちます。現在のノードは「次のノードへのポインタ」と「前のノードへのポインタ」の両方を保持しており、リスト末尾のノードはnextポインタに「NULL(None)」を格納します。この構造により、リストを前方・後方のどちらの方向からでも走査できるのが大きな特徴です。

二分木とは

二分木は非線形データ構造の一種で、1つのルートノードを頂点とし、ルート以外のすべてのノードは必ず1つの親ノードを持ちます。また、各ノードが持てる子ノードの数は最大2つまでという制約があります。

実装の方針

二分木を双方向リンクリストに変換するためのメソッドと、ノードの値を出力するメソッドをそれぞれ定義します。変換処理では、木を「通りがけ順(in-order)」で走査しながら、訪問したノードを順番にリストの末尾へ連結していくことで、整列された双方向リンクリストを構築できます。

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

サンプルコード

class Node:
    def __init__(self, my_data):
        self.right = None
        self.data = my_data
        self.left = None


class binary_tree_to_list:
    def __init__(self):
        self.root = None
        self.head = None
        self.tail = None

    def convert_tree_to_list(self, node_val):
        if node_val is None:
            return
        self.convert_tree_to_list(node_val.left)
        if self.head == None:
            self.head = self.tail = node_val
        else:
            self.tail.right = node_val
            node_val.left = self.tail
            self.tail = node_val
        self.convert_tree_to_list(node_val.right)

    def print_it(self):
        curr = self.head
        if self.head == None:
            print("The list is empty")
            return
        print("The nodes are :")
        while curr != None:
            print(curr.data)
            curr = curr.right


my_instance = binary_tree_to_list()
print("Elements are being added to the list")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.right = Node(29)
my_instance.root.right.left = Node(45)
my_instance.root.right.right = Node(80)
my_instance.convert_tree_to_list(my_instance.root)
my_instance.print_it()

実行結果

Elements are being added to the list
The nodes are :
22
14
29
10
45
17
80

コードの解説

• まず、ノードのデータと左右の子への参照を保持する「Node」クラスを作成します。
• 次に、必要な属性を持つ「binary_tree_to_list」クラスを定義します。
• 「__init__」メソッドでは、二分木のルート(root)、およびリンクリストの先頭(head)と末尾(tail)をすべて「None」で初期化します。
• 「convert_tree_to_list」メソッドは、二分木を通りがけ順で再帰的に走査し、訪問したノードを順に双方向リンクリストへ連結していきます。
• 「print_it」メソッドは、headから順にノードをたどりながら、リンクリスト内の各ノードの値を表示します。
• 「binary_tree_to_list」クラスのインスタンスを生成し、二分木を構築したうえで「convert_tree_to_list」メソッドを呼び出します。
• このメソッドが二分木全体を走査して双方向リンクリストへの変換を行い、その結果が「print_it」メソッドによってコンソールに出力されます。

このように、通りがけ順の走査を利用することで、二分木のノードを昇順に並べた双方向リンクリストへ簡単に変換できます。特に二分探索木(BST)に対して適用すれば、ソート済みのリンクリストが得られる点も覚えておくと便利です。