แปลง Binary Tree เป็น Doubly Linked List ใน Python

บทนำ

การแปลง Binary Tree เป็น Doubly Linked List ทำได้โดย Inorder Traversal (Left → Root → Right) ซึ่งจะได้ลิสต์ที่เรียงลำดับ (ถ้าเป็น BST) หรือตามลำดับ Inorder ของต้นไม้

โค้ดตัวอย่าง

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

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

    def convert(self, node):
        if node is None:
            return
        
        # Inorder: Left → Root → Right
        self.convert(node.left)
        
        # Process current node
        if self.head is None:
            self.head = self.tail = node
            node.left = None
        else:
            self.tail.right = node
            node.left = self.tail
            self.tail = node
        
        self.convert(node.right)

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=' ')
            curr = curr.right
        print()

# สร้าง Binary Tree
root = Node(10)
root.left = Node(14)
root.right = Node(17)
root.left.left = Node(22)
root.left.right = Node(29)
root.right.left = Node(45)
root.right.right = Node(80)

# แปลง
converter = BinaryTreeToDLL()
converter.convert(root)

print("Doubly Linked List (Inorder):")
converter.display()

ผลลัพธ์

Doubly Linked List (Inorder):
22 14 29 10 45 17 80

คำอธิบาย

• Inorder traversal: Left subtree → Root → Right subtree
• แปลง left pointer → prev, right pointer → next
• Head = โหนดซ้ายสุด (Inorder เริ่มต้น), Tail = โหนดขวาสุด
• ถ้าเป็น BST ผลลัพธ์จะเป็น sorted list

โครงสร้าง Tree ตัวอย่าง

        10
       /  \
     14    17
    / \   / \
   22 29 45 80

Inorder: 22, 14, 29, 10, 45, 17, 80

ความแตกต่าง Ternary vs Binary