Chương trình sửa cây nhị phân bị lỗi bằng Python

Giả sử, chúng ta được đưa ra một cây nhị phân có vấn đề; một trong những con trỏ con bên phải của nút trỏ đến một nút khác ở cùng mức trong cây nhị phân một cách sai lầm. Vì vậy, để khắc phục sự cố này, chúng ta phải tìm ra nút có lỗi này và xóa nút đó và con cháu của nó ngoại trừ nút mà nó trỏ đến. Chúng tôi trả về nút gốc của cây nhị phân cố định.

Vì vậy, nếu đầu vào giống như

Chúng ta có thể thấy rằng có một liên kết sai giữa 4 và 6. Con trỏ bên phải của 4 điểm đến 6.

thì kết quả đầu ra, biểu diễn nhỏ hơn của cây đã sửa sẽ là - 2, 3, 5, 6, 7, 8,

Nút 4 bị xóa vì nó có liên kết sai đến nút 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• q:=a new deque chứa root

• p:=một bản đồ mới

• đã ghé thăm:=một tập hợp mới

• trong khi q không trống, thực hiện

  • cur:=pop phần tử ngoài cùng bên trái của q

  • nếu cur có mặt trong lượt truy cập thì

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

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

    • nếu is_left không phải là null, thì

      • bên trái của grand_p:=null

    • nếu không,

      • quyền grand_p:=null

    • trả về thư mục gốc

  • thêm (cur) số lượt truy cập

  • nếu bên trái của cur không phải là null, thì

    • p [left of cur]:=a new tuple (cur, 1)

    • chèn bên trái của cur vào cuối q

  • nếu bên phải của cur không phải là null thì

    • p [right of cur]:=a new tuple (cur, 0)

    • chèn bên phải của cur vào cuối q

• trả về thư mục gốc

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

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