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