পাইথনে বাইনারি অনুসন্ধান গাছের সাথে লিঙ্কযুক্ত তালিকা তৈরি করার প্রোগ্রাম

ধরুন আমাদের n আকারের একটি সাজানো লিঙ্কযুক্ত তালিকা নোড আছে, আমাদেরকে (n / 2) এর k =ফ্লোরের মানটি রুট হিসাবে সেট করে একটি বাইনারি অনুসন্ধান ট্রি তৈরি করতে হবে। তারপর kth নোডের বামে লিঙ্ক করা তালিকা ব্যবহার করে বাম সাবট্রিকে পুনরাবৃত্তিমূলকভাবে তৈরি করা হচ্ছে। এবং kth নোডের ডানদিকে লিঙ্ক করা তালিকা ব্যবহার করে পুনরাবৃত্তভাবে ডান সাবট্রি তৈরি করা।

সুতরাং, যদি ইনপুটটি [2,4,5,7,10,15] এর মত হয়, তাহলে আউটপুট হবে

এটি সমাধান করার জন্য, আমরা এই পদক্ষেপগুলি অনুসরণ করব—

• একটি পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি নোড গ্রহণ করবে

• যদি নোড নাল হয়, তাহলে

  • রিটার্ন নাল

• যদি নোডের পরেরটি নাল হয়, তাহলে

  • নোডের মান সহ একটি নতুন ট্রি নোড ফেরত দিন

• ধীর :=নোড, দ্রুত :=নোড

• পূর্ববর্তী :=কোনোটিই নয়

• ফাস্ট এবং ফাস্টের পরবর্তী শূন্য না হলে, করুন

  • পূর্ববর্তী :=ধীরে

  • স্লো :=স্লো এর পরের

  • দ্রুত :=ফাস্টের পরবর্তী

• আগেরটির পরের :=কোনোটিই নয়

• 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,