Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

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

मान लीजिए हमारे पास एक बाइनरी ट्री का इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से ट्री उत्पन्न करना है। इसलिए यदि पोस्टऑर्डर और इनऑर्डर अनुक्रम [9,15,7,20,3] और [9,3,15,20,7] हैं, तो ट्री होगा -

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

आइए चरण देखते हैं -

  • मान लीजिए मेथड को buildTree कहा जाता है जिसमें प्रीऑर्डर और इनऑर्डर लिस्ट हैं
  • root := पोस्टऑर्डर से अंतिम नोड, और पोस्टऑर्डर से पहला नोड हटाएं
  • root_index := इनऑर्डर लिस्ट से root.val का इंडेक्स
  • root का लेफ्ट := buildTree(इनऑर्डर का सबसेट root_index + 1 से अंत तक, पोस्टऑर्डर)
  • root का राइट := buildTree(इनऑर्डर का सबसेट इंडेक्स 0 से root_index तक, पोस्टऑर्डर)

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

उदाहरण

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    # इनऑर्डर ट्रैवर्सल का उपयोग करके प्रिंट करें
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution(object):
    def buildTree(self, preorder, inorder):
        if inorder:
            root = TreeNode(preorder.pop(0))
            root_index = inorder.index(root.data)
            root.left = self.buildTree(preorder, inorder[:root_index])
            root.right = self.buildTree(preorder, inorder[root_index+1:])
            return root

ob1 = Solution()
print_tree(ob1.buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3]))

इनपुट

[9,3,15,20,7] [9,15,7,20,3]

आउटपुट

9, 15, 7, 20, 3,
  1. पायथन में प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं पायथन में प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से बाइनरी ट्री बनाएं

    मान लीजिए हमारे पास एक बाइनरी ट्री का इनऑर्डर और प्रीऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से ट्री उत्पन्न करना है। इसलिए यदि प्रीऑर्डर और इनऑर्डर अनुक्रम [3,9,20,15,7] और [9,3,15,20,7] हैं, तो ट्री होगा - आइए चरण देखते हैं - मान लीजिए मेथड को buildTree कहा जाता है जिसमें प्रीऑर्डर और इनऑर

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

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें रिकर्सन का उपयोग किए बिना इनऑर्डर ट्रैवर्सल योजना का उपयोग करके इस ट्री को पार करना है। इसलिए यदि ट्री इस तरह हैतो ट्रैवर्सल [2,5,7,10,15,20] होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -दो सरणी res और stack बनाएं, curr := root सेट करेंएक अनंत लूप च

  1. पायथन में बाइनरी ट्री उल्टा करें पायथन में बाइनरी ट्री उल्टा करें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमारा कार्य एक उल्टा बाइनरी ट्री बनाना है। यदि ट्री नीचे जैसा है: उल्टा ट्री इस तरह होगा: इसे हल करने के लिए हम एक पुनरावर्ती दृष्टिकोण का उपयोग करेंगे: यदि रूट null है, तो वापस करें बाएं और दाएं पॉइंटर्स को स्वैप करें बाएं सबट्री और दाएं सबट्री के लिए पुनर