Pythonで三分木（三項木）から双方向連結リストを作成する方法

三分木（各ノードが最大3つの子ノードを持つ木構造）を双方向連結リストに変換するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードに格納されるデータと、left（左）・mid（中央）・right（右）の子ノードへの参照という属性を持たせます。

続いて、初期化処理を行う「ternary_tree_to_list」クラスを作成します。このクラスでは、ルート（root）、先頭（head）、末尾（tail）の各ポインタを「None」で初期化します。

双方向連結リストとは

双方向連結リストでは、各ノードが前後両方のノードへのポインタを持ちます。現在のノードは、次のノードへのポインタと前のノードへのポインタの両方を保持しています。また、リストの末尾ノードのnextポインタには「NULL」（PythonではNone）が設定されます。この構造により、リストを前方・後方のどちらの方向からでも走査できる点が大きな特徴です。

ここでは、与えられた三分木を双方向連結リストへ変換するメソッドと、ノードの値を出力するメソッドを定義します。以下にその実装例を示します。

サンプルコード

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

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

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

    def print_it(self):
        curr = self.head
        if self.head == None:
            print("リストは空です")
            return
        print("ノードの値:")
        while curr != None:
            print(curr.data)
            curr = curr.right

my_instance = ternary_tree_to_list()
print("要素をリストに追加しています")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.mid = Node(24)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.mid = Node(23)
my_instance.root.mid.left = Node(24)
my_instance.root.mid.mid = Node(28)
my_instance.root.mid.right = Node(30)
my_instance.root.right.left = Node(45)
my_instance.root.right.mid = Node(50)
my_instance.root.right.right = Node(80)
my_instance.convert_ternary_tree_to_list(my_instance.root)
my_instance.print_it()

出力結果

要素をリストに追加しています
ノードの値:
10
14
22
23
24
24
28
30
17
45
50
80

コードの解説

• まず「Node」クラスを作成します。各ノードはデータ本体と、left・mid・rightの3つの子ノードへの参照を持ちます。
• 次に、必要な属性を備えた「ternary_tree_to_list」クラスを作成します。
• 「__init__」メソッドでは、root・head・tailの各ノードをNoneに初期化します。
• 「convert_ternary_tree_to_list」メソッドを定義し、三分木を再帰的に走査して双方向連結リストへ変換します。headが未設定の場合は最初のノードとして登録し、以降のノードはtailの後ろに順次接続していきます。
• 子ノードは左・中央・右の順番で再帰的に処理されるため、木全体がリストの順序に反映されます。
• 「print_it」メソッドを定義し、変換後の連結リストの各ノードの値を表示します。リストが空の場合はその旨のメッセージを出力します。
• 「ternary_tree_to_list」クラスのインスタンスを生成し、三分木を構築したうえで変換メソッドを呼び出します。
• 最後に「print_it」メソッドを使って、変換結果をコンソールに出力します。