पायथन का उपयोग करके पैरेंट पॉइंटर्स का उपयोग करके बाइनरी ट्री के सबसे कम सामान्य पूर्वज का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक बाइनरी ट्री दिया गया है और दो विशिष्ट नोड x और y भी दिए गए हैं। हमें बाइनरी ट्री से दो नोड्स के सबसे कम सामान्य पूर्वज का पता लगाना है। बाइनरी ट्री में सबसे कम सामान्य पूर्वज सबसे निचला नोड होता है, जिसमें दोनों नोड x और y वंशज होते हैं। एक विशेष नोड स्वयं का वंशज भी हो सकता है। हमें नोड ढूंढना है और इसे आउटपुट के रूप में वापस करना है।

पेड़ की नोड संरचना नीचे की तरह है -

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

समाधान खोजने के लिए हमें पैरेंट पॉइंटर का उपयोग करना होगा।

तो, अगर इनपुट पसंद है

और एक्स =3, वाई =7; तो आउटपुट 5 होगा।

3 और 7 दोनों 5 के वंशज हैं, इसलिए उत्तर 5 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• path_p_r :=एक नई सूची

• जबकि x रिक्त नहीं है, करें

  • path_p_r के अंत में x डालें

  • x :=x का जनक

• जबकि y रिक्त नहीं है, करें

  • अगर y path_p_r में मौजूद है, तो

    • वापसी y

  • y :=y के माता-पिता

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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)

इनपुट

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

आउटपुट

5