जब इनऑर्डर या पोस्टऑर्डर ट्रैवर्सल का उपयोग करके इनपुट लेकर बाइनरी ट्री बनाने की आवश्यकता होती है, तो एक क्लास परिभाषित की जाती है जिसमें रूट तत्व सेट करने, इनऑर्डर ट्रैवर्सल करने, पोस्टऑर्डर ट्रैवर्सल करने के लिए मेथड्स होते हैं। इसका उपयोग क्लास का इंस्टेंस बनाकर किया जा सकता है।
उदाहरण
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' मेथड का उपयोग पहले से निर्दिष्ट तत्वों को लेकर बाइनरी ट्री बनाने के लिए किया जाता है।
इस ट्री पर पोस्ट ऑर्डर ट्रैवर्सल और इन ऑर्डर ट्रैवर्सल किया जाता है।
प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।
एल्गोरिदम समझाया गया
पोस्टऑर्डर + इनऑर्डर से ट्री पुनर्निर्माण:
पोस्टऑर्डर का अंतिम तत्व हमेशा रूट होता है
इनऑर्डर में रूट को खोजें - बाईं ओर के तत्व बाएं उपट्री हैं, दाईं ओर दाएं उपट्री
बाएं और दाएं उपट्री के लिए पुनरावृत्त रूप से लागू करें
पोस्टऑर्डर में बाएं उपट्री के तत्व पहले आते हैं (समान लंबाई), फिर दाएं उपट्री के, फिर रूट
पूर्वापेक्षाएँ
इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल एक ही ट्री के होने चाहिए
सभी तत्व अद्वितीय होने चाहिए (कोई डुप्लिकेट नहीं)
दोनों ट्रैवर्सल की लंबाई समान होनी चाहिए
समय जटिलता
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)