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

पायथन प्रोग्राम: इनऑर्डर या पोस्टऑर्डर ट्रैवर्सल इनपुट से बाइनरी ट्री बनाना


जब इनऑर्डर या पोस्टऑर्डर ट्रैवर्सल का उपयोग करके इनपुट लेकर बाइनरी ट्री बनाने की आवश्यकता होती है, तो एक क्लास परिभाषित की जाती है जिसमें रूट तत्व सेट करने, इनऑर्डर ट्रैवर्सल करने, पोस्टऑर्डर ट्रैवर्सल करने के लिए मेथड्स होते हैं। इसका उपयोग क्लास का इंस्टेंस बनाकर किया जा सकता है।

उदाहरण

class BinaryTree_struct:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None

    def set_root(self, key):
        self.key = key

    def inorder_traversal(self):
        if self.left is not None:
            self.left.inorder_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder_traversal()

    def post_order_traversal(self):
        if self.left is not None:
            self.left.post_order_traversal()
        if self.right is not None:
            self.right.post_order_traversal()
        print(self.key, end=' ')

def construct_btree(post_ord, in_ord):
    if post_ord == [] or in_ord == []:
        return None
    key = post_ord[-1]
    node = BinaryTree_struct(key)
    index = in_ord.index(key)
    node.left = construct_btree(post_ord[:index], in_ord[:index])
    node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
    return node

post_ord = input('पोस्ट-ऑर्डर ट्रैवर्सल के लिए इनपुट है: ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('इन-ऑर्डर ट्रैवर्सल के लिए इनपुट है: ').split()
in_ord = [int(x) for x in in_ord]

my_instance = construct_btree(post_ord, in_ord)
print('बाइनरी ट्री बनाया गया...')
print('सत्यापन प्रक्रिया में...')
print('पोस्ट-ऑर्डर ट्रैवर्सल है... ', end='')
my_instance.post_order_traversal()
print()
print('इन-ऑर्डर ट्रैवर्सल है... ', end='')
my_instance.inorder_traversal()
print()

आउटपुट

पोस्ट-ऑर्डर ट्रैवर्सल के लिए इनपुट है: 1 2 3 4 5
इन-ऑर्डर ट्रैवर्सल के लिए इनपुट है: 5 4 3 2 1
बाइनरी ट्री बनाया गया...
सत्यापन प्रक्रिया में...
पोस्ट-ऑर्डर ट्रैवर्सल है... 1 2 3 4 5
इन-ऑर्डर ट्रैवर्सल है... 5 4 3 2 1

व्याख्या

  • आवश्यक विशेषताओं के साथ 'BinaryTree_struct' क्लास बनाई गई है।

  • इसमें एक 'init' फ़ंक्शन है जो बाएं और दाएं नोड्स को 'None' पर सेट करता है।

  • इसमें एक 'set_root' मेथड है जो बाइनरी ट्री की जड़ सेट करने में मदद करता है।

  • 'inorder_traversal' नामक एक अन्य मेथड इन-ऑर्डर ट्रैवर्सल करता है, यानी Left→Node→Right।

  • 'post_order_traversal' नामक एक अन्य मेथड पोस्ट ऑर्डर में ट्री को ट्रैवर्स करने में मदद करता है, यानी Left→Right→Node।

  • 'construct_btree' नामक एक मेथड परिभाषित की गई है, जो पहले से निर्दिष्ट तत्वों का उपयोग करके बाइनरी ट्री बनाने में मदद करती है।

  • 'search_elem' नामक एक मेथड परिभाषित की गई है, जो एक विशिष्ट तत्व खोजने में मदद करती है।

  • 'BinaryTree_struct' क्लास का एक ऑब्जेक्ट बनाया जाता है।

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

  • इस ट्री पर पोस्ट ऑर्डर ट्रैवर्सल और इन ऑर्डर ट्रैवर्सल किया जाता है।

  • प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।

एल्गोरिदम समझाया गया

पोस्टऑर्डर + इनऑर्डर से ट्री पुनर्निर्माण:

  1. पोस्टऑर्डर का अंतिम तत्व हमेशा रूट होता है

  2. इनऑर्डर में रूट को खोजें - बाईं ओर के तत्व बाएं उपट्री हैं, दाईं ओर दाएं उपट्री

  3. बाएं और दाएं उपट्री के लिए पुनरावृत्त रूप से लागू करें

  4. पोस्टऑर्डर में बाएं उपट्री के तत्व पहले आते हैं (समान लंबाई), फिर दाएं उपट्री के, फिर रूट

पूर्वापेक्षाएँ

  • इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल एक ही ट्री के होने चाहिए

  • सभी तत्व अद्वितीय होने चाहिए (कोई डुप्लिकेट नहीं)

  • दोनों ट्रैवर्सल की लंबाई समान होनी चाहिए

समय जटिलता

  • in_ord.index(key) प्रत्येक पुनरावृत्ति कॉल में O(n) है

  • कुल: O(n²) - हैश मैप का उपयोग करके O(n) तक अनुकूलित किया जा सकता है

अनुकूलित संस्करण (O(n))

def construct_btree_optimized(post_ord, in_ord):
    inorder_index_map = {val: idx for idx, val in enumerate(in_ord)}
    
    def build(post_start, post_end, in_start, in_end):
        if post_start > post_end or in_start > in_end:
            return None
        root_val = post_ord[post_end]
        root = BinaryTree_struct(root_val)
        in_root_idx = inorder_index_map[root_val]
        left_size = in_root_idx - in_start
        
        root.left = build(post_start, post_start + left_size - 1, in_start, in_root_idx - 1)
        root.right = build(post_start + left_size, post_end - 1, in_root_idx + 1, in_end)
        return root
    
    return build(0, len(post_ord) - 1, 0, len(in_ord) - 1)

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

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

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

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

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

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें ट्री के व्यास की लंबाई की गणना करनी है। बाइनरी ट्री का व्यास वास्तव में ट्री में किन्हीं दो नोड्स के बीच सबसे लंबे पथ की लंबाई है। यह पथ अनिवार्य रूप से रूट से होकर नहीं जाता। यदि ट्री नीचे जैसा है, तो व्यास 3 होगा क्योंकि पथ [4,2,1,3] या [5,2,1,3] की लंब