Tree Traversal Techniques: Inorder, Preorder, Postorder গাইড ও নোট

বাইনারি ট্রির নোডগুলি পরিদর্শন করার জন্য বিভিন্ন পদ্ধতি রয়েছে। এই পদ্ধতিগুলি হল ইনঅর্ডার, প্রি-অর্ডার, এবং পোস্ট-অর্ডার। প্রতিটি পদ্ধতি নোডগুলিকে ভিন্নভাবে পরিদর্শন করে।

১. ইনঅর্ডার ট্রাভার্সাল (Inorder Traversal)

১.১ ধারণা

ইনঅর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. বাম শিশু -> মূল নোড -> ডান শিশু

১.২ বৈশিষ্ট্য

• বাইনারি অনুসন্ধান ট্রি (BST) হলে, ইনঅর্ডার ট্রাভার্সাল গঠন করে সাজানো ডেটা।
• যখন সাজানো ডেটা প্রয়োজন, তখন এই পদ্ধতি ব্যবহার করা হয়।

১.৩ C তে উদাহরণ

#include <stdio.h>
#include <stdlib.h>

// নোডের গঠন
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// নতুন নোড তৈরি করা
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// ইনঅর্ডার ট্রাভার্সাল
void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);  // বাম subtree
        printf("%d ", root->data);      // মূল নোড
        inOrderTraversal(root->right); // ডান subtree
    }
}

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Inorder Traversal: ");
    inOrderTraversal(root); // আউটপুট: 1 2 3 4 5
    printf("\n");

    return 0;
}

২. প্রি-অর্ডার ট্রাভার্সাল (Preorder Traversal)

২.১ ধারণা

প্রি-অর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. মূল নোড -> বাম শিশু -> ডান শিশু

২.২ বৈশিষ্ট্য

• এই পদ্ধতি ব্যবহৃত হয় গাছের কপি তৈরি করার জন্য অথবা অভিব্যক্তি গাছের প্রিফিক্স এক্সপ্রেশন পেতে।
• এটি পিতৃ নোডকে প্রথমে প্রক্রিয়া করে।

২.৩ C তে উদাহরণ

// প্রি-অর্ডার ট্রাভার্সাল
void preOrderTraversal(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);      // মূল নোড
        preOrderTraversal(root->left);  // বাম subtree
        preOrderTraversal(root->right); // ডান subtree
    }
}

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Preorder Traversal: ");
    preOrderTraversal(root); // আউটপুট: 4 2 1 3 5
    printf("\n");

    return 0;
}

৩. পোস্ট-অর্ডার ট্রাভার্সাল (Postorder Traversal)

৩.১ ধারণা

পোস্ট-অর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. বাম শিশু -> ডান শিশু -> মূল নোড

৩.২ বৈশিষ্ট্য

• এই পদ্ধতি গাছটি মুছে ফেলতে ব্যবহৃত হয়, কারণ এটি নিশ্চিত করে যে শিশুর নোডগুলি পিতৃ নোডের আগে প্রক্রিয়া করা হয়।
• এটি পোস্টফিক্স এক্সপ্রেশন পেতে ব্যবহার হয়।

৩.৩ C তে উদাহরণ

// পোস্ট-অর্ডার ট্রাভার্সাল
void postOrderTraversal(Node* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);  // বাম subtree
        postOrderTraversal(root->right); // ডান subtree
        printf("%d ", root->data);      // মূল নোড
    }
}

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Postorder Traversal: ");
    postOrderTraversal(root); // আউটপুট: 1 3 2 5 4
    printf("\n");

    return 0;
}

৪. সারাংশ

• ইনঅর্ডার ট্রাভার্সাল: বাম -> মূল -> ডান। সাজানো ডেটা পাওয়ার জন্য কার্যকরী।
• প্রি-অর্ডার ট্রাভার্সাল: মূল -> বাম -> ডান। গাছের কপি তৈরি করতে ব্যবহৃত হয়।
• পোস্ট-অর্ডার ট্রাভার্সাল: বাম -> ডান -> মূল। গাছ মুছে ফেলার সময় ব্যবহৃত হয়।

এই ট্রাভার্সাল পদ্ধতিগুলি বাইনারি ট্রির সাথে কাজ করার জন্য গুরুত্বপূর্ণ, এবং বিভিন্ন অ্যালগরিদম বাস্তবায়নে ব্যবহৃত হয়।