एक पेड़ के अजगर में एक नया मूल्य डालें

Nov 24 2020

मेरे पास एक पेड़ है:

tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]

संख्या प्रत्येक नोड की जड़ का प्रतिनिधित्व करती है, कोई भी उन बच्चों का प्रतिनिधित्व नहीं करता है जिनका कोई मूल्य नहीं है।

उदाहरण के लिए, मुख्य जड़ 4 है और [[कोई नहीं, 1, कोई नहीं], 2, [कोई नहीं, 3, कोई नहीं]] बाईं ओर उप वृक्ष है और यह [कोई नहीं, 6, [कोई नहीं, 7, कोई भी]] क्या वह दाईं ओर उप वृक्ष है। बाईं ओर के उप-वृक्ष पर मूल जड़ 2 आदि है ...

और मेरी समस्या यह है कि मैं इस पेड़ में एक मूल्य सम्मिलित करना चाहता हूं।

उदाहरण के लिए मैं मान 5 जोड़ना चाहता हूं, यही वह है जो मैं चाहता हूं:

tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]

मेरे फ़ंक्शन को जोड़ने के लिए दो तर्क, पेड़ और पूर्णांक लेते हैं, मुझे पुनरावर्ती फ़ंक्शन का उपयोग करने की आवश्यकता है, उदाहरण के लिए यह वह है जो मैं देख रहा हूं:

def insert(tree,int):
    cur = tree
    prev = None
    while cur != None:
        prev = cur
        if int < cur[1]:
            cur = cur[0]
        else :
            cur = cur[2]

अग्रिम में धन्यवाद

जवाब

2 Maaddy Nov 24 2020 at 09:00

चूंकि आपने पुनरावर्तन का उल्लेख किया है, यहाँ पुनरावृत्ति का उपयोग करके एक समाधान है:

def insert_node(root, node):
    if root == [None]:  #corner case of an empty tree
        root.append(node)
        root.append(None)   #now root will be : [None, node, None]
        return
    if node <= root[1]:  #we need to go left
        if root[0] == None:
            root[0] = [None, node, None]
            return
        else:
            insert_node(root[0], node)
    else:               #we need to go right
        if root[2] == None:
            root[2] = [None, node, None]
            return
        else:
            insert_node(root[2], node)

समाधान का परीक्षण:

tree = [None]   #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)

फ़ंक्शन नोड को सम्मिलित करने के लिए सही स्थान तक पहुंचने तक पेड़ को पुन: खोजता है। चूंकि यह एक द्विआधारी खोज पेड़ है, इसलिए हमें इस शर्त को सुनिश्चित करना चाहिए कि किसी भी नोड के बाईं ओर का बच्चा उस नोड से कम होना चाहिए, और दाईं ओर कोई भी बच्चा अधिक होना चाहिए। इसलिए हम ट्रैवर्सल की वर्तमान जड़ के साथ नए नोड की तुलना के अनुसार लेफ / राइट जाते हैं।