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

जब रीकर्सन का उपयोग करके ट्री पर डेप्थ फर्स्ट सर्च करना हो, तो एक क्लास परिभाषित की जाती है और उस पर मेथड्स परिभाषित की जाती हैं जो ब्रेडथ फर्स्ट सर्च करने में मदद करती हैं।

उदाहरण

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 insert_at_left(self, new_node):
        self.left = new_node
    def insert_at_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(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp = self.right.search(key)
            return temp
        return None
    def depth_first_search(self):
        print('entering {}...'.format(self.key))
        if self.left is not None:
            self.left.depth_first_search()
        print('at {}...'.format(self.key))
        if self.right is not None:
            self.right.depth_first_search()
        print('leaving {}...'.format(self.key))

btree_instance = None
print('मेन्यू (कोई डुप्लिकेट कीज़ नहीं)')
print('insert  at root')
print('insert  left of ')
print('insert  right of ')
print('dfs')
print('quit')
while True:
    my_input = input('आप क्या करना चाहेंगे? ').split()
    op = my_input[0].strip().lower()
    if op == 'insert':
        data = int(my_input[1])
        new_node = BinaryTree_struct(data)
        sub_op = my_input[2].strip().lower()
        if sub_op == 'at':
            btree_instance = new_node
        else:
            position = my_input[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 sub_op == 'left':
                ref_node.insert_at_left(new_node)
            elif sub_op == 'right':
                ref_node.insert_at_right(new_node)
    elif op == 'dfs':
        print('डेप्थ-फर्स्ट सर्च ट्रैवर्सल:')
        if btree_instance is not None:
            btree_instance.depth_first_search()
        print()
    elif op == 'quit':
        break

आउटपुट

मेन्यू (कोई डुप्लिकेट कीज़ नहीं)
insert  at root
insert  left of 
insert  right of 
dfs
quit
आप क्या करना चाहेंगे? insert 5 at root
आप क्या करना चाहेंगे? insert 6 left of 5
आप क्या करना चाहेंगे? insert 8 right of 5
आप क्या करना चाहेंगे? dfs
डेप्थ-फर्स्ट सर्च ट्रैवर्सल:
entering 5...
entering 6...
at 6...
leaving 6...
at 5...
entering 8...
at 8...
leaving 8...
leaving 5...
आप क्या करना चाहेंगे? quit
बाहर निकलने के लिए quit() या Ctrl-D (यानी EOF) का उपयोग करें

व्याख्या

• आवश्यक एट्रिब्यूट्स के साथ 'BinaryTree_struct' क्लास बनाई जाती है।

• इसमें एक 'init' फंक्शन होता है जिसका उपयोग 'left' और 'right' नोड्स को 'None' असाइन करने के लिए किया जाता है।

• 'set_root' नामक एक अन्य मेथड ट्री के रूट को निर्दिष्ट करने के लिए परिभाषित की जाती है।

• 'insert_at_left' नामक एक अन्य मेथड परिभाषित की जाती है जो ट्री के बाईं ओर नोड्स जोड़ने में मदद करती है।

• 'insert_at_right' नामक एक अन्य मेथड परिभाषित की जाती है जो ट्री के दाईं ओर नोड्स जोड़ने में मदद करती है।

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

• 'depth_first_search' नामक एक मेथड परिभाषित की जाती है जो बाइनरी ट्री पर डेप्थ फर्स्ट सर्च करने में मदद करती है।

• क्लास का एक इंस्टेंस बनाया जाता है और 'None' असाइन किया जाता है।

• एक मेन्यू दिया जाता है।

• उपयोगकर्ता इनपुट उस ऑपरेशन के लिए लिया जाता है जिसे करने की आवश्यकता है।

• उपयोगकर्ता की पसंद के आधार पर ऑपरेशन किया जाता है।

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