บทนำ
Ternary Tree เป็นต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุด 3 ตัว (left, mid, right) การแปลงเป็น Doubly Linked List ทำได้โดย Preorder Traversal (Root → Left → Mid → Right) เชื่อมโหนดเป็น linked list
โค้ดตัวอย่าง
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.mid = None
self.right = None
class TernaryTreeToDLL:
def __init__(self):
self.head = None
self.tail = None
def convert(self, node):
if node is None:
return
# Preorder: Root → Left → Mid → Right
# Process current node
if self.head is None:
self.head = self.tail = node
node.left = None # prev
node.mid = None # clear mid
else:
self.tail.right = node # next
node.left = self.tail # prev
node.mid = None
self.tail = node
# Recurse children (เก็บ reference ก่อนเพราะจะถูกแก้ไข)
left, mid, right = node.left, node.mid, node.right
self.convert(left)
self.convert(mid)
self.convert(right)
# Right child จะถูกต่อท้ายอัตโนมัติจาก recursion
def display(self):
curr = self.head
while curr:
print(curr.data, end=' ')
curr = curr.right
print()
# สร้าง Ternary Tree
root = Node(10)
root.left = Node(14)
root.mid = Node(24)
root.right = Node(17)
root.left.left = Node(22)
root.left.mid = Node(23)
root.mid.left = Node(24)
root.mid.mid = Node(28)
root.mid.right = Node(30)
root.right.left = Node(45)
root.right.mid = Node(50)
root.right.right = Node(80)
# แปลง
converter = TernaryTreeToDLL()
converter.convert(root)
print("Doubly Linked List (Preorder):")
converter.display()
ผลลัพธ์
Doubly Linked List (Preorder): 10 14 22 23 24 24 28 30 17 45 50 80
คำอธิบาย
- ใช้ Preorder traversal: Root → Left → Mid → Right
- แปลง pointer: left→prev, right→next, mid→None
- Head = โหนดแรกที่เจอ (root), Tail = โหนดสุดท้าย
- ต้องเก็บ children references ก่อนเรียก convert() เพราะ pointer จะถูกแก้ไข
โครงสร้าง Tree ตัวอย่าง
10
/ | \
14 24 17
/ \ / \ / \
22 23 24 28 30 45 50 80
