পাইথন ব্যবহার করে একটি বাইনারি গাছের মূল পরিবর্তন করার জন্য প্রোগ্রাম

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

• যদি একটি নোডের একটি বাম সন্তান থাকে, তাহলে এটি ডান সন্তান হয়ে যায়।

• একটি নোডের পিতামাতা তার বাম সন্তান হয়ে ওঠে। এই প্রক্রিয়ায়, সেই নোডের সাথে প্যারেন্ট নোডের লিঙ্কটি শূন্য হয়ে যায়, তাই এটির একটি মাত্র সন্তান থাকবে৷

গাছের নোড গঠন নিচের মত -

TreeNode:
   data: <integer>
   left: <pointer of TreeNode>
   right: <pointer of TreeNode>
   parent: <pointer of TreeNode>

আমাদের রূপান্তরিত গাছের মূল ফিরিয়ে দিতে হবে।

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

এবং নতুন রুট হল 8; তাহলে রূপান্তরিত গাছের ক্রমানুসারে উপস্থাপনা হবে − 2, 3, 4, 5, 7, 6, 8,

গাছের নতুন রুট নোড হল 8.

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

• একটি ফাংশন হেল্পার() সংজ্ঞায়িত করুন। এটি নোড নেবে, new_par

  • যদি নোড রুট হিসাবে একই হয়, তাহলে

    • নোডের মূল :=new_par

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

      • নোডের বাম :=শূন্য

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

      • নোডের ডানদিকে :=শূন্য

    • রিটার্ন রুট

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

    • নোডের ডানদিকে :=নোডের বাম

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

    • নোডের প্যারেন্টের বাম:=শূন্য

  • নোডের বাম :=সাহায্যকারী (নোডের পিতামাতা, নোড)

  • নোডের মূল :=new_par

  • রিটার্ন নোড

• রিটার্ন হেল্পার(লিফ, নাল)

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

উদাহরণ

import collections
class TreeNode:
   def __init__(self, data, left = None, right = None, parent = None):
      self.data = data
      self.left = left
      self.right = right
      self.parent = parent
   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, parent = temp)
            else:
               temp.left = TreeNode(0, parent = temp)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data, parent = temp)
         else:
            temp.right = TreeNode(0, parent = temp)
         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, leaf):
   def helper(node, new_par):
      if node == root:
         node.parent = new_par
         if node.left == new_par:
            node.left = None
         if node.right == new_par:
            node.right = None
         return root
      if node.left:
         node.right = node.left
      if node.parent.left == node:
         node.parent.left = None
      node.left = helper(node.parent, node)
      node.parent = new_par
      return node
   return helper(leaf, None)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))
print_tree(root)

ইনপুট

root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))

আউটপুট

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