বাইনারি ট্রি ইন-অর্ডারে ট্রাভার্স করলে প্রথমে বাম সাবট্রি, তারপর রুট এবং শেষে ডান সাবট্রি ভিজিট করা হয়। ইন-অর্ডার ট্রাভার্সালে কীগুলো 오름차াক্রমে আউটপুট হয়। এটি রিকারশন ছাড়া ইনঅর্ডার ট্রি ট্রাভার্সালের C++ প্রোগ্রাম।
অ্যালগরিদম
Begin
n স্ট্রাকচার ডিক্লেয়ার করুন (d ইন্টিজার, l এবং r পয়েন্টার)।
কনস্ট্রাক্টর ডিক্লেয়ার করুন।
inOrder(struct n *root) ফাংশন ডিক্লেয়ার করুন।
stack s ডিক্লেয়ার করুন।
n *current = root ইনিশিয়ালাইজ করুন।
while (current != NULL || s.empty() == false)
while (current != NULL) s.push(current), current = current->l
current = s.top(); s.pop()
print current->d
current = current->r
ট্রিতে নোড ইনসার্ট করুন।
inOrder(root) কল করুন ট্রাভার্স করতে।
End.উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct n {
int d;
struct n* l;
struct n* r;
n(int d) { this->d = d; l = r = NULL; }
};
void inOrder(struct n *root) {
stack<n*> s;
n *current = root;
while (current != NULL || s.empty() == false) {
while (current != NULL) {
s.push(current);
current = current->l;
}
current = s.top();
s.pop();
cout << current->d << " ";
current = current->r;
}
}
int main() {
struct n* root = new n(6);
root->l = new n(4);
root->r = new n(7);
root->l->l = new n(8);
root->l->r = new n(5);
root->r->l = new n(9);
root->r->r = new n(10);
inOrder(root);
return 0;
}আউটপুট
8 4 5 6 9 7 10
