पायथन में बाइनरी ट्री इनऑर्डर ट्रैवर्सल

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें रिकर्सन का उपयोग किए बिना इनऑर्डर ट्रैवर्सल स्कीम का उपयोग करके इस पेड़ को पार करना होगा। तो अगर पेड़ ऐसा है

फिर ट्रैवर्सल होगा [2,5,7,10,15,20]

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

• दो ऐरे रेस और स्टैक बनाएं, कर्व सेट करें:=रूट
• एक अनंत लूप चलाएं
  • जबकि करंट शून्य नहीं है
    • कर्फ़ को स्टैक में पुश करें, और curr सेट करें:=curr के बाएँ
  • जब स्टैक की लंबाई =0 हो, तो रेज़ वापस करें
  • नोड:=स्टैक से पॉप किया गया तत्व
  • रेस में नोड का मान डालें
  • curr:=curr का अधिकार

उदाहरण

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

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):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def inorderTraversal(self, root):
      res, stack = [], []
      current = root
      while True:
         while current:
            stack.append(current)
            current = current.left
         if len(stack) == 0:
            return res
         node = stack[-1]
         stack.pop(len(stack)-1)
         if node.data != None:
            res.append(node.data)
         current = node.right
      return res
ob1 = Solution()
root = make_tree([10,5,15,2,7,None,20])
print(ob1.inorderTraversal(root))

इनपुट

[10,5,15,2,7,null,20]

आउटपुट

[2,5,7,10,15,20]