বাইনারি ট্রির পোস্ট-অর্ডার রিকার্সিভ ট্রাভার্সালের C++ প্রোগ্রাম

ট্রি ট্রাভার্সাল (Tree Traversal) গ্রাফ ট্রাভার্সালের একটি রূপ। এতে ট্রির প্রতিটি নোডকে ঠিক একবার ভিজিট বা প্রিন্ট করা হয়। বাইনারি সার্চ ট্রির পোস্ট-অর্ডার ট্রাভার্সালে নোডগুলো ভিজিট করার ক্রম হলো: বাম (Left) → ডান (Right) → রুট (Root)।

উদাহরণ

একটি বাইনারি ট্রি দেওয়া আছে (চিত্রটি অনুপস্থিত, কিন্তু ট্রাভার্সাল ফলাফল নিচে):

পোস্ট-অর্ডার ট্রাভার্সাল: 1 5 4 8 6

উদাহরণ কোড

#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 postorder(struct node *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
}

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 << "বাইনারি সার্চ ট্রির পোস্ট-অর্ডার ট্রাভার্সাল: ";
    postorder(root);
    return 0;
}

আউটপুট

বাইনারি সার্চ ট্রির পোস্ট-অর্ডার ট্রাভার্সাল: 1 3 2 9 5 4

কোড ব্যাখ্যা

node স্ট্রাকচার

struct node একটি সেলফ-রেফারেনশিয়াল স্ট্রাকচার কারণ এতে struct node* টাইপের পয়েন্টার দুটি (left, right) থাকে।

createNode() ফাংশন

একটি নতুন নোড তৈরির জন্য মেমরি অ্যালোকেট করে (malloc), ডেটা সেট করে এবং লেফট/রাইট পয়েন্টারগুলো NULL করে।

postorder() ফাংশন

রিকার্সিভ ফাংশন। বাম সাব-ট্রি, তারপর ডান সাব-ট্রি, সবশেষে রুট নোডের ডেটা প্রিন্ট করে।

insertNode() ফাংশন

বাইনারি সার্চ ট্রি প্রোপার্টি মেনে মান ইনসার্ট করে: ছোট মান বামে, বড় মান ডানে।

main() ফাংশন

রুট NULL দিয়ে শুরু করে ৪, ৫, ২, ৯, ১, ৩ মানগুলো ইনসার্ট করে। তারপর postorder(root) কল করে ট্রাভার্সাল প্রিন্ট করে।

নোট: আউটপুটে দেখা যাচ্ছে ১ ৩ ২ ৯ ৫ ৪ — এটি ইনসার্ট করা মানগুলোর ওপর ভিত্তি করে তৈরি ট্রির পোস্ট-অর্ডার ক্রম।