โปรแกรมหาระยะห่างระหว่างสองโหนดในไบนารีทรีใน Python

สมมติว่าเราได้รับไบนารีทรีและขอให้ค้นหาระยะห่างระหว่างสองโหนดในไบนารีทรี เราหาขอบระหว่างโหนดทั้งสองเหมือนในกราฟและคืนค่าจำนวนขอบหรือระยะห่างระหว่างโหนดทั้งสอง โหนดของต้นไม้มีโครงสร้างดังนี้ −

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

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

และโหนดระหว่างที่เราต้องหาระยะห่างระหว่างคือ 2 ถึง 8; แล้วผลลัพธ์จะเป็น 4

ขอบระหว่างสองโหนด 2 และ 8 คือ:(2, 3), (3, 5), (5, 7) และ (7, 8) มี 4 ขอบในเส้นทางระหว่างพวกเขา ดังนั้นระยะทางคือ 4

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

• กำหนดฟังก์ชัน findLca() สิ่งนี้จะทำการรูท p, q
  • ถ้า root เหมือนกับ null แล้ว
    • คืนค่า null
  • ถ้าข้อมูลของรูทเป็นใดๆ ของ (p,q) แล้ว
    • คืนราก
  • left :=findLca(left of root, p, q)
  • ขวา :=findLca(ทางขวาของรูท, p, q)
  • ถ้าซ้ายและขวาไม่เป็นโมฆะ
    • คืนราก
  • กลับซ้ายหรือขวา
• กำหนดฟังก์ชัน findDist() สิ่งนี้จะทำการรูท data
  • คิว :=เดคใหม่
  • ใส่คู่ใหม่ (root, 0) ที่ท้ายคิว
  • ขณะที่คิวไม่ว่างให้ทำ
    • ปัจจุบัน :=ค่าแรกของคู่ซ้ายสุดในคิว
    • dist :=ค่าที่สองของคู่ซ้ายสุดในคิว
    • ถ้าข้อมูลปัจจุบันเหมือนกับข้อมูลแล้ว
      • คืนสินค้า
    • ถ้ากระแสที่เหลือไม่เป็นโมฆะ
      • เพิ่มคู่ (ด้านซ้ายของปัจจุบัน dist+1) ให้กับคิว
    • ถ้ากระแสไฟไม่เป็นโมฆะ
      • เพิ่มคู่ (current.right, dist+1) ให้กับคิว
• โหนด :=findLca(root, p, q)
• ส่งคืน findDist(โหนด, p) + findDist(โหนด, 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 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))

อินพุต

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

ผลลัพธ์

4