জাভাস্ক্রিপ্ট ট্রিতে ইন-অর্ডার ট্রাভারসাল

এই ট্রাভারসাল মেথডে, বাম সাবট্রি প্রথমে ভিজিট করা হয়, তারপর রুট এবং পরে ডান সাব-ট্রি। আমাদের সদা মনে রাখতে হবে যে প্রতিটি নোড নিজে একটি সাবট্রি হতে পারে।

যদি একটি বাইনারি ট্রি ইন-অর্ডার-এ ট্রাভার্স করা হয়, তবে আউটপুট সর্টেড কি ভ্যালু দেবে এসেন্ডিং অর্ডারে।

আমরা 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

লক্ষ্য করুন এলিমেন্টগুলো সর্টেড অর্ডারে প্রিন্ট হয়েছে। এর কারণ হলো যেহেতু আমরা রিকারসিভলি বাম সাবট্রি প্রথমে এক্সপ্লোর করি, আমরা সবচেয়ে ছোট ভ্যালুগুলো প্রথমে পাই। এটি চলতে থাকে শেষ পর্যন্ত এবং আমরা সব এলিমেন্ট সর্টেড অর্ডারে পাই।