Chương trình tìm ra tổ tiên chung thấp nhất của cây nhị phân bằng cách sử dụng con trỏ cha bằng Python

Giả sử, chúng ta được cung cấp một cây nhị phân và hai nút cụ thể x và y. Chúng ta phải tìm ra tổ tiên chung thấp nhất của hai nút từ cây nhị phân. Tổ tiên chung thấp nhất trong cây nhị phân là nút thấp nhất mà cả hai nút x và y đều là con cháu. Một nút cụ thể cũng có thể là con của chính nó. Chúng tôi phải tìm nút và trả về nó dưới dạng đầu ra.

Cấu trúc nút của cây như dưới đây -

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

Chúng tôi phải sử dụng con trỏ cha trong khi tìm giải pháp.

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

và x =3, y =7; thì đầu ra sẽ là 5.

3 và 7 đều là con cháu của 5 nên câu trả lời sẽ là 5.

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

• path_p_r:=một danh sách mới

• trong khi x không rỗng, thực hiện

  • chèn x vào cuối path_p_r

  • x:=cha của x

• trong khi y không null, thực hiện

  • nếu y có trong path_p_r thì

    • trả lại y

  • y:=cha của y

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

Ví dụ

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 solve(x, y):
   path_p_r = []
   while x:
      path_p_r.append(x)
      x = x.parent
   while y:
      if y in path_p_r:
         return y
      y = y.parent
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)

Đầu vào

[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7

Đầu ra

5