Chương trình C++ duyệt hậu thứ tự không đệ quy của cây nhị phân

Nếu cây nhị phân được duyệt hậu thứ tự (post-order), cây con trái được thăm trước, rồi cây con phải, sau đó gốc. Đây là chương trình C++ duyệt cây hậu thứ tự không dùng đệ quy, sử dụng stack.

Thuật toán

Cho duyệt hậu thứ tự:

Begin
    Khai báo postorder_traversal(struct node*t, struct tree**top)
    if(t==NULL) then
        in "Empty Tree".
        Return.
    In "Postorder Data Using Stack :".
    Gọi push(t,top) để chèn giá trị.
    Khai báo con trỏ store trỏ đến cấu trúc tree.
        Khởi tạo 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

Ví dụ

#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;
}

Kết quả

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