二叉树的遍历

二叉树的操作有很多种，其中最常用的是二叉树的遍历。二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使得每个结点都被仅且访问一次。
通过一次完整的遍历，可使二叉树中的结点由原来的非线性序列变为某种意义的线性序列。根据根节点访问的顺序不同，遍历的顺序分为前序遍历，中序遍历，后序遍历。

二叉树的遍历方法与算法实现

二叉树

先序遍历

先序遍历的递归定义：如果二叉树为空，则遍历的结果为空，否则：

• 访问根节点
• 先序遍历左子树
• 先序遍历右子树

以上图作为遍历对象的话：

• 先访问根节点A
• 先序遍历根节点的左子树，然后继续按照先序遍历的顺序

• 先访问结点B

• 访问结点D
  • 左子树为空
  • 访问结点E
• 访问结点f
  • 访问结点G
  • 右子树为空
• 访问右子树结点C

最终得到的遍历序列为： ABDEfGC

二叉树先序遍历递归算法的实现

void Preorder(BinTree t)
{
    if(t!=NULL)
    {
        printf("%c ",t->data);
        preOrder(t->leftChild);
        preOrder(t->rightChild);
    }
}

二叉树先序遍历非递归算法的实现

因为进行的顺序为从根节点开始，沿着左子树一直找下去，找到底，然后返回到最近找过的结点的右子树。所以需要记录访问过的根节点，便于往回走，由于是先让根节点一个个记录起来，然后在返回的时候找最近刚找过的根节点，所以符合栈的特性（先进先出），用顺序栈存储即可。

#define MAXSIZE 100
void Preorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    //找到底，且栈中没有可以回去的结点时，遍历结束
    while(p!=NULL || top>0)
    {
        //找左子树，找到头为止
        while(p!=NULL)
        {
            printf("%c ",p->data);  //访问结点的指针域
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        //找右子树
        --top;
        p = stack[top];
        p = p->rightChild;
    }
}

按先序序列建立二叉树

建立二叉树时的输入的树为把树的每一个叶子结点的孩子结点填充为'#'。

void CreatBintree(BinTree *root)
{
    char ch;
    if((ch=getchar())=='#') //从键盘上输入二叉树结点数值到#截止
        *root = NULL
    else
    {
        *root = (BinNode*)malloc(sizeof(BinNode));
        (*root)->data = ch;
        CreatBintree(&((*root)->leftChild));
        CreatBintree(&((*root)->rightChild));
    }
}

中序遍历

中序遍历的递归定义：如果二叉树为空，则遍历的结果为空，否则：

• 中序遍历根节点的左子树
• 访问根节点
• 中序遍历根节点的右子树

有了先序遍历的经验，以上图作为遍历对象的话：
最终得到的遍历序列为：DEBGfAC

二叉树中序遍历递归算法实现

void Inorder(BinTree t)
{
    if(t!=NULL)
    {
        InOrder(t->leftChild);
        printf("%c ",t->data);
        InOrder(t->rightChild);
    }
}

二叉树中序遍历非递归算法实现

对于中序遍历与先序遍历不同的是访问的顺序不同，但同样要用栈来记录

#define MAXSIZE 100;
void Inorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    while(p!=NULL || top>0)
    {
        //先遍历到底再访问结点
        while(p!=NULL)
        {
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        top--;
        p = stack[top];
        printf("%c ",p->data);  //访问结点的指针域
        p = p->rightChild;
    }
}

后序遍历

后续遍历的递归定义：若二叉树为空，遍历结果为空，否则：

• 后序遍历根节点的左子树
• 后续遍历根节点的右子树
• 访问根节点

以上图为遍历对象的话
遍历结果的序列为：EDGfBCA

二叉树后序遍历递归算法实现

void Posorder(BinTree t)
{
    if(t!=NULL)
    {
        Posorder(t->leftChild);
        Posorder(t->rightChild);
        printf("%c ",t->data);
    }
}

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

与前序遍历和中序遍历不同的是你跑完了左子树和右子树才能访问根节点，此时当你遍历完左子树时，你需要回到根节点，但是此时你还不能访问，因为你要先遍历右子树所以你还要根结点再次入栈，然后下次在出栈的时候才能访问，所以这里用一个标记来处理

#define MAXSIZE 100
typedef struct
{
    BinTree link;
    int flag;
}stackType;
void Posorder2(BinTree t)
{
    if(t==NULL)
        return ;
    stackType stack[MAXSIZE];
    BinTree p;
    int top = 0;
    while(p!=NULL || top>0)
    {
        if(p!=NULL)
        {
            //结点第一次进栈
            stack[top].link = p;
            stack[top].flag = 0;
            //找结点的左儿子
            p = p->leftChild;
            top++;
        }
        else
        {
            top--;
            p = stack[top].link;
            sign = stack[top].flag;
            if(sign==0)
            {
                //第二次进栈
                stack[top].link = p;
                stack[top].flag = 1;
                top++;
                p = p->rightChild;
            }
            else
            {
                //访问该结点的数据域
                printf("%c ",p->data);
                //找完讲p置为空防止在继续往左找下去
                p = NULL;
            }
        }
    }
}

二叉树的层序遍历

对于先序，中序，后序来说，他们属于深度遍历，也就是先探到低然后再折回来。对于层序遍历来说，顾名思义，就是一层一层的扫过去，所以层序遍历的方法为先上层在下层，同层之间，从左到遍历过去。从这样的遍历描述可以看出该遍历为广度遍历，可用队列来实现。
上图的遍历结果为： ABCDfEG

#define Error 0
#define OK 1
#define MAXSIZE 100
typedef char DataType;
typedef struct node
{
    DataType data;
    struct node* leftChild;
    struct node* rightChild;
}BinNode;
typedef BinNode* BinTree;
typedef BinTree ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}SeQueue;
typedef int Status;

Status InitQueue(SeQueue *q)
{
    q->front = 0;
    q->rear = 0;
    return OK;
}
int EmptyQueue(SeQueue *q)
{
    if(q->rear == q->front)
        return 1;
    else
        return 0;
}
ElemType FrontQueue(SeQueue *q)
{
    if(EmptyQueue(q))
    {
        printf("Empty!\n");
    }
    return q->data[q->front];
}
Status DeQueue(SeQueue *q)
{
    if(EmptyQueue(q))
        return Error;
    q->front++;
    return OK;
}
Status EnQueue(SeQueue *q,ElemType e)
{
    if(q->rear == MAXSIZE)
        return Error;
    q->data[q->rear] = e;
    q->rear++;
    return OK;
}
Status LevelOrder(BinTree bt)
{
    if(bt==NULL)
        return Error;
    SeQueue q;
    InitQueue(&q);
    EnQueue(&q,bt);
    while(!EmptyQueue(&q))
    {
        BinTree tmp = FrontQueue(&q);   //获取队头元素
        printf("%c",tmp->data);
        //同层元素从左到右进行遍历
        if(tmp->leftChild!=NULL)        
            EnQueue(&q,tmp->leftChild);
        if(tmp->rightChild!=NULL)
            EnQueue(&q,tmp->rightChild);
        DeQueue(&q);
    }
    printf("\n");
    return OK;
}