考研笔记

板子：层序遍历与按层处理

用队列：出队一个结点，访问它，再把它的左右孩子入队。要一层一层地处理，就在每一轮开始时记下队列长度，这个长度正好是当前这一层的结点数。

代码

void LevelOrder(BiTree T) {
    BiTNode *q[MaxSize];                     // 队列存结点指针；每个结点只进队一次，不用写成循环队列
    int front = 0, rear = 0;                 // front 指向队头，rear 指向队尾的下一个位置
    if (T != NULL) q[rear++] = T;            // 空树不入队
    while (front < rear) {                   // 队列不空
        BiTNode *p = q[front++];             // 出队
        visit(p);
        if (p->lchild != NULL) q[rear++] = p->lchild;   // 左孩子先入队，所以同一层从左往右
        if (p->rchild != NULL) q[rear++] = p->rchild;
    }
}
 
int maxWidth(BiTree T) {                     // 按层处理：求树的宽度（结点最多的那一层有几个）
    BiTNode *q[MaxSize];
    int front = 0, rear = 0, ans = 0;
    if (T != NULL) q[rear++] = T;
    while (front < rear) {
        int cnt = rear - front;              // 此刻队列里恰好是完整的一层
        if (cnt > ans) ans = cnt;
        while (cnt-- > 0) {                  // 把这一层全部出队，同时把下一层全部入队
            BiTNode *p = q[front++];
            if (p->lchild != NULL) q[rear++] = p->lchild;
            if (p->rchild != NULL) q[rear++] = p->rchild;
        }
    }
    return ans;
}

复杂度：时间 ，空间 。

按层处理还能做的题

在 maxWidth 的外层循环里改一两行就行：

题目改法
树高（非递归）外层循环每转一圈，h++
第 层有几个结点转到第 圈时，直接返回 cnt
每层最右边的结点内层循环里最后一个出队的结点
WPL（2014 的另一种解法）内层循环里碰到叶子，就加上「权值 当前深度」，见 WPL

关键边界

  • int cnt = rear - front; 必须在内层循环开始之前记下来。内层循环一直在入队，rear 一直在变。
  • 队列数组要开到 （结点总数）。

易错点

  • 空树时不能把 NULL 入队，否则出队后访问 p->lchild 会出错。
  • 教材的层序遍历用的是封装好的循环队列（EnQueue / DeQueue），和这里的写法等价。

链接

反向链接