后序遍历二叉树的非递归算法

方法一：

#include 

#include 

#define MAX_TREE_SIZE  100

typedef struct BiTNode {

    char data;

    struct BiTNode * lchild;

    struct BiTNode * rchild;

}BiTNode, *BiTree;

//函数声明

void Print(BiTree *root);

void Selection(int sel,BiTree *root);

void ReadExPreOrder(BiTree *root);

void PrintExPreOrder(BiTree root);

void PostOrderTraverse(BiTree T);

//主函数

void main()    {

    BiTree root=NULL; //初始化根结点

    Print(&root);

    while (true)    {

        printf("\\nPress enter to continue.........");

        getchar();

        getchar();

        system("cls");

        Print(&root);

    }

}

void Print(BiTree *root)    {

  //提示

    int sel;

    printf("使用说明:本程序可实现二叉链表方式存储的二叉树，输入为扩展先序遍历序列.\\n");

    printf("---------------------\\n");

    printf("1.输入扩展先序遍历序列并建立对应的二叉树.\\n");

    printf("2.打印当前的二叉树的扩展先序遍历序列.\\n");

    printf("3.后序遍历当前的二叉树并打印遍历序列.\\n");

    printf("4.按其它任意键退出.\\n");

    printf("---------------------\\n");

    printf("请选择你要的操作:");

    scanf("%d", &sel);

    getchar();

    Selection(sel, root);

}

void Selection(int sel, BiTree *root)    {

      //根据用户输入决定下一步骤

    switch (sel) {

        case 1: ReadExPreOrder(root);

                break;

        case 2: PrintExPreOrder(*root);

                break;

        case 3: PostOrderTraverse(*root);

                break;

        default: exit(0);

    }

}

void ReadExPreOrder(BiTree *root)    {

 //先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针

    char ch;

    ch = getchar();

    if (ch == '.')

        *root = NULL;

    else {

        (*root) = (BiTree)malloc(sizeof(BiTNode));

     (*root)->data = ch;

     ReadExPreOrder(&((*root)->lchild));

     ReadExPreOrder(&((*root)->rchild));

    }

}

void PrintExPreOrder(BiTree root)    {

    char ch;

    if (root!=NULL)    {

     ch = root->data;

        printf("%c", ch);

     PrintExPreOrder(root->lchild);

     PrintExPreOrder(root->rchild);

    }

    else

        printf(".");

}

void PostOrderTraverse(BiTree T) {

    BiTree stack[MAX_TREE_SIZE], p;

    int tag[MAX_TREE_SIZE],top=0;

    p = T;

    while(p || top != 0)    {

        while(p)        {

            top++;

            stack[top]=p;

            tag[top]=0;

         p=p->lchild;//从根开始，左结点依次入栈

        }

        if(top> 0) {

          if(tag[top]==1){//表示是从该结点的右子树返回，则访问该结//点

                p=stack[top];

                printf("%c", p->data);

                top--;

                p=NULL;//将p指向NULL,则下次进入while循环时，不做左子//树入栈操作

            }

            else{ //表明是从该结点左子树返回，应继续访问其右子树

                p=stack[top];

                if(top> 0) {

                 p=p->rchild;

                    tag[top]=1;  //表明该结点的右子树已访问

                }

            } //end of else

        } //end of if

    }//end of while

}

方法二（顺序栈）：

#include

using namespace std;

typedef struct node 

{

char ch;

struct node *lchild;

struct node *rchild;

}node;

typedef struct binarytree

{

node *head;//指向根结点

}bt;

int n=0;

void ini(bt * &b)

{

b =new bt;

b->head=NULL;

}

void precreate(node * &t)//先序递归建立二叉树

{

cout<<"\\n\\n请输入结点数据，以'.'代表空:";

char c;

cin>>c;

if(c=='.') t=NULL;

else

{

n++;

t=new node;

t->ch=c;

precreate(t->lchild);

precreate(t->rchild);

}

}

//--------------------------------------------------

//非递归算法需要栈

typedef struct stack {

node **base;

node **top;

int stacksize;

}stack;

void ini(stack &s) {

s.base=new node *[100] ;

s.top=s.base;

s.stacksize=100;

}

void push(stack &s,node *elem) {

(*s.top++)=elem;

}

void pop(stack &s,node * &elem){

elem= *(--s.top);

}

int isempty(stack &s) {

if(s.base==s.top)return 1;

else return 0;

}

void gettop(stack &s,node *&t) {

t=*(s.top-1);

}

void afttraverse(node *t)  {//后序遍历非递归算法

stack s;

ini(s);

    node * lastvist = NULL;

while (NULL != t || !isempty(s))  {

        while (NULL != t)   { 

push(s,t);

             t = t->lchild;

        }

        gettop(s,t); 

if (NULL == t->rchild || lastvist == t->rchild) {     

cout<<"   "<ch;

          pop(s,lastvist);

          t = NULL;

        }

        else 

t = t->rchild;

}

}

int main() {

bt   *b;

ini(b);

precreate(b->head);//构造二叉树

cout<<"\\n\\n后序遍历: ";

afttraverse(b->head);

cout<<"\\n\\n";

}

方法三（链栈）：

#include

#include

typedef struct BiTNode  {

 char item;

 struct BiTNode *lchild,*rchild;

}BiTNode,*Tree;

typedef struct Stack{

 Tree m;

 struct Stack *next;

}Stack,*st;

Tree CreateTree()

