पायथन में एक बाइनरी ट्री में दो नोड्स के बीच की दूरी का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक बाइनरी ट्री दिया जाता है और हमें बाइनरी ट्री में दो नोड्स के बीच की दूरी का पता लगाने के लिए कहा जाता है। हम दो नोड्स के बीच के किनारों को एक ग्राफ की तरह ढूंढते हैं और किनारों की संख्या या उनके बीच की दूरी को वापस कर देते हैं। पेड़ के नोड की संरचना नीचे दी गई है -

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
  • यदि रूट शून्य के समान है, तो
    • वापसी शून्य
  • यदि रूट का डेटा (p,q) में से कोई है, तो
    • रिटर्न रूट
  • बाएं:=findLca(रूट के बाएं, p, q)
  • दाएं:=findLca(रूट का दायां, p, q)
  • यदि बाएँ और दाएँ रिक्त नहीं हैं, तो
    • रिटर्न रूट
  • बाएं या दाएं लौटें
• एक फ़ंक्शन को परिभाषित करें findDist() । यह जड़ लेगा, डेटा
  • कतार :=एक नया डेक
  • कतार के अंत में एक नया जोड़ा (रूट, 0) डालें
  • जबकि कतार खाली नहीं है, करें
    • वर्तमान :=कतार में सबसे बाईं जोड़ी का पहला मान
    • dist :=कतार में सबसे बाईं जोड़ी का दूसरा मान
    • यदि करंट का डेटा डेटा के समान है, तो
      • वापसी जिला
    • यदि धारा का बायां भाग शून्य नहीं है, तो
      • जोड़ी जोड़ें (वर्तमान के बाईं ओर, जिला+1) को कतार में जोड़ें
    • यदि धारा का अधिकार शून्य नहीं है, तो
      • जोड़ी जोड़ें (current.right, dist+1) को कतार में जोड़ें
• नोड :=findLca(root, p, 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