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

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

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

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

• दो सरणी res और stack बनाएं, curr := root सेट करें
• एक अनंत लूप चलाएं
  • जब तक current null नहीं है
    • curr को स्टैक में पुश करें, और curr := curr का लेफ्ट सेट करें
  • जब स्टैक की लंबाई = 0 हो, तो res लौटाएं
  • node := स्टैक से पॉप किया गया तत्व
  • node के मान को res में डालें
  • curr := node का राइट

उदाहरण

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

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]