Chương trình tìm khoảng cách giữa hai nút trong cây nhị phân bằng Python

Giả sử, chúng ta được cung cấp một cây nhị phân và được yêu cầu tìm khoảng cách giữa hai nút trong cây nhị phân. Chúng tôi tìm ra các cạnh giữa hai nút giống như trong một đồ thị và trả về số cạnh hoặc khoảng cách giữa chúng. Một nút của cây có cấu trúc như sau -

data : <integer value>
right : <pointer to another node of the tree>
left : <pointer to another node of the tree>

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

và các nút mà chúng ta phải tìm khoảng cách giữa là 2 và 8; thì đầu ra sẽ là 4.

Các cạnh giữa hai nút 2 và 8 là:(2, 3), (3, 5), (5, 7) và (7, 8). Có 4 cạnh trên đường đi giữa chúng, vì vậy khoảng cách là 4.

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

• Xác định một hàm findLca (). Điều này sẽ bắt nguồn từ gốc, p, q
  • nếu root giống với null, thì
    • trả về null
  • nếu dữ liệu của gốc là bất kỳ trong số (p, q), thì
    • trả về thư mục gốc
  • left:=findLca (left of root, p, q)
  • right:=findLca (bên phải gốc, p, q)
  • nếu trái và phải không rỗng, thì
    • trả về thư mục gốc
  • quay lại trái hoặc phải
• Xác định một hàm findDist (). Điều này sẽ root, dữ liệu
  • queue:=a new deque
  • chèn một cặp mới (gốc, 0) vào cuối hàng đợi
  • trong khi hàng đợi không trống, hãy thực hiện
    • current:=giá trị đầu tiên của cặp ngoài cùng bên trái trong hàng đợi
    • dist:=giá trị thứ hai của cặp ngoài cùng bên trái trong hàng đợi
    • nếu dữ liệu hiện tại giống với dữ liệu, thì
      • return dist
    • nếu left of current không phải là null, thì
      • thêm cặp (bên trái hiện tại, dist + 1) vào hàng đợi
    • nếu quyền hiện tại không rỗng, thì
      • thêm cặp (current.right, dist + 1) vào hàng đợi
• nút:=findLca (root, p, q)
• trả về findDist (node, p) + findDist (node, q)

Ví dụ

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

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 findLca(root, p, q):
   if root is None:
      return None
   if root.data in (p,q):
      return root
   left = findLca(root.left, p, q)
   right = findLca(root.right, p, q)
   if left and right:
      return root
   return left or right

def findDist(root, data):
   queue = collections.deque()
   queue.append((root, 0))
   while queue:
      current, dist = queue.popleft()
      if current.data == data:
         return dist
      if current.left: queue.append((current.left, dist+1))
      if current.right: queue.append((current.right, dist+1))

def solve(root, p, q):
   node = findLca(root, p, q)
   return findDist(node, p) + findDist(node, q)

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

Đầu vào

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

Đầu ra

4