C++ प्रोग्राम: दिए गए बाइनरी ट्री का पोस्टऑर्डर नॉन-रिकर्सिव ट्रैवर्सल करना

यदि एक बाइनरी ट्री को पोस्ट-ऑर्डर में ट्रैवर्स किया जाता है, तो पहले लेफ्ट सबट्री देखी जाती है, फिर राइट सब-ट्री और बाद में रूट। यह रिकर्सन के बिना पोस्ट ऑर्डर ट्री ट्रैवर्सल के लिए एक C++ प्रोग्राम है। हम यहां स्टैक का उपयोग करके प्रोग्राम करते हैं।

एल्गोरिदम

पोस्टऑर्डर ट्रैवर्सल के लिए:

Begin
    postorder_traversal(struct node*t,struct tree**top) घोषित करें
        if(t==NULL) तो
            "Empty Tree" प्रिंट करें।
            Return.
        "Postorder Data Using Stack :" प्रिंट करें।
        मान डालने के लिए push(t,top) फंक्शन कॉल करें।
        ट्री स्ट्रक्चर के विरुद्ध एक पॉइंटर स्टोर घोषित करें।
            struct tree*store=NULL आरंभ करें।
        while(t!=NULL)
            store=*top;
            if(store->v==0) तो
                if(t->r!=NULL) तो
                    (store->v)++
                    push(t->r,top)
                if(t->l!=NULL) तो
                    (store->v)++
                    push(t->l,top)
                if(store->v==0) तो
                    cout<d
                    t=NULL
                    pop(top)
                else
                    cout<d
                    t=NULL
                    pop(top)
            if(*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);
struct node*create_node(int value) {
    struct node*new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node!=NULL) {
        new_node->d=value;
        new_node->l=new_node->r=NULL;
        return new_node;
    } else {
        printf("\n Memory overflow.");
        return NULL;
    }
}

void push(struct node*,struct tree*);
void push(struct node*node,struct tree**top) {
    struct tree*new_node=(struct tree*)malloc(sizeof(struct tree));
    if(new_node!=NULL) {
        new_node->link=node;
        new_node->n=*top;
        new_node->v=0;
        *top=new_node;
    } else {
        cout<<"\n Memory overflow.";
        return ;
    }
}

void pop(struct tree**);
void pop(struct tree**top) {
    if(*top!=NULL) {
        struct tree*remove=*top;
        *top=(*top)->n;
        remove->link=NULL;
        remove->n=NULL;
        remove=NULL;
    }
}

void postorder_traversal(struct node*,struct tree**);
void postorder_traversal(struct node*t,struct tree**top) {
    if(t==NULL) {
        cout<<"\n Empty Tree";
        return;
    }
    cout<<"\n Postorder Data Using Stack :";
    push(t,top);
    struct tree*store=NULL;
    while(t!=NULL) {
        store=*top;
        if(store->v==0) {
            if(t->r!=NULL) {
                (store->v)++;
                push(t->r,top);
            }
            if(t->l!=NULL) {
                (store->v)++;
                push(t->l,top);
            }
            if(store->v==0) {
                cout<<t->d;
                t=NULL;
                pop(top);
            }
        } else {
            cout<<t->d;
            t=NULL;
            pop(top);
        }
        if(*top!=NULL)
            t=(*top)->link;
    }
}

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