ট্রি ট্রাভার্সাল হল গ্রাফ ট্রাভার্সালের একটি ফর্ম। এটা ঠিক একবার গাছের প্রতিটি নোড চেক বা মুদ্রণ জড়িত. একটি বাইনারি সার্চ ট্রির প্রি-অর্ডার ট্রাভার্সাল ট্রির প্রতিটি নোডকে ক্রমানুসারে পরিদর্শন করে (রুট, বাম, ডান)।
বাইনারি গাছের প্রি-অর্ডার ট্রাভার্সালের একটি উদাহরণ নিম্নরূপ।
একটি বাইনারি গাছ নিম্নরূপ দেওয়া হয়৷
প্রি-অর্ডার ট্রাভার্সাল হল:5 3 2 4 8 9
প্রি-অর্ডার নন-রিকারসিভ ট্রাভার্সাল করার জন্য একটি প্রোগ্রাম নিম্নরূপ দেওয়া হয়েছে।
উদাহরণ
#include<iostream>
#include <stack>
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 preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node->right);
if (temp_node→left)
nodeStack.push(temp_node->left);
}
}
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, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
} আউটপুট
Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9
উপরের প্রোগ্রামে, স্ট্রাকচার নোড একটি গাছের নোড তৈরি করে। এই কাঠামোটি একটি স্ব-উল্লেখযোগ্য কাঠামো কারণ এতে স্ট্রাকট নোড টাইপের পয়েন্টার রয়েছে। এই কাঠামোটি নিম্নরূপ দেখানো হয়েছে।
struct node {
int data;
struct node *left;
struct node *right;
}; CreateNode() ফাংশন একটি নোড টেম্প তৈরি করে এবং malloc ব্যবহার করে মেমরি বরাদ্দ করে। ডাটা ভ্যালু টেম্পের ডাটাতে সংরক্ষণ করা হয়। NULL তাপমাত্রার বাম এবং ডান পয়েন্টারে সংরক্ষণ করা হয়। এটি নিম্নলিখিত কোড স্নিপেট দ্বারা প্রদর্শিত হয়৷
৷struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp→data = val;
temp→left = temp→right = NULL;
return temp;
} ফাংশন preorder() একটি স্ট্যাক ব্যবহার করে প্রি-অর্ডারে গাছের উপাদানগুলি প্রিন্ট করতে। প্রথমে রুট নোড স্ট্যাকের মধ্যে ঢোকানো হয়। একটি while লুপ শুরু হয় যা স্ট্যাক খালি না হওয়া পর্যন্ত চলে। প্রথমে স্ট্যাকের টপনোড উপাদানের ডেটা প্রদর্শিত হয় এবং তারপরে, নোডটি পপ করা হয়। তারপর উপরের নোডের ডান এবং বাম নোডগুলিকে স্ট্যাকের মধ্যে পুশ করা হয়।
এই ফাংশনটি নিম্নলিখিত কোড স্নিপেট ব্যবহার করে প্রদর্শিত হয়।
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node→right);
if (temp_node→left)
nodeStack.push(temp_node→left);
}
} insertNode() ফাংশনটি তার সঠিক অবস্থানে বাইনারি ট্রিতে প্রয়োজনীয় মান সন্নিবেশ করে। যদি নোডটি NULL হয়, তাহলে createNode বলা হয়। অন্যথায়, নোডের জন্য সঠিক অবস্থানটি গাছে পাওয়া যায়। এটি নিম্নলিখিত কোড স্নিপেটে লক্ষ্য করা যেতে পারে।
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;
} main() ফাংশনে, রুট নোডকে প্রথমে NULL হিসাবে সংজ্ঞায়িত করা হয়। তারপর প্রয়োজনীয় মান সহ সমস্ত নোডগুলি বাইনারি অনুসন্ধান গাছে ঢোকানো হয়। এটি নীচে দেখানো হয়েছে৷
৷struct node *root = NULL; root = insertNode(root, 5); insertNode(root, 8); insertNode(root, 3); insertNode(root, 2); insertNode(root, 6); insertNode(root, 9); insertNode(root, 4);
অবশেষে, ফাংশন preorder()টিকে গাছের রুট নোড ব্যবহার করে বলা হয় এবং সমস্ত গাছের মান প্রি-অর্ডারে প্রদর্শিত হয়। এটি নীচে দেওয়া হল৷
৷cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);
