เมื่อต้องการแปลงไบนารีทรีที่กำหนดให้เป็นรายการที่เชื่อมโยงแบบทวีคูณ จะต้องสร้างคลาส 'โหนด' ในคลาสนี้ มีแอตทริบิวต์ 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"