Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python से बाइनरी ट्री की रूट को लीफ नोड पर कैसे बदलें?

लीफ नोड को नया रूट बनाने के लिए पैरेंट पॉइंटर्स का उपयोग करके ट्री को रीस्ट्रक्चर करें: लेफ्ट चाइल्ड राइट बन जाता है, पैरेंट लेफ्ट बन जाता है।

एल्गोरिदम

  • रिकर्सिव हेल्पर helper(node, new_par)।
  • अगर नोड मूल रूट है: पैरेंट सेट करें, लेफ्ट/राइट चाइल्ड जो new_par हैं उन्हें None करें।
  • अगर लेफ्ट चाइल्ड है: उसे राइट चाइल्ड बनाएं।
  • पैरेंट के लेफ्ट/राइट पॉइंटर को None करें जो इस नोड को पॉइंट करता है।
  • रिकर्सिवली पैरेंट को प्रोसेस करें और नया लेफ्ट चाइल्ड बनाएं।
  • पैरेंट अपडेट करें और नोड रिटर्न करें।

उदाहरण कोड


class TreeNode:
    def __init__(self, data, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent

def solve(root, leaf):
    def helper(node, new_par):
        if node == root:
            node.parent = new_par
            if node.left == new_par: node.left = None
            if node.right == new_par: node.right = None
            return root
        if node.left:
            node.right = node.left
        if node.parent.left == node:
            node.parent.left = None
        node.left = helper(node.parent, node)
        node.parent = new_par
        return node
    return helper(leaf, None)

# टेस्ट: ट्री [5,3,7,2,4,6,8], न्यू रूट=8 -> इनऑर्डर: 2,3,4,5,7,6,8

इनपुट/आउटपुट

इनपुट: रूट=5, लीफ=8
आउटपुट (इनऑर्डर): 2, 3, 4, 5, 7, 6, 8

  1. पायथन में बाइनरी ट्री के BST होने की जांच करने का प्रोग्राम पायथन में बाइनरी ट्री के BST होने की जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जांचना है कि क्या यह एक बाइनरी सर्च ट्री है या नहीं। जैसा कि हम जानते हैं एक BST के निम्न गुण होते हैं: इसके बाएं सबट्री के सभी नोड्स वर्तमान नोड के मान से छोटे होते हैं इसके दाएं सबट्री के सभी नोड्स वर्तमान नोड के मान से बड़े होते हैं ये गुण सभी नोड्स क

  1. पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ढूंढनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो बाएं सबसे नोड और दाएं सबसे नोड के बीच रखे जा सकते हैं। उदाहरण के लिए, यदि इनपुट है: तो आउटपुट होगा 2। हल करने के चरण एक मैप d बनाएं, न्यूनतम और अधिकतम मान

  1. पायथन में बाइनरी ट्री उल्टा करें पायथन में बाइनरी ट्री उल्टा करें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमारा कार्य एक उल्टा बाइनरी ट्री बनाना है। यदि ट्री नीचे जैसा है: उल्टा ट्री इस तरह होगा: इसे हल करने के लिए हम एक पुनरावर्ती दृष्टिकोण का उपयोग करेंगे: यदि रूट null है, तो वापस करें बाएं और दाएं पॉइंटर्स को स्वैप करें बाएं सबट्री और दाएं सबट्री के लिए पुनर