जब इनऑर्डर या पोस्टऑर्डर ट्रैवर्सल का उपयोग करके इनपुट लेकर बाइनरी ट्री बनाने की आवश्यकता होती है, तो एक वर्ग परिभाषित किया जाता है, जिसमें रूट तत्व सेट करने, इनऑर्डर ट्रैवर्सल करने, पोस्ट ऑर्डर ट्रैवर्सल करने के तरीके होते हैं। इसका उपयोग कक्षा का एक उदाहरण बनाकर किया जा सकता है।
नीचे उसी का एक प्रदर्शन है -
उदाहरण
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('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print() आउटपुट
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
स्पष्टीकरण
-
आवश्यक विशेषताओं के साथ 'BinaryTree_struct' वर्ग बनाया गया है।
-
इसमें एक 'init' फंक्शन होता है जिसका इस्तेमाल बाएँ और दाएँ नोड्स को 'कोई नहीं' पर सेट करने के लिए किया जाता है।
-
इसमें एक 'set_root' विधि है जो बाइनरी ट्री की जड़ को सेट करने में मदद करती है।
-
'इनऑर्डर_ट्रैवर्सल' नाम की एक अन्य विधि जो इन-ऑर्डर ट्रैवर्सल करती है, यानी लेफ्ट → नोड → राइट।
-
'post_order_traversal' नामक एक अन्य विधि को परिभाषित किया गया है जो पेड़ के माध्यम से पोस्ट ऑर्डर, यानी बाएं → दाएं → नोड में पार करने में मदद करता है।
-
'construct_btree' नाम की एक विधि परिभाषित की गई है, जो पहले निर्दिष्ट किए गए तत्वों का उपयोग करके एक बाइनरी ट्री बनाने में मदद करती है।
-
'Search_elem' नाम की एक विधि परिभाषित की गई है, जो एक विशिष्ट तत्व की खोज में मदद करती है।
-
'BinaryTree_struct' वर्ग का एक ऑब्जेक्ट बनाया जाता है।
-
'Construct_btree' पद्धति का उपयोग पहले निर्दिष्ट किए गए तत्वों को लेकर एक बाइनरी ट्री बनाने के लिए किया जाता है।
-
इस पेड़ पर पोस्ट ऑर्डर ट्रैवर्सल और ऑर्डर ट्रैवर्सल किया जाता है।
-
प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।