ট্রি ট্রাভার্সাল গ্রাফ ট্রাভার্সালের একটি রূপ। বাইনারি সার্চ ট্রির ইন-অর্ডার ট্রাভার্সালে নোডগুলো ভিজিট করার ক্রম: বাম (Left) → রুট (Root) → ডান (Right)। এই ক্রমে BST-এ নোডগুলো সর্টেড অর্ডারে প্রিন্ট হয়।
উদাহরণ
বাইনারি ট্রি (চিত্র অনুপস্থিত)। ইন-অর্ডার ট্রাভার্সাল: 1 4 5 6 8
উদাহরণ কোড
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout << "বাইনারি সার্চ ট্রির ইন-অর্ডার ট্রাভার্সাল: ";
inorder(root);
return 0;
}আউটপুট
বাইনারি সার্চ ট্রির ইন-অর্ডার ট্রাভার্সাল: 1 2 3 4 5 9
কোড ব্যাখ্যা
node স্ট্রাকচার
সেলফ-রেফারেনশিয়াল স্ট্রাকচার: int data, node* left, node* right।
createNode()
নতুন নোডের মেমরি অ্যালোকেশন, ডেটা অ্যাসাইন, চাইল্ড পয়েন্টার NULL।
inorder() ফাংশন
রিকার্সিভ: বাম সাব-ট্রি ট্রাভার্স → রুট প্রিন্ট → ডান সাব-ট্রি ট্রাভার্স।
insertNode() ফাংশন
BST ইনসার্শন লজিক: মানের তুলনা করে বাম বা ডান সাব-ট্রিতে রিকার্সিভ কল।
main()
একই মানগুলো (৪, ৫, ২, ৯, ১, ৩) ইনসার্ট করে ইন-অর্ডার ট্রাভার্সাল প্রিন্ট করে। আউটপুট সর্টেড: ১ ২ ৩ ৪ ৫ ৯।
বিশেষতা: BST-এ ইন-অর্ডার ট্রাভার্সাল সদা সর্টেড আউটপুট দেয়।
