โปรแกรมแก้ไขไบนารีทรีที่ผิดพลาดโดยใช้ Python

สมมติว่าเราได้รับไบนารีทรีที่มีปัญหา ตัวชี้ลูกด้านขวาตัวหนึ่งของโหนดชี้ไปยังโหนดอื่นที่ระดับเดียวกันในไบนารีทรีอย่างไม่ถูกต้อง ดังนั้น เพื่อแก้ไขปัญหานี้ เราต้องหาโหนดที่มีข้อผิดพลาดนี้ และลบโหนดนั้นและลูกหลานของโหนดนั้น ยกเว้นโหนดที่ชี้ไปอย่างผิดพลาด เราคืนค่าโหนดรูทของต้นไม้ไบนารีคงที่

ดังนั้นหากอินพุตเป็นแบบ

เราจะเห็นว่ามีการเชื่อมโยงที่ผิดพลาดระหว่าง 4 และ 6 ตัวชี้ลูกด้านขวาของ 4 คะแนนถึง 6

จากนั้นผลลัพธ์ การแสดงความไม่เป็นระเบียบของทรีที่แก้ไขจะเป็น − 2, 3, 5, 6, 7, 8,

โหนด 4 ถูกลบเนื่องจากมีลิงก์ไปยังโหนด 6 ที่ผิดพลาด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• q :=deque ใหม่ที่มีรูท

• p :=แผนที่ใหม่

• เข้าชมแล้ว :=ชุดใหม่

• ในขณะที่ q ไม่ว่างให้ทำ

  • cur :=ป๊อปองค์ประกอบด้านซ้ายสุดของ q

  • ถ้ามี cur อยู่ในการเยี่ยมชมแล้ว

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

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

    • ถ้า is_left ไม่เป็นโมฆะ

      • ซ้ายของ grand_p :=null

    • มิฉะนั้น

      • ด้านขวาของ grand_p :=null

    • คืนค่ารูท

  • เพิ่ม (cur) ของการเยี่ยมชม

  • ถ้า cur เหลือไม่เป็นโมฆะ

    • p[left of cur] :=ทูเพิลใหม่ (cur, 1)

    • แทรกด้านซ้ายของ cur ที่ส่วนท้ายของ q

  • ถ้าสิทธิของเคอร์ไม่เป็นโมฆะ

    • p[right of cur] :=ทูเพิลใหม่ (cur, 0)

    • แทรกด้านขวาของ cur ที่ส่วนท้ายของ q

• คืนค่ารูท

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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,