今天把二叉樹的非遞歸遍歷實現(xiàn)了 后序的有點難度 呵呵

#include <stdio.h>
#include <stdlib.h>

typedef struct BitNode
{
char data;
BitNode *lchild,*rchild;
int ltag,rtag;
}BitNode,*BitTree,ElemType;         //樹的結(jié)構體定義

typedef struct node
{
ElemType stack;
struct node *next;
}linkstack;             //棧的結(jié)構體定義

int initstack(linkstack **s)//初始化一個帶頭結(jié)點的空棧
{
*s=(linkstack *)malloc(sizeof(linkstack));
if(*s==NULL)exit(-1);
(*s)->next=NULL;
return 1;
}

int push(linkstack *s,ElemType *x)//入棧操作,，將x的數(shù)據(jù)元素插入棧s中,，使x成為新的棧頂元素
{
linkstack *p,*q;
q=s;
p=(linkstack *)malloc(sizeof(linkstack));
if(!p)exit(-1);
p->stack=*x;
p->next=NULL;
while(q->next)
   q=q->next;
q->next=p;
return 1;
} 
/////////////////////////////////////////////////
//因為非遞歸遍歷算法 調(diào)用的棧不需要 全部出棧
//進棧的鏈表實現(xiàn)的 真正算法為
// q->stack=*x;
// q->next=S->next;
// S->next=q;
////////////////////////////////////////////////

int pop(linkstack *s,ElemType *e)//出棧操作,先將棧s的棧頂結(jié)點的值送到e所指向的內(nèi)存單元，然后刪除棧頂結(jié)點
{
linkstack *p,*q;
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
   q=p;
   p=p->next;
}
q->next=NULL;
*e=p->stack;
free(p);
return 1;
}

int emptystack(linkstack *s)//判斷棧是否為空
{
if(s->next==NULL)return 1;
else return 0;
}

int gettop(linkstack *s,ElemType *e)
{
linkstack *p,*q; 
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
   q=p;
   p=p->next;
}
*e=p->stack;
return 1;
}

