基本介紹
- 中文名：後序遍歷
- 外文名：PROCEDURE POSTRAV(B
- 形式：若二叉樹為空結束
- 後根：: abcd-*+ef/-
- 別稱：後序遍歷
遞歸算法,非遞歸算法,
遞歸算法
後根: abcd-*+ef/- 
算法描述：
（1）若二叉樹為空，結束
（2）後序遍歷左子樹
（3）後序遍歷右子樹
（4）訪問根結點偽代碼
PROCEDURE POSTRAV(BT)
IF BT<>0 THEN
{
POSTRAV(L(BT))
POSTRAV(R(BT))
OUTPUT V(BT)
}
RETURN
c語言描述
struct btnode
{
int d;
struct btnode *lchild;
struct btnode *rchild;
};
void postrav(struct btnode *bt)
{
if(bt!=NULL)
{
postrav(bt->lchild);
postrav(bt->rchild);
printf("%d ",bt->d);
}
}
非遞歸算法
算法1（c語言描述）：
void postrav1(struct btnode *bt)
{
struct btnode *p;
struct
{
struct btnode *pt;
int tag;
}st[MaxSize];
}
int top=-1;
top++;
st[top].pt=bt;
st[top].tag=1;
while(top>-1) /*棧不為空*/
{
if(st[top].tag==1) /*不能直接訪問的情況*/
{
p=st[top].pt;
top--;
if(p!=NULL)
{
top++; /*根結點*/
st[top].pt=p;
st[top].tag=0;
top++; /*右孩子結點*/
st[top].pt=p->p->rchild;
st[top].tag=1;
top++; /*左孩子結點*/
st[top].pt=p->lchild;
st[top].tag=1;
}
}
if(st[top].tag==0) /*直接訪問的情況*/
{
printf("%d ",st[top].pt->d);
top--;
}
}
}
算法2：
void postrav2(struct btnode *bt)
{
struct btnode *st[MaxSize],*p;
int flag,top=-1;
if(bt!=NULL)
{
do
{
while(bt!=NULL)
{
top++;
st[top]=bt;
bt=bt->lchild;
}
p=NULL;
flag=1;
while(top!=-1 && flag)
{
bt=st[top];
if(bt->rchild==p)
{
printf("%d ",bt->d);
top--;
p=bt;
}
else
{
bt=bt->rchild;
flag=0;
}
}
}while(top!=-1)
printf("\n");
}
}
