ডাটা স্ট্রাকচারে বাইনারি ট্রি ট্রাভার্সাল

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

ধরুন আমাদের এইরকম একটি গাছ আছে -

ইনঅর্ডার ট্রাভার্সাল সিকোয়েন্স হবে − 5 8 10 15 16 20 23

প্রি-অর্ডার ট্রাভার্সাল সিকোয়েন্স হবে − 10 5 8 16 15 20 23

পোস্টঅর্ডার ট্রাভার্সাল সিকোয়েন্স হবে − 8 5 15 23 20 16 10

লেভেল-অর্ডার ট্রাভার্সাল সিকোয়েন্স হবে − 10, 5, 16, 8, 15, 20, 23

অ্যালগরিদম

inorderTraverse(root):রুট খালি না থাকলে শুরু করুন, তারপর inorderTraversal(root এর বাম) রুটের মান প্রিন্ট করুন রুটের প্রিঅর্ডার ট্রাভার্সাল(রুটের বামে) প্রিঅর্ডার ট্রাভার্সাল(রুটের ডানে) শেষ হলে ইন্ডপোস্টরডার ট্রাভার্সাল(রুট):রুট খালি না থাকলে শুরু করুন, তারপর পোস্টঅর্ডারট্রাভার্সাল(রুটের বামে) পোস্টঅর্ডার ট্রাভার্সাল(রুটের ডানে) রুট এন্ডের মান প্রিন্ট করুন ifEndlevelOrderTraverse(root) :ক্যুতে রুট সন্নিবেশ নোড সংরক্ষণ করতে সারি que সংজ্ঞায়িত শুরু করুন। que খালি না থাকাকালীন, do item :=সারির সামনের অবস্থানে উপস্থিত আইটেমটির মান প্রিন্ট করুন যদি আইটেমের বাম অংশ নাল না হয়, তারপর আইটেমের ডানদিকে শূন্য না হলে que এন্ডে আইটেমের বাম অংশ ঢোকান, তারপর que এন্ডে আইটেমের ডানদিকে সন্নিবেশ করান যদি que doneEnd

উদাহরণ

#include#includeনামস্পেস ব্যবহার করে std;class node{ public:int h_left, h_right, bf, value; নোড *বাম, *ডান;};ক্লাস ট্রি{ ব্যক্তিগত:নোড *গেট_নোড(int কী); পাবলিক:নোড *রুট; tree(){ root =NULL; //শুরুতে NULL হিসাবে রুট সেট করুন } void inorder_traversal(node ​​*r); void preorder_traversal(নোড *r); void postorder_traversal(নোড *r); void levelorder_traversal(নোড *r); node *insert_node(node ​​*root, int key);};node *tree::get_node(int key){নোড *new_node; new_node =নতুন নোড; // গতিশীলভাবে একটি নতুন নোড তৈরি করুন new_node->h_left =0; new_node->h_right =0; new_node->bf =0; নতুন_নোড->মান =কী; //প্রদত্ত কী থেকে মান সঞ্চয় করুন new_node->left =NULL; new_node->right =NULL; রিটার্ন new_node;}void tree::inorder_traversal(node ​​*r){ if(r !=NULL){ //রুট উপস্থিত থাকলে, বাম - রুট - ডান inorder_traversal(r->left) দেখুন; cout < মান <<" "; inorder_traversal(r->ডান); }} void tree::preorder_traversal(node ​​*r){ if(r !=NULL){ //রুট উপস্থিত থাকলে, বাম - রুট - ডান কউট < মান <<" "; preorder_traversal(r->বাম); preorder_traversal(r->ডান); }} void tree::postorder_traversal(node ​​*r){ if(r !=NULL){ //রুট উপস্থিত থাকলে, বাম - রুট - ডান postorder_traversal(r->left); postorder_traversal(r->ডান); cout < মান <<" "; }} void tree::levelorder_traversal(node ​​*root){ queue  que; নোড *আইটেম; que.push(root); //প্রথমে রুট ঢোকান (!que.empty()){ item =que.front(); // সম্মুখ প্রান্ত থেকে উপাদানটি পান <<আইটেম-> মান <<" "; if(item->left!=NULL) //যখন বাম শিশু উপস্থিত থাকে, queue que.push(item->left); if(item->right !=NULL) //যখন ডান শিশু উপস্থিত থাকে, queue que.push(item->right); que.pop(); //সারি থেকে আইটেমটি সরান }}নোড *ট্রি::ইনসার্ট_নোড(নোড *রুট, int কী){ if(root ==NULL){ রিটার্ন (get_node(key)); //যখন গাছ খালি থাকে, রুট হিসাবে একটি নোড তৈরি করুন } if(key value){ //যখন কী রুট মানের থেকে ছোট হয়, বাম রুট->লেফট =ইনসার্ট_নোড(রুট->বাম, কী) এ যান ); }অন্যথায় যদি(কী> রুট->মান){ //কী রুট মানের চেয়ে বড় হয়, ডান রুটে যান->right =insert_node(root->right, key); } রিটার্ন রুট; //যখন কী ইতিমধ্যে উপস্থিত থাকে, তখন এটিকে আবার ঢোকাবেন না}main(){ node *root; গাছ আমার_বৃক্ষ; // গাছে কিছু কী ঢোকান। my_tree.root =my_tree.insert_node(my_tree.root, 10); my_tree.root =my_tree.insert_node(my_tree.root, 5); my_tree.root =my_tree.insert_node(my_tree.root, 16); my_tree.root =my_tree.insert_node(my_tree.root, 20); my_tree.root =my_tree.insert_node(my_tree.root, 15); my_tree.root =my_tree.insert_node(my_tree.root, 8); my_tree.root =my_tree.insert_node(my_tree.root, 23); cout <<"ইন-অর্ডার ট্রাভার্সাল:"; my_tree.inorder_traversal(my_tree.root); cout <<"\nপ্রি-অর্ডার ট্রাভার্সাল:"; my_tree.preorder_traversal(my_tree.root); cout <<"\nপোস্ট-অর্ডার ট্রাভার্সাল:"; my_tree.postorder_traversal(my_tree.root); cout <<"\nলেভেল-অর্ডার ট্রাভার্সাল:"; my_tree.levelorder_traversal(my_tree.root);}

আউটপুট

অর্ডার ট্রাভার্সাল:5 8 10 15 16 20 23 প্রি-অর্ডার ট্রাভার্সাল:10 5 8 16 15 20 23 পোস্ট-অর্ডার ট্রাভার্সাল:8 5 15 23 20 16 10 লেভেল-অর্ডার:520 520 পূর্বে>