जब बाइनरी ट्री के इनऑर्डर ट्रैवर्सल का उपयोग करके 'n'वें नोड को खोजने की आवश्यकता होती है, तो एक बाइनरी ट्री क्लास बनाई जाती है जिसमें रूट तत्व सेट करने, बाएं या दाएं तत्व जोड़ने, इनऑर्डर ट्रैवर्सल करने आदि के लिए मेथड्स होते हैं। क्लास का एक इंस्टेंस बनाया जाता है, और इसका उपयोग मेथड्स तक पहुंचने के लिए किया जा सकता है।
उदाहरण
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_nth(self, n):
return self.inorder_nth_helper_fun(n, [])
def inorder_nth_helper_fun(self, n, in_ord):
if self.left is not None:
temp = self.left.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
in_ord.append(self)
if n == len(in_ord):
return self
if self.right is not None:
temp = self.right.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
def insert_to_left(self, new_node):
self.left = new_node
def insert_to_right(self, new_node):
self.right = new_node
def search_elem(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_elem(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_elem(key)
return temp
return None
btree_instance = None
print('मेनू (यह मानता है कोई डुप्लिकेट कुंजी नहीं)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('inorder ')
print('quit')
while True:
do = input('आप क्या करना चाहेंगे? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_struct(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
btree_instance = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree_instance is not None:
ref_node = btree_instance.search_elem(key)
if ref_node is None:
print('ऐसी कोई कुंजी नहीं।')
continue
if suboperation == 'left':
ref_node.insert_to_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'inorder':
if btree_instance is not None:
index = int(do[1].strip().lower())
node = btree_instance.inorder_nth(index)
if node is not None:
print('इनऑर्डर ट्रैवर्सल का nth पद: {}'.format(node.key))
else:
print('इंडेक्स अधिकतम संभव इंडेक्स से अधिक है।')
else:
print('ट्री खाली है...')
elif operation == 'quit':
break
आउटपुट
मेनू (यह मानता है कोई डुप्लिकेट कुंजी नहीं) insert <data> at root insert <data> left of <data> insert <data> right of <data> inorder quit आप क्या करना चाहेंगे? insert 5 at root आप क्या करना चाहेंगे? insert 6 left of 5 आप क्या करना चाहेंगे? insert 8 right of 5 आप क्या करना चाहेंगे? inorder 5 इंडेक्स अधिकतम संभव इंडेक्स से अधिक है। आप क्या करना चाहेंगे? 6 6
व्याख्या
आवश्यक विशेषताओं के साथ 'BinaryTree_struct' क्लास बनाई गई है।
इसमें एक 'init' फ़ंक्शन है जो बाएं और दाएं नोड्स को 'None' पर सेट करता है।
इसमें एक 'set_root' मेथड है जो बाइनरी ट्री की जड़ सेट करने में मदद करता है।
'inorder_nth' नामक एक अन्य मेथड पुनरावृत्ति का उपयोग करके इनऑर्डर ट्रैवर्सल करता है।
इसलिए इसके साथ एक हेल्पर फ़ंक्शन परिभाषित किया गया है।
'insert_to_right' नामक एक अन्य मेथड रूट नोड के दाईं ओर तत्व जोड़ने के लिए परिभाषित की गई है।
'insert_to_left' नामक एक मेथड रूट नोड के बाईं ओर तत्व जोड़ने के लिए परिभाषित की गई है।
'search_elem' नामक एक मेथड एक विशिष्ट तत्व खोजने के लिए परिभाषित की गई है।
'BinaryTree_struct' क्लास का एक ऑब्जेक्ट बनाया जाता है।
उपयोगकर्ता इनपुट लिया जाता है कि कौन सा ऑपरेशन करना है।
उपयोगकर्ता की पसंद के आधार पर, ऑपरेशन किया जाता है।
प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।
एल्गोरिदम विश्लेषण
inorder_nth_helper_fun एक सूची in_ord का उपयोग करके देखे गए नोड्स को ट्रैक करता है। जब सूची की लंबाई n के बराबर होती है, तो वर्तमान नोड nवां नोड होता है।
समय और स्थान जटिलता
समय: O(n) - सबसे खराब स्थिति में सभी नोड्स विजिट करने पड़ते हैं
स्थान: O(n) - पुनरावृत्ति स्टैक + in_ord सूची
सुधार: जनरेटर का उपयोग करके
def inorder_generator(self):
if self.left:
yield from self.left.inorder_generator()
yield self
if self.right:
yield from self.right.inorder_generator()
def inorder_nth(self, n):
for i, node in enumerate(self.inorder_generator(), 1):
if i == n:
return node
return None
यह संस्करण अधिक मेमोरी-कुशल है (O(h) स्थान जहां h ऊंचाई है) और पायथनिक है।
नोट
मूल आउटपुट में अंत में "6 6" भ्रमित करने वाला लगता है - यह संभवतः उपयोगकर्ता इनपुट इको है।
