एक बाइनरी ट्री एक पदानुक्रमीय संरचना हो जहाँ प्रत्येक नोड को सबैभन्दा धेरै दुई संतान हुन्छन्, जसलाई left र भनिन्छ। यसको एक एकल हुन्छ; कुनै पनि संतान नभएका नोडहरू हुन्। यो BSTs, heaps, र expression trees को आधार हो।n
एक बाइनरी ट्री एक पदानुक्रमीय संरचना हो जहाँ प्रत्येक नोड को सबैभन्दा धेरै दुई संतान हुन्छन्, जसलाई left र भनिन्छ। यसको एक एकल हुन्छ; कुनै पनि संतान नभएका नोडहरू हुन्। यो BSTs, heaps, र expression trees को आधार हो।n
right 1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
एक level-order (BFS) ट्रावर्सल एक queue प्रयोग गरी गहिराइ अनुसार भ्रमण गर्छ।
| Traversal | Order | सामान्य प्रयोग |
|---|---|---|
| Inorder | L, N, R | BST को क्रमबद्ध आउटपुट |
| Preorder | N, L, R | ट्री प्रतिलिपि/serialize गर्नु |
| Postorder | L, R, N | ट्री मिटाउनु, expr मूल्याङ्कन |
| Level-order | गहिराइ अनुसार | BFS, ट्रीमा सबैभन्दा छोटो पाथ |
प्रत्येक ट्रावर्सल प्रत्येक नोडलाई एक पल भ्रमण गर्छ → O(n) समय, O(h) स्ट्याक स्पेस जहाँ h ट्रीको उचाइ हो।
बाइनरी ट्रीहरूले स्वाभाविक रूपमा पदानुक्रमीय डेटा (फाइल प्रणाली, parse trees, निर्णय ट्रीहरू) मडेल गर्छन् र कुशल खोज र क्रमबद्धता संरचनाको आधार हुन्छन्।
चारवटा ट्रावर्सलहरू मास्टर गर्नु अपरिहार्य छ — अधिकांश ट्री इन्टरभ्यु समस्याहरू यीमध्ये एकको भिन्नता हुन्।