पायथन का उपयोग करके एक गलत बाइनरी ट्री को ठीक करने का कार्यक्रम

मान लीजिए, हमें एक बाइनरी ट्री दिया गया है जिसमें कोई समस्या है; नोड के दाहिने चाइल्ड पॉइंटर में से एक बाइनरी ट्री में समान स्तर पर दूसरे नोड को गलत तरीके से इंगित करता है। इसलिए, इस समस्या को ठीक करने के लिए, हमें उस नोड का पता लगाना होगा जिसमें यह त्रुटि है और उस नोड और उसके वंशज को उस नोड को छोड़कर हटाना होगा जिसे वह गलती से इंगित कर रहा है। हम फिक्स्ड बाइनरी ट्री का रूट नोड लौटाते हैं।

तो, अगर इनपुट पसंद है

हम देख सकते हैं कि 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 के बाएँ :=null

    • अन्यथा,

      • Grand_p का अधिकार:=शून्य

    • वापसी जड़

  • देखे गए का जोड़ें(cur)

  • यदि वक्र का बायां भाग शून्य नहीं है, तो

    • p[बाएं वक्र] :=एक नया टपल (cur, 1)

    • क्यू के अंत में वक्र के बाईं ओर डालें

  • यदि वक्र का अधिकार शून्य नहीं है, तो

    • p[दायां वक्र] :=एक नया टपल (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,