जावास्क्रिप्ट ट्री में इन-ऑर्डर ट्रैवर्सल

इस ट्रैवर्सल मेथड में, लेफ्ट सबट्री को पहले विजिट किया जाता है, फिर रूट और बाद में राइट सब-ट्री। हमें हमेशा याद रखना चाहिए कि प्रत्येक नोड स्वयं एक सबट्री का प्रतिनिधित्व कर सकता है।

यदि बाइनरी ट्री को इन-ऑर्डर ट्रैवर्स किया जाता है, तो आउटपुट आरोही क्रम में सॉर्टेड की वैल्यूज़ उत्पन्न करेगा।

हम A से शुरू करते हैं, और इन-ऑर्डर ट्रैवर्सल का पालन करते हुए, हम इसके लेफ्ट सबट्री B पर जाते हैं। B को भी इन-ऑर्डर में ट्रैवर्स किया जाता है। प्रक्रिया तब तक चलती है जब तक सभी नोड्स विजिट नहीं हो जाते। इस ट्री का इनऑर्डर ट्रैवर्सल आउटपुट होगा:

D → B → E → A → F → C → G

यह वह एल्गोरिदम है जिसे हम लागू करेंगे:

रिकर्सिवली लेफ्ट सबट्री को ट्रैवर्स करें
नोड के डेटा को प्रिंट करें
रिकर्सिवली राइट सबट्री को ट्रैवर्स करें

आइए देखते हैं कि हम इसे अपनी क्लास में कैसे लागू करेंगे। चूंकि हम नहीं चाहते कि यूजर्स खुद रूट पास करें, हम फिर से क्लास के बाहर एक हेल्पर फ़ंक्शन बनाने जा रहे हैं।

inOrder() { inOrderHelper(this.root); }

हेल्पर फ़ंक्शन:

उदाहरण

function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}

आप इसका परीक्षण इस तरह कर सकते हैं:

उदाहरण

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();

आउटपुट

इससे निम्न आउटपुट मिलेगा:

3 5 7 10 12 15 50

ध्यान दें कि एलिमेंट्स सॉर्टेड क्रम में प्रिंट हुए थे। ऐसा इसलिए है क्योंकि चूंकि हम पहले लेफ्ट सबट्री को रिकर्सिवली एक्सप्लोर करते हैं, हमें सबसे छोटे मान पहले मिलते हैं। यह अंत तक चलता रहता है और हमें सभी एलिमेंट्स सॉर्टेड क्रम में मिलते हैं।