与えられた二分木のポストオーダー非再帰的トラバーサルを実行するC++プログラム

二分木がポストオーダーでトラバースされる場合、最初に左側のサブツリーにアクセスし、次に右側のサブツリーにアクセスし、次にルートにアクセスします。これは、再帰なしのポストオーダーツリートラバーサル用のC++プログラムです。ここでは、スタックを使用してプログラムを実行します。

アルゴリズム

注文後のトラバーサルの場合：

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