二叉树的遍历

首发于微信公众号东哥夜谈。欢迎关注东哥夜谈，让我们一起聊聊个人成长、投资、编程、电影、运动等话题。
本帐号所有文章均为原创。文章可以随意转载，但请务必注明作者。如果觉得文章有用，欢迎转发朋友圈分享。

1 问题

这段时间在研究数据结构，在二叉树上花了不少时间，感觉终于摸到了点正确的学习方法。

以二叉树为例。二叉树的概念是从上到下的链表，每个结点有两个子树。二叉树的关键操作为遍历，遍历又分为以下几类：

先序遍历
- 递归法
- 堆栈法
中序遍历
- 递归法
- 堆栈法
后序遍历
- 递归法
- 堆栈法
层次遍历
- 队列法

所以一共有递归法、堆栈法和队列发三种方法。把这三种方法搞清楚了，遍历问题就可以说是基本解决。

下面我们以中国大学MOOC 2017年里陈越、何钦铭的数据结构第03-01题为例，说明这几种遍历的方法。

输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输入样例：

8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

最后生成的二叉树：

2 数据结构分析

层级遍历需要用到队列法。核心思想是先把根结点放入队列，然后每次从队首取出结点时，都将其子结点按从左到右的顺序放入队列。这样最后队列为空时，所有结点按从上到下、从左到右的顺序遍历结束。

输入数据为三个，大写英文字母、左孩子编号、右孩子编号。考虑用二叉树完成，需要额外用两个指针 lchild 和 rchild。故需要设置数据结构如下

typedef struct BiNode * BiTree;
struct BiNode
{
    char data[2];
    int left, right, loc;
    BiTree lchild, rchild;
};

用二叉树及链表时的一个好习惯是设置头结点。对于本题目，需要先读入结点数。我们用头结点的loc 域存放该数据。

3 队列法

用队列法遍历需要用到队列，该队列需要有两个参数，一个用来存放结点指针，一个用来存放队列下一项的指针。队列需要有存放头指针和尾指针的地方，于是还需要一个结构体来表示该队列。

于是有如下数据结构

typedef struct QNode * QPointer;
struct QNode
{
    BiTree data;
    QPointer next;
};

struct QLink
{
    QPointer front;
    QPointer rear;
};

层次遍历先将找到的根结点放入队列，然后依次取出，每次取出时将其子结点放入队列。类似二叉树，我们给队列也设置一个头结点，最初将头指针和尾指针都指向该结点，每放入一个树结点就新生成一个队列结点，将树结点的指针存放在 data 域里，同时将尾指针后移到该结点。每取出一个树结点，就将头结点后移，并将该队列结点空间释放。

对于本题目，可在数据读入的时候生成树结点，依次将每一个后输入的结点都作为前一个输入的左孩子，则最后会形成一个以输入顺序为顺序的左斜二叉树。然后我们只需要在其中找出根结点，然后根据根结点里面存储的 left/right 域，相应查找各个子结点即可。

于是有如下代码

tree->lchild = pBefore->lchild; // pBefore 为根结点的父节点，可通过遍历找到；
// 该处必须用父节点，因为后面需要断开排序好的树结点；

Queue.front = Queue.rear = (QPointer)malloc(sizeof(struct QNode)); // 生成头结点
Queue.front->data = NULL; // 原则：任何时候都不要出现随机指向的指针；
Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
Queue.rear = Queue.rear->next;
Queue.rear->data = tree->lchild; // 放入根结点
Queue.rear->next = NULL;
pBefore->lchild = pBefore->lchild->lchild; // 断开排序好的树结点
tree->lchild->lchild = NULL; // 排完序的树结点因为其子结点尚未找到，先设置为空；
// 第二次强调原则：任何时候都不要出现随机指向的指针；

while (Queue.front->next != NULL) {
    tCurrent = Queue.front->next->data;
    if(tCurrent->left != -1)
    {
        pBefore = line; // line 为原输入的乱序左斜二叉树；
        while (tCurrent->left != pBefore->lchild->loc) {
            pBefore = pBefore->lchild;
        }
        Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
        Queue.rear = Queue.rear->next;
        Queue.rear->data = pBefore->lchild;
        Queue.rear->next = NULL;
        pBefore->lchild = pBefore->lchild->lchild;
        tCurrent->lchild = Queue.rear->data;
    }
    else tCurrent->lchild = NULL;

    if(tCurrent->right != -1)
    {
        pBefore = line; // line 为原输入的乱序左斜二叉树；
        while (tCurrent->right != pBefore->lchild->loc) {
            pBefore = pBefore->lchild;
        }
        Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
        Queue.rear = Queue.rear->next;
        Queue.rear->data = pBefore->lchild;
        Queue.rear->next = NULL;
        pBefore->lchild = pBefore->lchild->lchild;
        tCurrent->rchild = Queue.rear->data;
    }
    else tCurrent->rchild = NULL;

    qTmp = Queue.front->next; // 释放已被取出的队头结点
    Queue.front->next = qTmp->next;
    free(qTmp);
} // End while

3 递归法

递归法的核心在于深入一直到最后一个结点，然后返回。用递归可以形成先序访问、中序访问和后续访问三种遍历方法。

用刚才生成的二叉树举例，即输入

8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

采用依次打印各数据的方法访问。对于先序访问，是先打印父节点，然后递归进入子结点，打印该时的父节点，再递归进入子结点。当子结点打印完毕后，返回到上一级父节点，打印其右结点，然后返回。于是有

