জাভাস্ক্রিপ্টে ট্রি ট্রাভার্সাল অন্বেষণ: উদাহরণ সহ ইনঅর্ডার, প্রিঅর্ডার এবং পোস্টঅর্ডার

ট্রি ট্রাভার্সাল হল কম্পিউটার সায়েন্সের একটি মৌলিক ধারণা যা একটি গাছের ডেটা স্ট্রাকচারের প্রতিটি নোডকে পদ্ধতিগতভাবে পরিদর্শন করে। ট্রি ট্রাভার্সালের মাধ্যমে, আমরা নোডগুলিকে পূর্বনির্ধারিত ক্রমে প্রক্রিয়া করতে পারি, অনুসন্ধান, বাছাই এবং অভিব্যক্তি মূল্যায়নের মতো ক্রিয়াকলাপগুলিকে সহজতর করে৷

এই নিবন্ধে, আমরা তিনটি বহুল ব্যবহৃত ট্রি ট্রাভার্সাল পদ্ধতির অন্বেষণ করব: ইনঅর্ডার, প্রি-অর্ডার এবং পোস্টঅর্ডার।

জাভাস্ক্রিপ্টে বাস্তবায়িত স্পষ্ট এবং সংক্ষিপ্ত উদাহরণগুলির মাধ্যমে, আপনি এই ট্রাভার্সাল কৌশলগুলির একটি দৃঢ় উপলব্ধি অর্জন করতে পারবেন।

গাছের গঠন সংজ্ঞা

ট্রি ট্রাভার্সাল অ্যালগরিদমগুলিতে ডুব দেওয়ার আগে, আসুন আমরা বাইনারি গাছের জন্য যে কাঠামোটি ব্যবহার করব তা সংজ্ঞায়িত করি। গাছটি নোড নিয়ে গঠিত হবে, যেখানে প্রতিটি নোডের একটি মান এবং তার বাম এবং ডান চাইল্ড নোডের রেফারেন্স রয়েছে।

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

এখন যেহেতু আমরা গাছের গঠন সংজ্ঞায়িত করেছি, আমরা তিনটি ট্রি ট্রাভার্সাল পদ্ধতির অন্বেষণে এগিয়ে যেতে পারি।

ইনঅর্ডার ট্রাভার্সাল

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

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

রিকার্সিভ ইনঅর্ডার ট্রাভার্সাল

1. বর্তমান নোডটি শূন্য কিনা তা পরীক্ষা করুন। যদি তাই হয়, ফিরে যান।

   
   

2. বারবার বাম সাবট্রিতে ফাংশনটি কল করুন।

   
   

3. বর্তমান নোড দেখুন।

   
   

4. পুনরাবৃত্তভাবে ডান সাবট্রিতে ফাংশনটি কল করুন।

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

অ-পুনরাবৃত্ত ইনঅর্ডার ট্রাভার্সাল

1. একটি খালি স্ট্যাক শুরু করুন এবং বর্তমান নোডটিকে গাছের মূলে সেট করুন।

   
   

2. স্ট্যাক খালি না থাকা অবস্থায় বা বর্তমান নোডটি শূন্য না থাকার সময় পুনরাবৃত্তি করুন।

   • সমস্ত বাম নোডগুলিকে স্ট্যাকের উপর চাপুন যতক্ষণ না একটি শূন্য বাম শিশু পর্যন্ত পৌঁছায়।

   • স্ট্যাক থেকে একটি নোড পপ করুন, এটি দেখুন এবং বর্তমান নোডটিকে তার ডান চাইল্ডে সেট করুন।

     
     

3. স্ট্যাকটি খালি না হওয়া পর্যন্ত এবং বর্তমান নোডটি শূন্য না হওয়া পর্যন্ত ধাপ 2 পুনরাবৃত্তি করুন।

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

প্রি-অর্ডার ট্রাভার্সাল

প্রি-অর্ডার ট্রাভার্সালে, অ্যালগরিদম প্রথমে বর্তমান নোডটি পরিদর্শন করে, তারপরে বাম সাবট্রিকে অতিক্রম করে এবং অবশেষে ডান সাবট্রিকে অতিক্রম করে। এই ক্রমটি নিশ্চিত করে যে নোডগুলি "উপর-নিচে" পদ্ধতিতে পরিদর্শন করা হয়, মূল থেকে শুরু করে এবং পাতার দিকে চলে যায়।

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

