โปรแกรมสร้างรายการเชื่อมโยงไปยังแผนผังการค้นหาไบนารีใน Python

สมมติว่าเรามีโหนดรายการเชื่อมโยงที่เรียงลำดับขนาด n เราต้องสร้างแผนผังการค้นหาแบบไบนารีโดยรับค่าของ k =ชั้นของ (n / 2) การตั้งค่าที่เล็กที่สุดเป็นรูท จากนั้นสร้างทรีย่อยด้านซ้ายซ้ำโดยใช้รายการที่เชื่อมโยงทางด้านซ้ายของโหนด kth และสร้างทรีย่อยที่ถูกต้องซ้ำๆ โดยใช้รายการลิงก์ทางด้านขวาของโหนดที่ k

ดังนั้นหากอินพุตเป็น [2,4,5,7,10,15] ผลลัพธ์จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• กำหนดวิธีการแก้ปัญหา () สิ่งนี้จะใช้โหนด

• หากโหนดเป็นโมฆะ

  • คืนค่า null

• หากโหนดถัดไปเป็นโมฆะ

  • คืนค่าโหนดต้นไม้ใหม่พร้อมค่าของโหนด

• ช้า :=โหนด เร็ว :=โหนด

• ก่อนหน้า :=ไม่มี

• ในขณะที่ fast และ next of fast ไม่เป็นโมฆะ ทำ

  • ก่อนหน้า :=ช้า

  • ช้า :=ถัดจากช้า

  • เร็ว :=ถัดไปของเร็ว

• next of prev :=ไม่มี

• root :=โหนดต้นไม้ใหม่ที่มีค่าช้า

• ทางซ้ายของรูท :=แก้ (โหนด)

• ทางขวาของรูท :=แก้ (ถัดจากช้า)

• คืนค่ารูท

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
return head

def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)

class Solution:
   def solve(self, node):
      if not node:
         return None
      if not node.next:
         return TreeNode(node.val)
      slow = fast = node
      prev = None
      while fast and fast.next:
         prev = slow
         slow = slow.next
         fast = fast.next.next
      prev.next = None
      root = TreeNode(slow.val)
      root.left = self.solve(node)
      root.right = self.solve(slow.next)

      return root

ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)

อินพุต

[2,4,5,7,10,15]

ผลลัพธ์

2, 4, 5, 7, 10, 15,