एक पेड़ के अजगर में एक नया मूल्य डालें
मेरे पास एक पेड़ है:
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]
अग्रिम में धन्यवाद
जवाब
चूंकि आपने पुनरावर्तन का उल्लेख किया है, यहाँ पुनरावृत्ति का उपयोग करके एक समाधान है:
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)
फ़ंक्शन नोड को सम्मिलित करने के लिए सही स्थान तक पहुंचने तक पेड़ को पुन: खोजता है। चूंकि यह एक द्विआधारी खोज पेड़ है, इसलिए हमें इस शर्त को सुनिश्चित करना चाहिए कि किसी भी नोड के बाईं ओर का बच्चा उस नोड से कम होना चाहिए, और दाईं ओर कोई भी बच्चा अधिक होना चाहिए। इसलिए हम ट्रैवर्सल की वर्तमान जड़ के साथ नए नोड की तुलना के अनुसार लेफ / राइट जाते हैं।