मान लीजिए कि हमारे पास एक बाइनरी ट्री है जिसे हमें एक स्ट्रिंग बनाना है जिसमें प्रीऑर्डर ट्रैवर्सिंग तरीके से एक बाइनरी ट्री से कोष्ठक और पूर्णांक होते हैं। एक अशक्त नोड को खालीपैरेंटेसिस जोड़ी "()" द्वारा दर्शाया जाएगा। और हमें उन सभी खाली कोष्ठक युग्मों को छोड़ना होगा जो स्ट्रिंग और मूल बाइनरी ट्री के बीच एक-से-एक मानचित्रण संबंध को प्रभावित नहीं करते हैं।
तो, अगर इनपुट पसंद है
तो आउटपुट होगा 5(6()(8))(7)
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- उत्तर:=खाली स्ट्रिंग
- फ़ंक्शन पॉट () को परिभाषित करें। यह नोड लेगा, एस
- यदि शून्य है, तो
- रिक्त स्ट्रिंग लौटाएं
- यदि नोड का बायां या दायां शून्य है, तो
- नोड.डेटा लौटाएं
- ss:=node.data
- यदि नोड.बायां रिक्त नहीं है, तो
- ss :=ss concatenate '(' concatenate pot(node.left, रिक्त स्ट्रिंग) concatenate ')'
- अन्यथा,
- ss:=ss concatenate '()'
- यदि node.right शून्य नहीं है, तो
- ss:=ss concatenate '(' concatenate pot(node.right, रिक्त स्ट्रिंग) concatenate ')'
- रिटर्न एसएस
- मुख्य विधि से निम्न कार्य करें -
- रिटर्न पॉट (टी, ब्लैंक स्ट्रिंग)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution:
def tree2str(self, t: TreeNode):
ans = ''
def pot(node, s):
if node == None or node.data == 0:
return ''
if node.left == node.right == None:
return str(node.data)
ss = str(node.data)
if node.left != None:
ss = ss + '(' + pot(node.left, '') + ')'
else:
ss = ss + '()'
if node.right != None:
ss = ss + '(' + pot(node.right, '') + ')'
return ss
return pot(t, '')
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root)) इनपुट
[5,6,7,None,8]
आउटपुट
5(6()(8))(7)