二叉树的三种金典遍历法
1.前序遍历法：
前序遍历（DLR）
前序遍历（DLR）
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
如上图所示二叉树
前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树
遍历结果：ABDECF
中序遍历，也叫中根遍历，顺序是 左子树，根，右子树
遍历结果：DBEAFC
后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根
遍历结果：DEBFCA
2.中序遍历法：
中序遍历
中序遍历（LDR）
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
3.后序遍历法：
后序遍历
简介
后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。
递归算法
算法描述：
（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");
}
}
老曹回答 必属佳作 记得给分 谢谢合作！
