পাইথন ব্যবহার করে প্রদত্ত নোডের একটি বাইনারি গাছের সর্বনিম্ন সাধারণ পূর্বপুরুষ খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে এবং গাছের সমস্ত নোডের সর্বনিম্ন সাধারণ পূর্বপুরুষ খুঁজে বের করতে বলা হয়েছে। একটি বাইনারি গাছের সর্বনিম্ন সাধারণ পূর্বপুরুষ হল সর্বনিম্ন নোড যার মধ্যে x1, x2, x3,...., xn হল বংশধর। একটি নির্দিষ্ট নোড নিজেই একটি বংশধর হতে পারে। আমাদের নোডটি খুঁজে বের করতে হবে এবং এটিকে আউটপুট হিসাবে ফেরত দিতে হবে। ইনপুটগুলি হল গাছের মূল নোড এবং নোডগুলির তালিকা যা আমাদের পূর্বপুরুষ খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুট মত হয়

এবং নোডগুলির তালিকা যা আমাদের পূর্বপুরুষদের খুঁজে বের করতে হবে [6, 8]; তাহলে আউটপুট হবে 7.

আউটপুট হল 7, কারণ সর্বনিম্ন নোড যার মধ্যে নোড 6 এবং 8 এর বংশধর হল 7৷

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

• একটি ফাংশন fn() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে

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

    • রিটার্ন নোড

  • অন্যথায় যখন নোড নোডগুলিতে প্রিসেট করা হয়, তখন

    • রিটার্ন নোড

  • left :=fn (নোডের বাম দিকে),

  • ডান :=fn(নোডের ডানদিকে)

  • যদি বাম এবং ডান শূন্য না হয়, তাহলে

    • রিটার্ন নোড

  • অন্যথায়,

    • যদি বাম বা ডান শূন্য না হয়, তাহলে

      • রিটার্ন নোড

• নোডস :=একটি নতুন তালিকা

• node_list এ প্রতিটি উপাদানের জন্য, করুন

  • নোডের শেষে search_node(root, elem) সন্নিবেশ করুন

• নোডস :=নোড থেকে একটি নতুন সেট

• ফেরত fn(root)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

import collections
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
def search_node(root, element):
   if (root == None):
      return None
   if (root.data == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
def solve(root, node_list):
   nodes = []
   for elem in node_list:
      nodes.append(search_node(root, elem))
      nodes = set(nodes)
def fn(node):
   if not node:
      return node
   elif node in nodes:
      return node
      left, right = fn(node.left), fn(node.right)
      return node if left and right else left or right
   return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6,8]).data)

ইনপুট

make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]

আউটপুট

7