{

    Tree B;

    char ch;

    ch=getchar();

    if(ch=='.')

       return NULL;

    else

      { 

          B=(Tree)malloc(sizeof(BiTNode));

B->item=ch;

B->lchild=CreateTree();

B->rchild=CreateTree();

          return B;

      }

}

void PostOrder(Tree T)

{

    Tree p,q;

    st s,top;

    int op;

    p=T;

    top=NULL;

    do{

        while(p!=NULL)

        {

            s=(st)malloc(sizeof(Stack));//使用链表形式存储栈,即//链栈

s->m=p;

s->next=top;

            top=s;

p=p->lchild;

        }

    op=1;//该标志用于控制进入下面的while循环

    q=NULL;

    while(top!=NULL&&op==1)

    {

        if(top->m->rchild==q) //若当前栈顶结点的右孩子是上次访问的结点，则打印该结点

        { 

            printf("%c",top->m->item);//第一次时打印最左下边结点

q=top->m; //q记录上次访问的结点

top=top->next; //栈指针后移,即将该结点从栈中弹出

        }

      else//若当前栈顶结点的右孩子不是上次访问的结点,则先访问其右孩//子

       { 

     p=top->m->rchild;

            op=0;//op用来控制往右走一步后跳出当前while循环,进入下//一次外层的while循环

       }

   }

 }while(top!=NULL);

}

int main()

{

    Tree T;

    printf("please enter the chars:\\n");

    T=CreateTree();

    PostOrder(T);

    getchar();

    getchar();

    return 0;

}

方法四：

#include  

#include  

struct TREE //二叉树结点结构

{ 

char data; 

struct TREE *lsubtree; 

struct TREE *Rsubtree; 

}; 

struct TREE *tree; 

void createtree(struct TREE *&p) //先序创建二叉树

{ 

char ch;

ch = getchar(); 

if (ch == '\\n') 

{

p = NULL; 

}

else if(ch == '.') 

p = NULL; 

else 

{ 

p = (struct TREE*)malloc(sizeof(struct TREE));//分配//结点空间

p->data = ch;

createtree(p->lsubtree); //递归创建左子树

createtree(p->Rsubtree); //递归创建右子树

}

} 

void lastorder(struct TREE *tree)//非递归后序遍历

{ 

struct TREE *p; 

struct TREE *s[100];//用一个指针数组来用作栈

int top=-1;//下标

int mack[100];//标志数组

p=tree; 

do { 

while(((p->lsubtree)!=NULL)&&(mack[top+1]!=2))//循环//直到让p向左滑到最左子树，并且该结点非第二次入栈

        { 

            top=top+1; 

            s[top]=p;//每循环一次，当前结点入栈

            mack[top]=1;//结点第一次入栈时，标志为1

            p=p->lsubtree;//找最左子树

    } //叶子结点无须入栈

        printf("%c\\n",p->data); //输出末节点

        p=s[top];//出栈顶元素

        top=top-1;//每出一个栈顶元素，下标就后退一位

        if (mack[top+1]==1)//若结点是第一次出栈，则再入栈

        { 

            top=top+1;  

            s[top]=p; 

            mack[top]=2;//结点第二次入栈时，标志为2

            p=p->Rsubtree;//访问右子树

        } 

}while (top!=-1); //top==-1时，说明根结点刚访问完，跳出循环后//打印

    printf("%c\\n",s[0]->data);//最后把根输出

}

int main(){

printf("请输入二叉树数据\\n");

createtree(tree);

printf("后序遍历结果：\\n");

lastorder(tree);

getchar();getchar();

} 

方法五：

#include 

#include 

#define maxsize 50 

#define OK 1

typedef struct Bnode //声明二叉树的数据结构

{ 

char ch; 

struct Bnode *lchild,*rchild; 

}bnode,*btree; 

typedef struct type 

{ 

btree node; 

int flag; 

}datatype,*pdatatype; 

typedef struct{ //声明栈的数据结构

datatype data[maxsize];

int top; 

}seqstack,*pseqstack; 

btree creatbtree() //创建二叉树

{ 

int i=0; 

btree t;

char c;

c=getchar();

if(c=='#') 

{ t=NULL;i++; } 

else 

     { 

t=(btree)malloc(sizeof(bnode)); 

t->data=c;i++;

t->lchild=creatbtree();

t->rchild=creatbtree();

     } 

return t; 

}

int printelem(/*ElemType */char e)

{

      printf("%c",e);

      return OK;

}

void postorder(btree t) //二叉树的后序遍历(非递归) 

{  //与教材p.131的中序遍历方法类似

pseqstack p; 

p=(pseqstack)malloc(sizeof(seqstack)); 

p->top=0;

while(t||!(p->top==0))

{ 

if(t) 

{ 

p->data[p->top].node = t;

p->data[p->top].flag = 0;

(p->top)++;

t=t->lchild;

} 

else 

{  

if(p->data[p->top-1].flag==0)

{ //若该结点右孩子没有被访问，则先访问其右孩子，并置标志为//1 

p->data[p->top-1].flag=1;

t = p->data[p->top-1].node->rchild;//t=t->rchild;

} 

else 

{//否则直接访问该结点 

                 printf("%c",p->data[p->top-1].node->ch); 

                (p->top)--;

} 

} 

} 

} 

int main() 

{ 

btree t; 

t=creatbtree(); 

printf("\\n后序遍历："); 

postorder(t); 

getchar();

getchar();

return 0;

}