BitTree CreateBiTree()
{
BitTree bt;
char x;
x=getchar();
if(x=='#') bt=NULL;
else
{
   bt=(BitTree)malloc(sizeof(BitNode));
   bt->data=x;
   bt->lchild=NULL;
   bt->rchild=NULL;
   bt->lchild=CreateBiTree();
   bt->rchild=CreateBiTree();
}
return bt;
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸先序遍歷 二叉樹
//Algorithm:沿著左指針訪問沿途經(jīng)過的根節(jié)點,，同時將右指針進棧,，以便在遞歸訪
//問左子樹完成后能得到右子樹的根節(jié)點的地址，如此重復進行,，直到?？铡?br>//////////////////////////////////////////////////////////////////////////
void PreOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while(p||!emptystack(S))
{
   while (p)
   {
    printf("%c ",p->data);
    push(S,p);
    p=p->lchild;
   }
   if(pop(S,q))
    p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸中序遍歷 二叉樹
//Algorithm:先沿著左指針走到二叉樹中最左下的結(jié)點,，即左指針為空的結(jié)點,，將沿
//途經(jīng)過的根節(jié)點，指針進棧,。當左指針為空時,，從棧中取出根節(jié)點訪問，然后再跳
//到右子樹上,。
//////////////////////////////////////////////////////////////////////////
void InOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while (p||!emptystack(S))
{
   while (p)
   {
    push(S,p);
    p=p->lchild;
   }
   pop(S,q);
   printf("%c",q->data);
   p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸后續(xù)遍歷 二叉樹
//Algorithm:先沿著左指針走到二叉樹中最左下的結(jié)點,，將沿途經(jīng)過的根節(jié)點指針進
//棧，若右子樹為空,，則彈棧并訪問根節(jié)點,，否則，跳到右子樹上,。
//////////////////////////////////////////////////////////////////////////
void PostOrderBiTree(BitTree T)
{
    linkstack *S;
    BitTree p,q;
    char flag;//標記訪問過的節(jié)點
    initstack(&S);
    q=(BitTree)malloc(sizeof(BitNode));
    p=T;
    while (p||!emptystack(S))
    {
        if(p!=q)
        {
            while(p)                                                  //當子樹p不為空時 進棧
            {
                push(S,p);                                              
                if(p->lchild)p=p->lchild;                       //不為空 后移指向左子樹
                else p=p->rchild;                                //為空指向 右子樹
            }
        }
        if (emptystack(S))break;                       
        gettop(S,q);
        if(q->rchild==p)                                        //判斷是 遍歷過 右子樹 如遍歷過右子樹 說明該遍歷根子樹
        {
            p=(BitTree)malloc(sizeof(BitNode));
            pop(S,p);
            printf("%c",p->data);
            p=q;
            flag = p->data;                                   //記錄 遍歷過的子樹
        }
        else
        {
            p=q->rchild;
            if (flag == p->data)//如果根節(jié)點的右子樹剛剛訪問完成,，那么打印根節(jié)點。
            {
                p=(BitTree)malloc(sizeof(BitNode));
                pop(S,p);
                printf("%c",p->data);
                p=q;
                flag = p->data;
            }
        }
  
    }
}

前序,、中序、后序的非遞歸遍歷中,，要數(shù)后序最為麻煩,，如果只在棧中保留指向結(jié)點的指針，那是不夠的,，必須有一些額外的信息存放在棧中,。
方法有很多，這里只舉一種,，先定義棧結(jié)點的數(shù)據(jù)結(jié)構
typedef struct{Node * p; int rvisited;}SNode //Node 是二叉樹的結(jié)點結(jié)構,，rvisited==1代表p所指向的結(jié)點的右結(jié)點已被訪問過。

lastOrderTraverse(BiTree bt){
　　//首先,，從根節(jié)點開始,，往左下方走，一直走到頭,，將路徑上的每一個結(jié)點入棧,。
　　p = bt;
　　while(bt){
　　　　push(bt, 0); //push到棧中兩個信息，一是結(jié)點指針，一是其右結(jié)點是否被訪問過
　　　　bt = bt.lchild;
　　}

　　//然后進入循環(huán)體
　　while(!Stack.empty()){ //只要棧非空
　　　　sn = Stack.getTop(); // sn是棧頂結(jié)點

　　　　//注意,，任意一個結(jié)點N,，只要他有左孩子，則在N入棧之后,，N的左孩子必然也跟著入棧了(這個體現(xiàn)在算法的后半部分)，所以當我們拿到棧頂元素的時候,，可以確信這個元素要么沒有左孩子,，要么其左孩子已經(jīng)被訪問過，所以此時我們就不關心它的左孩子了,，我們只關心其右孩子,。

　　　　//若其右孩子已經(jīng)被訪問過，或是該元素沒有右孩子,，則由后序遍歷的定義,，此時可以visit這個結(jié)點了。
　　　　if(!sn.p.rchild || sn.rvisited){
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else //若它的右孩子存在且rvisited為0,，說明以前還沒有動過它的右孩子,，于是就去處理一下其右孩子。
　　　　{ 
　　　　　　//此時我們要從其右孩子結(jié)點開始一直往左下方走,，直至走到盡頭,，將這條路徑上的所有結(jié)點都入棧。

　　　　　　//當然,，入棧之前要先將該結(jié)點的rvisited設成1,，因為其右孩子的入棧意味著它的右孩子必將先于它被訪問(這很好理解，因為我們總是從棧頂取出元素來進行visit),。由此可知,，下一次該元素再處于棧頂時，其右孩子必然已被visit過了,，所以此處可以將rvisited設置為1,。
　　　　　　sn.rvisited = 1;

　　　　　　//往左下方走到盡頭，將路徑上所有元素入棧
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0){
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}//這一輪循環(huán)已結(jié)束,，剛剛?cè)霔５哪切┙Y(jié)點我們不必管它了,，下一輪循環(huán)會將這些結(jié)點照顧的很好。
　　}
}