बाइनरी ट्री का प्रतिनिधित्व
बाइनरी ट्री कंप्यूटर विज्ञान में व्यापक रूप से उपयोग की जाने वाली एक बुनियादी डेटा संरचना है। यह खोज (search), छँटाई (sorting) और डेटा को ट्रवर्स (traversing) करने जैसे कार्यों के लिए प्रभावी एल्गोरिदम बनाने में विशेष रूप से उपयोगी है।
बाइनरी ट्री नोड्स से मिलकर बनता है, जहाँ प्रत्येक नोड के अधिकतम दो चाइल्ड होते हैं—एक बायाँ (left) और एक दायाँ (right)। बाएँ और दाएँ दोनों चाइल्ड के भी अपने चाइल्ड हो सकते हैं, और यह संरचना तब तक चलती रहती है जब तक ट्री में कोई और नोड नहीं रह जाता।
बाइनरी ट्री का सबसे ऊपरी नोड रूट (root) कहलाता है, जबकि सबसे निचले तत्वों को ट्री के लीव्स (leaves) कहा जाता है।
यही सरल विचार कई अलग-अलग डेटा टाइप्स को कुशलता से दर्शाने की अनुमति देता है और विभिन्न प्रोग्रामिंग भाषाओं में इनका कार्यान्वयन आसान होता है:
class Node: # प्रत्येक नोड का डेटा रखने के लिए Node ऑब्जेक्ट
def __init__(self, value): # प्रत्येक नोड में रखने के लिए मान (किसी भी प्रकार का हो सकता है)
self.left = None # शुरू में left और right दोनों None हैं
self.right = None
self.value = value # मान को ऑब्जेक्ट में रखता है
# सभी नोड्स को मैन्युअल रूप से बनाना
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# अब हम संपूर्ण बाइनरी ट्री को रिकर्सिव रूप से ट्रवर्स कर सकते हैं
# आइए सभी नोड्स का योग निकालते हैं
def treesum(node: Node | None) -> int:
if node is None:
return 0
# बाएँ सबट्री, दाएँ सबट्री और वर्तमान नोड के मान का योग लौटाएँ
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Prints 36इस उदाहरण में, हम root से शुरू करके सभी नोड्स को ट्रवर्स करते हैं। अगर वर्तमान नोड None है, तो इसका मतलब है कि उस पथ के अंत तक पहुँच गए हैं और वहाँ कोई सबट्री नहीं बची; इस स्थिति में हम 0 लौटा देते हैं। अन्यथा, हम बाएँ सबट्री, दाएँ सबट्री और वर्तमान नोड के मान का योग निकालते हैं और उन्हें एक साथ जोड़ देते हैं।
चुनौती: बाइनरी ट्री को मैन्युअल रूप से बनाएँ
चित्र में दिखाए गए बाइनरी ट्री को मैन्युअल रूप से बनाने के लिए कहा गया है।
ऐसा कोड लिखें जो इस बाइनरी ट्री को बनाए। आपको कुछ भी प्रिंट करने की आवश्यकता नहीं है। यह भाग स्वचालित रूप से संभाल लिया जाता है।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB