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

বাইনারি ট্রি পোস্ট-অর্ডারে ট্রাভার্স করলে প্রথমে বাম সাবট্রি, তারপর ডান সাবট্রি এবং শেষে রুট ভিজিট করা হয়। এটি রিকারশন ছাড়া পোস্টঅর্ডার ট্রাভার্সালের C++ প্রোগ্রাম। এখানে স্ট্যাক ব্যবহার করা হয়েছে।

অ্যালগরিদম

Begin
    postorder_traversal(struct node*t, struct tree** top) ডিক্লেয়ার করুন
    যদি t==NULL হয় তবে "Empty Tree" প্রিন্ট করে রিটার্ন করুন।
    "Postorder Data Using Stack :" প্রিন্ট করুন।
    push(t, top) কল করুন মান ইনসার্ট করতে।
    struct tree* store=NULL ডিক্লেয়ার করুন।
    while(t!=NULL)
        store = *top
        যদি store->v==0 হয় তবে
            যদি t->r!=NULL হয় তবে (store->v)++ এবং push(t->r, top)
            যদি t->l!=NULL হয় তবে (store->v)++ এবং push(t->l, top)
            যদি store->v==0 হয় তবে cout<<d, t=NULL, pop(top)
            অন্যথায় cout<<d, t=NULL, pop(top)
        যদি *top!=NULL হয় তবে t = (*top)->link
End

উদাহরণ

#include <iostream>
#include <stdlib.h>
using namespace std;

struct node { int d; struct node *l,*r; };
struct tree { int v; struct node* link; struct tree* n; };

struct node* create_node(int);
void push(struct node*, struct tree**);
void pop(struct tree**);
void postorder_traversal(struct node*, struct tree**);

int main() {
    struct node* root = NULL;
    struct tree* top = NULL;
    root = create_node(20);
    root->l = create_node(10);
    root->r = create_node(30);
    root->r->r = create_node(7);
    root->l->l = create_node(25);
    root->l->r = create_node(35);
    root->l->r->r = create_node(40);
    root->l->l->r = create_node(26);
    postorder_traversal(root, &top);
    return 0;
}

আউটপুট

Postorder Data Using Stack : 26 25 40 35 10 7 30 20