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

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें एक सूची ढूंढनी होगी जिसमें एक सूची के रूप में रूट का इनऑर्डर ट्रैवर्सल हो। जैसा कि हम जानते हैं कि इनऑर्डर ट्रैवर्सल एक पेड़ में सभी नोड्स को ट्रैवर्स करने का एक तरीका है जहां हम -

• बाएं सबट्री को पुनरावर्ती रूप से पार करें।

• वर्तमान नोड को पार करें।

• पुनरावर्ती रूप से दाएँ उपप्रकार को पार करें।

हमें इस समस्या को पुनरावृत्त रूप से हल करने का प्रयास करना होगा।

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

तो आउटपुट [12,13,4,16,7,14,22]

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

• इनऑर्डर :=एक नई सूची

• स्टैक :=एक खाली स्टैक

• निम्नलिखित को असीम रूप से करें, करें

  • अगर रूट शून्य नहीं है, तो

    • जड़ को ढेर में धकेलें

    • जड़ :=जड़ के बाएँ

  • अन्यथा जब स्टैक खाली न हो, तब

    • जड़:=स्टैक का शीर्ष तत्व और स्टैक से पॉप

    • इनऑर्डर के अंत में रूट का मान डालें

    • जड़ :=जड़ के दाईं ओर

  • अन्यथा,

    • लूप से बाहर आएं

• वापसी क्रम में

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

उदाहरण

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      inorder = []
      stack = []
      while True:
         if root:
            stack.append(root)
            root = root.left
         elif stack:
            root = stack.pop()
            inorder.append(root.val)
            root = root.right
         else:
            break
      return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

इनपुट

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

आउटपुट

[12, 13, 4, 16, 7, 14, 22]