เมื่อต้องการแปลงไบนารีทรีที่กำหนดให้เป็นรายการที่เชื่อมโยงแบบทวีคูณ จะต้องสร้างคลาส 'โหนด' ในคลาสนี้ มีแอตทริบิวต์ 2 รายการ ได้แก่ ข้อมูลที่มีอยู่ในโหนด และการเข้าถึงโหนดถัดไปของรายการที่เชื่อมโยง
ต้องสร้างคลาส 'linked_list' อีกคลาสหนึ่งซึ่งจะมีฟังก์ชันการเริ่มต้น และส่วนหัวของโหนดจะเริ่มต้นเป็น 'None'
ในรายการที่เชื่อมโยงแบบทวีคูณ โหนดมีตัวชี้ โหนดปัจจุบันจะมีตัวชี้ไปยังโหนดถัดไปและโหนดก่อนหน้า ค่าสุดท้ายในรายการจะมีค่า 'NULL' ในพอยน์เตอร์ถัดไป สามารถเดินทางได้ทั้งสองทิศทาง
ทรีไบนารีเป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น ซึ่งประกอบด้วยโหนดรูทหนึ่งโหนดและทุกโหนด ยกเว้นรูทสามารถมีโหนดหลักได้หนึ่งโหนด โหนดไบนารีทรีสามารถมีลูกได้ไม่เกินสองคน
ผู้ใช้กำหนดวิธีการหลายวิธีในการแปลงไบนารีทรีที่กำหนดให้เป็นรายการที่เชื่อมโยงแบบทวีคูณ และเพื่อพิมพ์ค่าโหนด
ด้านล่างนี้เป็นการสาธิตสำหรับสิ่งเดียวกัน -
ตัวอย่าง
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
คำอธิบาย
- สร้างคลาส 'โหนด' แล้ว
- สร้างคลาสอื่นที่มีคุณสมบัติที่จำเป็นแล้ว
- มีการกำหนดวิธีการอื่นที่ชื่อว่า 'convert_tree_to_list' ซึ่งใช้ในการแปลงไบนารีทรีที่กำหนดให้เป็นรายการที่เชื่อมโยงแบบทวีคูณ
- มีการกำหนดวิธีการอื่นที่เรียกว่า 'print_it' ซึ่งแสดงโหนดของรายการที่เชื่อมโยงแบบวงกลม
- อ็อบเจ็กต์ของคลาส 'binary_tree_to_list' ถูกสร้างขึ้น และมีการเรียกใช้เมธอดในการแปลงทรีเป็นรายการที่เชื่อมโยงเป็นทวีคูณ
- มีการกำหนดวิธีการ 'init' ที่โหนดรูท ส่วนหัว และส่วนท้ายของรายการที่เชื่อมโยงแบบทวีคูณเป็นไม่มี
- มีการเรียกเมธอด 'convert_tree_to_list'
- มันวนซ้ำผ่านไบนารีทรี และแปลงเป็นรายการที่เชื่อมโยงเป็นสองเท่า
- แสดงบนคอนโซลโดยใช้วิธี "print_it"
