ট্রি ট্রাভার্সাল গ্রাফ ট্রাভার্সালের একটি রূপ। এতে ট্রির প্রতিটি নোডকে ঠিক একবার চেক বা প্রিন্ট করা জড়িত। বাইনারি সার্চ ট্রির প্রি-অর্ডার ট্রাভার্সালে ট্রির প্রতিটি নোডকে (রুট, বাম, ডান) ক্রমে ভিজিট করা জড়িত।
বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সালের একটি উদাহরণ নিচে দেওয়া হলো:
একটি বাইনারি ট্রি নিচে দেওয়া হলো:
Preorder Traversal is: 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);
return 0;
}
আউটপুট
Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9
উপরোক্ত প্রোগ্রামে, node স্ট্রাকচারটি একটি ট্রির নোড তৈরি করে। এই স্ট্রাকচারটি একটি সেলফ-রেফারেনশিয়াল স্ট্রাকচার কারণ এতে struct node টাইপের পয়েন্টার রয়েছে। এই স্ট্রাকচারটি নিচে দেখানো হলো:
struct node {
int data;
struct node *left;
struct node *right;
};
createNode() ফাংশনটি একটি temp নোড তৈরি করে এবং malloc ব্যবহার করে এটিকে মেমোরি অ্যালোকেট করে। val ডেটা ভ্যালু temp-এর ডেটা-এ সংরক্ষণ করা হয়। NULL temp-এর লেফট এবং রাইট পয়েন্টারে সংরক্ষণ করা হয়। এটি নিচের কোড স্নিপেটে প্রদর্শিত হয়েছে:
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() ফাংশনটি একটি স্ট্যাক ব্যবহার করে ট্রির উপাদানগুলো প্রি-অর্ডারে প্রিন্ট করে। প্রথমে রুট নোডটি স্টাকে ইনসার্ট করা হয়। একটি হয়েল লুপ শুরু হয় যা স্ট্যাক খালি না হওয়া পর্যন্ত চলে। প্রথমে স্ট্যাকের টপ নোড এলিমেন্টের ডেটা প্রদর্শন করা হয় এবং তারপর নোডটি পপ করা হয়। তারপর উপরের নোডের ডান এবং বাম নোডগুলো স্টাকে পুশ করা হয়।
এই ফাংশনটি নিচের কোড স্নিপেটে প্রদর্শিত হয়েছে:
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);
