बाइनरी सर्च ट्री का उपयोग करके सॉर्ट करने का पायथन प्रोग्राम

जब बाइनरी सर्च ट्री को सॉर्ट करना हो, तो एक क्लास बनाई जाती है और उसके अंदर मेथड्स परिभाषित की जाती हैं जो एलिमेंट इंसर्ट करने और इनऑर्डर ट्रैवर्सल करने जैसे ऑपरेशन करती हैं।

उदाहरण

class BinSearchTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key <= node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)
    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()

class BinSearchTree:
    def __init__(self):
        self.root = None
    def inorder_traversal(self):
        if self.root is not None:
            self.root.inorder_traversal()
    def add_val(self, key):
        new_node = BinSearchTreeNode(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)

my_instance = BinSearchTree()
my_list = input('संख्याओं की सूची दर्ज करें... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
    my_instance.add_val(x)
print('सॉर्ट की गई सूची:')
print(my_instance.inorder_traversal())

आउटपुट

संख्याओं की सूची दर्ज करें... 67 54 89 0 11 34 99
सॉर्ट की गई सूची:
0 11 34 54 67 89 99

व्याख्या

आवश्यक एट्रिब्यूट्स के साथ 'BinSearchTreeNode' क्लास बनाई जाती है।
इसमें एक 'init' फंक्शन होता है जिसका उपयोग 'left', 'right' और 'parent' नोड्स को 'None' असाइन करने के लिए किया जाता है।
'insert_elem' नामक एक अन्य मेथड परिभाषित की जाती है जो ट्री में नोड्स जोड़ने में मदद करती है।
'inorder_traversal' नामक एक अन्य मेथड परिभाषित की जाती है जो ट्री पर इनऑर्डर ट्रैवर्सल करने में मदद करती है।
'BinSearchTree' नामक एक अन्य क्लास परिभाषित की जाती है।
यह रूट को 'None' सेट करती है।
इसमें 'inorder_traversal' नामक एक मेथड होती है जो ट्री पर इनऑर्डर ट्रैवर्सल करने में मदद करती है।
'add_val' नामक एक अन्य मेथड परिभाषित की जाती है जो ट्री में नोड्स जोड़ने में मदद करती है।
'BinSearchTree' का एक इंस्टेंस बनाया जाता है।
संख्याओं की सूची उपयोगकर्ता द्वारा ली जाती है।
इसका उपयोग करके एक ट्री बनाई जाती है।
सूची सॉर्ट की जाती है और इसका इनऑर्डर ट्रैवर्सल किया जाता है।
प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।