রিকার্সিভ প্রি-অর্ডার ট্রাভার্সাল

1. বর্তমান নোডটি শূন্য কিনা তা পরীক্ষা করুন। যদি তাই হয়, ফিরে যান।

   
   

2. বর্তমান নোড দেখুন।

   
   

3. বারবার বাম সাবট্রিতে ফাংশনটি কল করুন।

   
   

4. পুনরাবৃত্তভাবে ডান সাবট্রিতে ফাংশনটি কল করুন।

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

নন-রিকারসিভ প্রি-অর্ডার ট্রাভার্সাল

1. একটি খালি স্ট্যাক দিয়ে শুরু করুন এবং রুট নোডটিকে স্ট্যাকের উপর চাপুন।

   
   

2. প্রি-অর্ডার ট্রাভার্সাল ফলাফল সংরক্ষণ করতে একটি খালি অ্যারে শুরু করুন।

   
   

3. স্ট্যাক খালি না হওয়া পর্যন্ত চলাকালীন একটি লুপ লিখুন।

   
   

4. স্ট্যাক থেকে একটি নোড পপ করুন, এবং ফলাফল অ্যারেতে এর মান যোগ করে এটি দেখুন।

   
   

5. যদি নোডের একটি সঠিক শিশু থাকে, তাহলে ডান শিশুটিকে স্ট্যাকের উপর ঠেলে দিন।

   
   

6. যদি নোডের একটি বাম শিশু থাকে তবে বাম শিশুটিকে স্ট্যাকের উপর ঠেলে দিন।

   
   

7. স্ট্যাক খালি না হওয়া পর্যন্ত 3-6 ধাপ পুনরাবৃত্তি করুন।

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

পোস্টঅর্ডার ট্রাভার্সাল

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

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

রিকার্সিভ পোস্টঅর্ডার ট্রাভার্সাল

1. বর্তমান নোডটি শূন্য কিনা তা পরীক্ষা করুন। যদি তাই হয়, ফিরে যান।

   
   

2. বারবার বাম সাবট্রিতে ফাংশনটি কল করুন।

   
   

3. পুনরাবৃত্তভাবে ডান সাবট্রিতে ফাংশনটি কল করুন।

   
   

4. বর্তমান নোড দেখুন।

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

নন-রিকারসিভ পোস্টঅর্ডার ট্রাভার্সাল

1. একটি খালি স্ট্যাক দিয়ে শুরু করুন এবং রুট নোডটিকে স্ট্যাকের উপর চাপুন।

   
   

2. পোস্টঅর্ডার ট্রাভার্সাল ফলাফল সংরক্ষণ করতে একটি খালি অ্যারে শুরু করুন।

   
   

3. স্ট্যাক খালি না হওয়া পর্যন্ত চলাকালীন একটি লুপ লিখুন।

   
   

4. স্ট্যাক থেকে শীর্ষ নোড পান (এটি অপসারণ ছাড়া)।

   
   

5. যদি নোডের একটি বাম সন্তান থাকে, তাহলে বাম শিশুটিকে স্ট্যাকের উপর চাপুন এবং বর্তমান নোডের বাম শিশুটিকে নাল সেট করুন।

   
   

6. যদি নোডের একটি সঠিক চাইল্ড থাকে, তাহলে ডান চাইল্ডটিকে স্ট্যাকের উপর চাপুন এবং বর্তমান নোডের ডান চাইল্ডটিকে নাল সেট করুন।

   
   

7. যদি নোডের একটি বাম বা ডান সন্তান না থাকে তবে এটি একটি পাতার নোড। স্ট্যাক থেকে নোডটি পপ করুন এবং ফলাফল অ্যারেতে এর মান যুক্ত করুন।

   
   

8. স্ট্যাক খালি না হওয়া পর্যন্ত ধাপ 4-7 পুনরাবৃত্তি করুন।

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

উপসংহার

আমি আশা করি যে আপনি এখন জাভাস্ক্রিপ্টে ইনঅর্ডার, প্রি-অর্ডার এবং পোস্টঅর্ডার ট্রাভার্সালের মধ্যে পার্থক্য সম্পর্কে স্পষ্টভাবে বুঝতে পেরেছেন। প্রদত্ত জ্ঞান এবং উদাহরণ সহ, আপনি এখন এই কৌশলগুলি আপনার নিজের কাজ এবং প্রকল্পগুলিতে কার্যকরভাবে প্রয়োগ করতে সজ্জিত।