পাইথন ব্যবহার করে একটি ভুল বাইনারি ট্রি ঠিক করার জন্য প্রোগ্রাম

ধরুন, আমাদেরকে একটি বাইনারি গাছ দেওয়া হল যাতে সমস্যা আছে; নোডের একটি ডান চাইল্ড পয়েন্টার ভুলভাবে বাইনারি গাছের একই স্তরে অন্য নোডের দিকে নির্দেশ করে। সুতরাং, এই সমস্যাটি সমাধান করার জন্য, আমাদের এই ত্রুটিটি আছে এমন নোডটি খুঁজে বের করতে হবে এবং সেই নোডটি এবং এটির উত্তরসূরিগুলিকে মুছে ফেলতে হবে যে নোডটি ভুলভাবে নির্দেশ করছে। আমরা ফিক্সড বাইনারি ট্রির রুট নোড ফেরত দিই।

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

আমরা দেখতে পাচ্ছি যে 4 এবং 6 এর মধ্যে একটি ভুল লিঙ্ক রয়েছে৷ 4 থেকে 6 পয়েন্টের সঠিক চাইল্ড পয়েন্টার৷

তারপর আউটপুট, সংশোধন করা গাছের অভ্যন্তরীণ উপস্থাপনা হবে − 2, 3, 5, 6, 7, 8,

নোড 4 মুছে ফেলা হয়েছে কারণ এটিতে নোড 6 এর সাথে একটি ভুল লিঙ্ক রয়েছে।

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

• q :=রুট ধারণকারী একটি নতুন ডিক

• p :=একটি নতুন মানচিত্র

• পরিদর্শন করেছেন :=একটি নতুন সেট

• q খালি না থাকার সময়, করুন

  • cur :=q

    এর বামতম উপাদান পপ করুন

  • যদি cur পরিদর্শন করা হয়, তাহলে

    • is_left :=p[p[cur, 0]]

    • grand_p :=p[p[cur, 0]]

    • যদি is_left শূন্য না হয়, তাহলে

      • grand_p এর বাম :=শূন্য

    • অন্যথায়,

      • grand_p এর ডান :=শূন্য

    • রিটার্ন রুট

  • পরিদর্শন করা যোগ(cur)

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

    • p[cur এর বামে] :=একটি নতুন টিপল (cur, 1)

    • q

      এর শেষে cur এর বাম দিকে সন্নিবেশ করুন

  • যদি cur এর ডান শূন্য না হয়, তাহলে

    • p[cur এর ডান] :=একটি নতুন টিপল (cur, 0)

    • q

      এর শেষে cur এর ডানদিকে সন্নিবেশ করুন

• রিটার্ন রুট

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

উদাহরণ

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):
   q = collections.deque([root])
   p, visited = dict(), set()
   while q:
      cur = q.popleft()
      if cur in visited:
         grand_p, is_left = p[p[cur][0]]
         if is_left: grand_p.left = None
            else: grand_p.right = None
            return root
      visited.add(cur)
      if cur.left:
         p[cur.left] = (cur, 1)
         q.append(cur.left)
      if cur.right:
         p[cur.right] = (cur, 0)
         q.append(cur.right)
   return root
root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to
print_tree(solve(root))

ইনপুট

root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to

আউটপুট

2, 3, 5, 6, 7, 8,