5.3 二叉树的遍历

先序、中序、后序、层次遍历的递归与非递归实现，以及由遍历序列构造二叉树。

什么是遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）和后序（LRN）三种，其中”序”指的是根结点在何时被访问。

递归遍历

1void PreOrder(BiTree T) {
2    if (T != NULL) {
3        visit(T);              // 访问根结点
4        PreOrder(T->lchild);   // 递归遍历左子树
5        PreOrder(T->rchild);   // 递归遍历右子树
6    }
7}

切换上面的下拉框，分别观察先序、中序、后序遍历。注意递归工作栈的变化：它恰好记录了从根到当前结点的路径。

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 $O(n)$。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有 $n$ 个结点且深度为 $n$ 的单支树，空间复杂度为 $O(n)$。

非递归遍历

借助栈，可以将递归算法转换为非递归算法。以中序遍历为例：

1void InOrder2(BiTree T) {
2    InitStack(S); BiTree p = T;
3    while (p || !IsEmpty(S)) {
4        if (p) {                   // 一路向左
5            Push(S, p);
6            p = p->lchild;
7        } else {                   // 出栈，访问，转向右子树
8            Pop(S, p);
9            visit(p);
10            p = p->rchild;
11        }
12    }
13}

• 先序非递归：与中序几乎一样，只是把”访问”放在入栈之前。
• 后序非递归最复杂：一个结点必须在其左右子树都访问完之后才能访问。做法是沿左孩子入栈；读栈顶（不出栈），若其右子树存在且未被访问过，转向右子树；否则出栈并访问。需要一个辅助指针 r 记录最近访问过的结点。

void PostOrder2(BiTree T) {
    InitStack(S);
    BiTNode *p = T, *r = NULL;          // r 指向最近访问过的结点
    while (p || !IsEmpty(S)) {
        if (p) {                        // 走到最左边
            Push(S, p);
            p = p->lchild;
        } else {
            GetTop(S, p);               // 读栈顶结点（非出栈）
            if (p->rchild && p->rchild != r)
                p = p->rchild;          // 右子树存在且未被访问
            else {
                Pop(S, p);
                visit(p);
                r = p;                  // 记录最近访问过的结点
                p = NULL;               // 结点访问完后，重置 p 指针
            }
        }
    }
}

层次遍历

按照层序（自上而下、自左向右）遍历二叉树需要借助一个队列：先将根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结点……如此反复，直至队列为空。

1void LevelOrder(BiTree T) {
2    InitQueue(Q);
3    BiTree p;
4    EnQueue(Q, T);                 // 根结点入队
5    while (!IsEmpty(Q)) {
6        DeQueue(Q, p);             // 队头结点出队
7        visit(p);
8        if (p->lchild != NULL)
9            EnQueue(Q, p->lchild); // 左孩子入队
10        if (p->rchild != NULL)
11            EnQueue(Q, p->rchild); // 右孩子入队
12    }
13}

由遍历序列构造二叉树

以先序 ABCDEFGHI、中序 BCAEDGHFI 为例：

typedef struct BiTNode {
    int weight;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

int wpl_PreOrder(BiTree root, int deep) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL)
        return root->weight * deep;         // 叶结点
    return wpl_PreOrder(root->left, deep + 1)
         + wpl_PreOrder(root->right, deep + 1);
}
int WPL(BiTree root) {
    return wpl_PreOrder(root, 0);
}

int Depth(BiTree T) {
    if (T == NULL) return 0;
    int l = Depth(T->lchild);
    int r = Depth(T->rchild);
    return (l > r ? l : r) + 1;       // 后序：左右子树高度的较大者 + 1
}

即时练习