int TPrePrint(BiTree tree)
{
    // This function printf the tree with a head Node.
    if (strlen(tree->data) == 0) {
        TPrePrint(tree->lchild);
        return 0;
    }

    printf("data: \t%s, the address is:\t%p.\n", tree->data, tree);
    printf("\tThe lchild is %p, the rchild is %p.\n", tree->lchild, tree->rchild);
    if(tree->lchild!=NULL) TPrePrint(tree->lchild);
    if(tree->rchild!=NULL) TPrePrint(tree->rchild);
    return 0;
}

这里打印的时候没有打印头结点，因为头结点不算是二叉树内容的组成部分。所以要提前设置一个判断头结点的方法，这里用的是其 data 为空。其他方法也可以，比如 loc 为负值。

对于中序访问，则可改为

int TInPrint(BiTree tree)
{
    // This function printf the tree with a head Node.
    if (strlen(tree->data) == 0) {
        TInPrint(tree->lchild);
        return 0;
    }

    if(tree->lchild!=NULL) TInPrint(tree->lchild);
    printf("%s ", tree->data);
    if(tree->rchild!=NULL) TInPrint(tree->rchild);
    return 0;
}

对于后续访问，可改为

int TPostPrint(BiTree tree)
{
    // This function printf the tree with a head Node.
    if (strlen(tree->data) == 0) {
        TPostPrint(tree->lchild);
        return 0;
    }

    if(tree->lchild!=NULL) TPostPrint(tree->lchild);
    if(tree->rchild!=NULL) TPostPrint(tree->rchild);
    printf("%s ", tree->data);
    return 0;
}

打印的结果顺序会相应有所不同。

4 堆栈法

堆栈法需要先建立堆栈。堆栈可以用单向链表的方法建立，所以需要先建立单向链表数据。堆栈与队列的结点数据内容其实一样，区别在于队列需要一个结构体，里面存储队列头尾两个指针，而堆栈只需要一个头指针即可，也就不需要结构体。所以可以直接利用队列的数据结构来做堆栈，故有

typedef struct QSNode * QSPointer;
struct QSNode
{
    BiTree data;
    QSPointer next;
};

从根结点开始，将每一个结点放入堆栈，然后移向其左孩子。当左孩子为空时，结点出栈，移向其右孩子。先序遍历和中序遍历的区别在于，先序是在结点入栈的时候访问，中序是在其结点出栈、准备移向其右孩子的时候访问。

所以，对于先序遍历，有

while (tCurrent != NULL || stack->next != NULL) {
    // tCurrent != NULL is ok to Push
    // stack->next != NULL is ok to Pop
    while(tCurrent != NULL)
    {
        sCurrent = stack->next;
        stack->next = (QSPointer)malloc(sizeof(struct QSNode));
        printf("%s ", tCurrent->data); // Visit before in stack
        stack->next->data = tCurrent;
        stack->next->next = sCurrent;
        tCurrent = tCurrent->lchild; // in stack over;
    } // End while. now tCurrent == NULL.
    if(stack->next != NULL){
        // Pop stack
        sCurrent = stack->next;
        stack->next = sCurrent->next; // Pop
        tCurrent = sCurrent->data->rchild;
    }
}

对于中序遍历，有

while (tCurrent != NULL || stack->next != NULL) {
    // tCurrent != NULL is ok to Push
    // stack->next != NULL is ok to Pop
    while(tCurrent != NULL)
    {
        sCurrent = stack->next;
        stack->next = (QSPointer)malloc(sizeof(struct QSNode));
        stack->next->data = tCurrent;
        stack->next->next = sCurrent;
        tCurrent = tCurrent->lchild; // in stack over;
    } // End while. now tCurrent == NULL.
    if(stack->next != NULL){
        // Pop stack
        sCurrent = stack->next;
        stack->next = sCurrent->next; // Pop
        tCurrent = sCurrent->data;
        printf("%s ", tCurrent->data);
        tCurrent = tCurrent->rchild;
    }
}

但对后序遍历，就有问题了。后序遍历的时候，结点入栈，然后移向其左孩子；当左孩子为空时，结点出栈（1），然后移向其右孩子。当右孩子为空时，结点出栈（2），访问该结点。

可以看出，该结点需要出栈两次，所以也需要入栈两次。在左孩子为空处返回出栈后，就需要再次入栈；直到从右孩子为空再次返回出栈，这时才需要访问。所以第一次出栈是不可访问的，第二次出栈才可以访问，我们需要一个变量跟踪其出栈次数。

所以栈结点除了像之前的栈结点那样有两个指针外，还需要一个变量用来标识其访问次数，所以栈结点需要修改为

typedef struct SNode * pSNode;
struct SNode
{
    int flag;
    BiTree data;
    pSNode next;
};

相应的遍历流程可以修改为

tCurrent = tree->lchild;
while (tCurrent != NULL || stack->next != NULL) {
    sCurrent = stack->next;
    if (tCurrent != NULL) {
        stack->next = (pSNode)malloc(sizeof(struct SNode));
        stack->next->data = tCurrent;
        stack->next->flag = 1;
        stack->next->next = sCurrent;
        tCurrent = tCurrent->lchild;
    } // End while. tree node in stack. tree->lchild == NULL;
    else
    {
        if(sCurrent->flag == 1) // Pop and go rchild
        {
            tCurrent = sCurrent->data->rchild;
            sCurrent->flag = 2; // 再次入栈
        }
        else
        {
            stack->next = sCurrent->next; // 出栈
            printf("%s ", sCurrent->data->data); // 访问
        }
    }
}