C++ Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree

ถ้า binary tree ถูก traverse แบบ post-order จะเยี่ยม left subtree ก่อน แล้ว right sub-tree และภายหลังถึง root นี่คือ C++ Program สำหรับ Post Order Tree traversal โดยไม่ใช้ recursion เราทำโปรแกรมนี้โดยใช้ stack

Algorithm

For postorder traversal:

Begin
    Declare postorder_traversal(struct node*t,struct tree**top)
        if(t==NULL) then
            print "Empty Tree".
            Return.
        Print "Postorder Data Using Stack :".
        Call push(t,top) function to insert values.
        Declare a pointer store against tree structure.
            Initialize struct tree*store=NULL.
        while(t!=NULL)
            store=*top;
            if(store->v==0) then
                if(t->r!=NULL) then
                    (store->v)++
                    push(t->r,top)
                if(t->l!=NULL) then
                    (store->v)++
                    push(t->l,top)
                if(store->v==0) then
                    cout<d
                    t=NULL
                    pop(top)
                else
                    cout<d
                    t=NULL
                    pop(top)
            if(*top!=NULL) then
                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