Binary Tree क्या हैं? [Binary tree in hindi]

Data Structure – Binary Tree क्या हैं?

Binary Tree क्या हैं?

Binary tree सीमित element का set होता है जिसके प्रत्येक element को node कहते हैं। इसकी सबसे बड़ी विशेषता यह होती हैं कि इसके प्रत्येक node के अधिकतम दो subnode (successor) एवं तीन भाग होते हैं। एक भाग में node का information (data) स्टोर होता है एवं बाकी के दो भाग pointer होते हैं जो node के दोनों subnode (successor) का address स्टोर करके रखते हैं अर्थात दोनो subnode (successor) को point करते हैं। माना TREE एक binary tree है तब इससे संबंधित महत्वपूर्ण तथ्य निम्नलिखित है:

1. यदि TREE खाली है तो null tree या empty tree कहते हैं।
2. यदि TREE में सीमित संख्या में node है तो इसके सबसे पहले या ऊपर के node को root node R कहते हैं एवं इसके बाकी के सभी nodes मिलकर दो और TREE का निर्माण करते हैं जिन्हें R का left subtree और right subtree.
3. TREE के किसी node N से left downward slanted line को N का left successor (left child) कहते हैं एवं right downward slanted line को N का right successor (right child) कहते हैं। इसमें प्रत्येक node का केवल दो successor (child) होता है।
4. TREE के किसी node N को इसके left successor (left child) व right successor (right child) का predecessor (parent) कहते हैं। इसमें root node को छोड़कर प्रत्येक node का केवल एक predecessor (parent) होता है।
5. TREE के किसी node N का कोई भी left successor व right successor न हो तो इसे terminal node कहते हैं।
6. TREE के किसी node N से इसके दोनों successors को जोड़ने वाली line को edge या branch कहते हैं।
7. TREE में node की संख्या न हो तो इसमें edges या branches की संख्या n-1 तथा इसका depth या height लगभग log2n+1 होता हैं।
8. TREE के किसी level e में nodes की अधिकतम संख्या 2 होता है जहाँ e=0, 1, 2 etc.

Representation of Binary Tree in Memory

Binary tree को मेमोरी में linked list की सहायता से प्रदर्शित किया जाता है। माना TREE एक binary tree है जिसके प्रत्येक node के तीन भाग INFO, LEFT व RIGHT है। INFO भाग में node का data स्टोर होता है तथा LEFT व RIGHT दो pointer होते हैं जिसमें क्रमशः node के left व right subnode (successor के address स्टोर होते हैं। अर्थात left व right subnode (successor) को point करते हैं। साथ ही ROOT नाम से एक और pointer होता हैं जिसमें TREE के root node का address स्टोर होता है अर्थात root node को point करता है। TREE के खाली होने की स्थिति में ROOT में null store होता है।

Traversal in Binary Tree

Binary tree के traversal करना बहुत आसान होता है। इसमें traversal करने के लिए तीन standard algorithm होते हैं जिनमे से किसी भी एक algorithm का प्रयोग करके हम binary tree में traversal कर सकते हैं। इन तीनों को preorder, in-order व postorder कहते हैं। इन तीनो algorithm के कार्य करने का तरीका भी एक जैसे ही होता है। तीनों left subtree को हमेशा right subtree से पहले traversal किया जाता है, बस root node R के process होने के क्रम में अंतर होता है। preorder में R पहले process होता है, In-order में R बीच मे process होता है तथा postorder में R बाद में process होता है।

1. Preorder

• Process the root R
• Traverse the left subtree of R in preorder
• Traverse the right subtree of R in preorder

2. In-order

• Traverse the left subtree of R in in-order
• Process the root R
• Traverse the right subtree of R in in-order

3. Postorder

• Traverse the left subtree of R in postorder
• Traverse the right subtree of R in postorder
• Process the root R

Drawing Binary Tree Diagram from given Expression

(1) E=(a-b)/((c*d)+e)  [Inorder Traversal]