पायथन का उपयोग करके बाइनरी ट्री में दाईं ओर नोड का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक बाइनरी ट्री प्रदान किया जाता है। हमें एक नोड ('u' नाम दिया गया) के लिए एक पॉइंटर भी दिया जाता है और हमें दिए गए नोड के ठीक दाईं ओर स्थित नोड को खोजना होता है। दिए गए नोड के दाईं ओर स्थित नोड समान स्तर पर रहना चाहिए और दिया गया नोड या तो लीफ नोड या आंतरिक नोड हो सकता है।

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

और u =6, तो आउटपुट 8 होगा।

नोड 6 के दाईं ओर स्थित नोड नोड 8 है, इसलिए मान 8 हमें वापस कर दिया जाता है।

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

• अगर रूट खाली है, तो

  • वापसी शून्य

• dq :=एक नया डेक

• dq के अंत में रूट डालें

• जबकि dq खाली नहीं है, करें

  • dq_size :=dq का आकार

  • अस्थायी:=एक नई सूची

  • सूचकांक :=-1

  • 0 से dq_size तक के प्रत्येक मान के लिए, करें

    • नोड:=डीक्यू से अंतिम तत्व हटाएं

    • यदि नोड का बायां भाग खाली नहीं है, तो

      • नोड के बाईं ओर dq के अंत में जोड़ें

    • यदि नोड का दाहिना भाग खाली नहीं है, तो

      • dq के अंत में नोड के दाईं ओर जोड़ें

    • अस्थायी के अंत में नोड डालें

    • यदि नोड आपके जैसा ही है, तो

      • अनुक्रमणिका :=तापमान का आकार - 1

  • यदि सूचकांक अस्थायी -1 के आकार के समान है, तो

    • वापसी शून्य

  • अगर अनुक्रमणिका> -1, तो

    • वापसी अस्थायी [सूचकांक + 1]

• वापसी शून्य

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

उदाहरण

from queue import deque
class TreeNode:
   def __init__(self, val=0, left=None, right=None):
      self.val = val
      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.val == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def solve(root, u):
   if not root:
      return None
   dq = deque()
   dq.append(root)
   while dq:
      dq_size = len(dq)
      temp = []
      index = -1
      for _ in range(dq_size):
         node = dq.pop()
         if node.left:
            dq.appendleft(node.left)
         if node.right:
            dq.appendleft(node.right)
         temp.append(node)
         if node == u:
            index = len(temp) - 1
      if index == len(temp) - 1:
         return None
      if index > -1:
         return temp[index + 1]
   return None
root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root,6)
ret = solve(root, u)
print(ret.val)

इनपुट

root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root,6)

आउटपुट

8