Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรม Python เพื่อแปลงไบนารีทรีที่กำหนดให้เป็นรายการที่เชื่อมโยงเป็นสองเท่า


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