二叉树的遍历算法

1.前言

定义：二叉树的遍历指按某条搜索路径访问树种的每个结点，使得每个结点均被访问一次，而且仅仅被访问一次。

二叉树的链式存储结构如下：

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

2.先序遍历

如果二叉树为空树，则什么也不做；否则

1）访问根结点

2）先序遍历左子树

3）先序遍历右子树

递归算法描述如下：

void PreOrder(BiTree T)
{
    if(T!=NULL)
    {
        visit(T);	//访问根结点
        PreOrder(T->lchild);	//访问左子树
        PreOrder(T->rchild);	//访问右子树
    }
}

简记：根左右

3.中序遍历

若二叉树为空，则什么也不做；否则

1）中序遍历左子树

2）访问根结点

3）中序遍历右子树

递归算法描述如下：

void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

简记：左根右

4.后序遍历

若二叉树为空，则什么也不做；否则

1）后序遍历左子树

2）后序遍历右子树

3）访问根节点

递归算法描述如下：

void PostOrder(BiTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

简记：左右根

5.层次遍历

算法描述如下：

void LevelOrder(BiTree T)
{
    InitQueue(Q);	//初始化辅助队列
    BiTree p;	
    EnQueue(Q,T);	//根结点入队
    while(!isEmpty(Q))	//队列不空，则继续循环
    {
        DeQueue(Q,p);	//队头结点出队
        visit(p);	//访问出队结点
        if(p->lchild!=NULL)
        {
            //左子树不空，则左子树根结点入队
            EnQueue(Q,p->lchild);
        }
        
        if(p->rchild!=NULL)
        {
            //右子树不空，则右子树根结点入队
            EnQueue(Q,p->rchild);
        }
    }
}