[数据结构] 06 - 2 - 二叉树的遍历

6.3 - 二叉树的遍历

二叉树遍历(Traversing binary tree)是指从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问且仅被访问一次。

  • 访问:根据实际需求决定要做什么,比如打印数据、计算等(触达某个结点并不等于访问);
  • 次序:不同于线性结构(只有从头至尾、循环、双向等简单的遍历方式),树的结点之间不存在唯一的前驱和后继关系,所以需要考虑次序。

6.3.1 - 递归遍历(深度优先, DFS)

前序、中序、后序有一个共同点:都是先一路往树的深处走,走到叶子节点再回头,去走另一条分支。这种"能往深走就往深走,走不了再回退"的遍历思路,叫做深度优先遍历(DFS)。

前序、中序、后序,本质上都是深度优先遍历,它们的区别只在于访问根节点的时机不同:

  • 前序:先访问根,再深入左右子树;
  • 中序:先深入左子树,再访问根,再深入右子树;
  • 后序:先深入左右子树,最后访问根。

一、前序遍历

前序遍历:如果树为空,则返回;否则先访问根节点,然后前序遍历左子树、再前序遍历右子树。

遍历顺序是:ABDGHCEIF

代码实现:

/* 二叉树的前序遍历递归算法 */
/* 初始条件:二叉树 T 存在 */
/* 操作结果:前序递归遍历 T */
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);        /* 显示结点数据,可以更改为其他对结点的操作 */
    PreOrderTraverse(T->lchild); /* 先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 先序遍历右子树 */
}
前序遍历例子

递归进行前序遍历例子:

  • 先递归遍历左子树,沿当前结点的左孩子向下遍历,直到穷尽;
  • 遇到 H 后,H 没有左子树,所以访问右子树 K,然后返回上一级函数;
  • 因为 D 没有右子树,所以再返回上一级函数;
  • 返回至 B,访问其右子树 E,因为 E 没有左、右子树,所以返回到 B;
  • B 结束,再返回上一级 A,然后从 A 开始前序遍历右子树。

二、中序遍历

中序遍历:如果树为空,直接返回;否则从根节点开始(注意不是访问根节点),中序遍历左子树,然后访问根节点,最后中序遍历右子树

遍历顺序是:GDHBAEICF

代码实现:

void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    InOrderTraverse(T->lchild); 
    printf("%c",T->data);
    InOrderTraverse(T->rchild);
}
  • 与前序遍历相比,只是交换了一个顺序;
  • 遍历时,先一路向左深入,直到找不到左孩子为止;
  • 对于每一个结点,都等待其左子树全部遍历完毕后,再进行访问(也就是实际的操作,此处只是打印数据)。

三、后序遍历

后序遍历:如果树为空,直接返回;否则以从左到右、先叶子后结点的方式,遍历访问左右子树,最后访问根节点。

遍历顺序是:GHDBIEFCA

void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); 
    PostOrderTraverse(T->rchild); 
    printf("%c",T->data);
}
  • 后序遍历遵循左子树→右子树→根节点的访问顺序,其触达结点的顺序和前序遍历一样,只是在最后才访问根节点;

6.3.2 - 非递归遍历

前序、中序和后序遍历都可以不使用递归,而是显式地使用栈实现。

递归本身就依赖调用栈。非递归遍历的本质,就是自己用栈,模拟递归过程中系统调用栈保存节点、返回节点的行为。

一、为什么离不开栈

当函数调用另一个函数时,必须记住自己执行到了哪里,以便将来继续执行。系统通过调用栈(Call Stack)保存这些信息。

以 preorder(A) 为例(括号内是栈的情况,右侧为栈顶):

  1. 进入 preorder(A),A 压入栈(A)
  2. 调用 preorder(B),B 压入栈(A B)
  3. 调用 preorder(D),D 压入栈(A B D)
  4. D 处理完成、出栈,返回 B(A B)
  5. B 接着处理右子树,使得 E 压入栈(A B E)
  6. E 处理完成、出栈,返回 B(A B)
  7. B 处理完成、出栈,返回 A(A),按照同样方式处理 A 的右子树。

二、非递归前序遍历

思路

前序遍历的访问顺序是:根 → 左 → 右。而栈是后进先出(LIFO)的,如果想先处理左子树,那么就要先将右孩子入栈,再将左孩子出栈,这样到时候就是左孩子先出栈了(“访问”是在出栈时发生的)。

所以,算法的思路就是:

  • 根结点入栈。
  • 第一:只要栈不为空,就弹出一个结点并访问。
  • 第二:如果它有右孩子,先把右孩子入栈。
  • 第三:如果它有左孩子,再把左孩子入栈。
  • 重复以上三个操作。

C 语言实现:

void preorder(TreeNode *root) {
    if (root == NULL) return;
 
    Stack S;
    initStack(&S);
 
    push(&S, root);
 
    while (!isEmpty(&S)) {
        TreeNode *p = pop(&S);
 
        visit(p);
 
        // 注意:右孩子先入栈
        if (p->right != NULL)
            push(&S, p->right);
 
        // 左孩子后入栈,因此先出栈
        if (p->left != NULL)
            push(&S, p->left);
    }
}
  • 根节点先入栈(如果为空直接返回);
  • 每次从栈中弹出一个结点 p,并立即访问该结点(visit(p));
  • 然后先让该结点的右孩子入栈,再让左孩子入栈,这样能保证左孩子先出栈。

三、非递归中序遍历

思路

中序遍历的访问顺序是:左 → 根 → 右。中序比前序更复杂,因为不能再第一次遇到某个结点时就访问它,而是要等待它的左子树全部处理完毕。

算法的思路是,维护一个指针 p,初始指向根节点:

  • 当 p != NULL,将 p 入栈,并使 p = p->left;
  • 不断重复直到 p == NULL,说明已经触达左子树最深处;
  • 此时开始弹出栈顶,并访问;
  • 再令 p = p->right,处理其右子树;
  • 直到 p == NULL 且栈为空(p 不为空说明还有新的子树要探索,栈不为空说明还有祖先节点未处理)。

C 语言实现:

void inorder(TreeNode *root) {
    Stack S;
    initStack(&S);
 
    TreeNode *p = root;
 
    while (p != NULL || !isEmpty(&S)) {
 
        // 第一阶段:一路向左
        while (p != NULL) {
            push(&S, p);
            p = p->left;
        }
 
        // 第二阶段:访问栈顶
        p = pop(&S);
        visit(p);
 
        // 第三阶段:转向右子树
        p = p->right;
    }
}

到达最后一个左叶子结点的时候,不是直接访问然后弹栈,回到其双亲结点,而是会经历这样的过程:

  • 将左叶子结点入栈(push(&S, p)),尝试触达其左孩子(p = p->left);
  • 发现左孩子为 NULL,离开 while 循环;
  • 弹栈(弹出左叶子,p = pop(&s))、访问(visit(p)),此时栈顶是左叶子的双亲结点;
  • 尝试触达其右孩子(p = p->right),回到第一阶段;
  • 因为右孩子为 NULL,所以无法进入循环,直接进入第二阶段;
  • 弹出并访问栈顶(即叶子节点的双亲节点),完成这次回溯。

四、非递归的后序遍历

思路:

非递归的后序遍历和前、中序相比是更难的,因为其访问操作是在处理完所有的左、右子树之后进行的。相比于中序,后序遍历还需要知道一个结点的右子树是否已经全部访问。

【方法一】使用两个栈:

后序的顺序是:左→右→根,反过来就是:根→右→左,非常容易通过对前序遍历稍作修改来实现。我们可以:

  • 使用栈 S1,用前序的思路实现「根 → 右 → 左」(先左孩子,再右孩子)。
  • 访问结点时,不立即输出,而是压入第二个栈 S2。
  • 最后依次弹出 S2,得到「左 → 右 → 根」。
void postorder(TreeNode *root) {
    if (root == NULL) return;
 
    Stack S1, S2;
    initStack(&S1);
    initStack(&S2);
 
    push(&S1, root);
 
    while (!isEmpty(&S1)) {
        TreeNode *p = pop(&S1);
 
        push(&S2, p);
 
        // 注意:这里先左后右
        if (p->left != NULL)
            push(&S1, p->left);
 
        if (p->right != NULL)
            push(&S1, p->right);
    }
 
    while (!isEmpty(&S2)) {
        visit(pop(&S2));
    }
}

【方法二】只用一个栈:

沿用一路向左的思路,但当一个结点来到栈顶的时候,需进一步判断:

  • 如果它的右子树还没有处理,就先处理右子树;
  • 如果它的右子树都处理完了,就进行访问。

为了判断其右子树是否已经处理,要引入一个指针 lastVisited 记录最近一次访问完成的结点:

  • 如果 lastVisited == p->right,则说明右子树已经处理完毕,因为后序遍历中,右子树最后被访问的结点就是右子树根;
  • 否则,说明右子树还没有访问,那么就要让 p = p->right;
  • 每次访问一个节点的时候,都更新这个指针。
void postorder(TreeNode *root) {
    Stack S;
    initStack(&S);
 
    TreeNode *p = root;
    TreeNode *lastVisited = NULL;
 
    while (p != NULL || !isEmpty(&S)) {
 
        if (p != NULL) {
            // 一路向左
            push(&S, p);
            p = p->left;
        }
        else {
            // 查看栈顶,但先不弹出
            p = peek(&S);
 
            if (p->right != NULL &&
                lastVisited != p->right) {
 
                // 右子树尚未处理
                p = p->right;
            }
            else {
                // 左右子树均处理完毕
                visit(p);
                lastVisited = p;
 
                pop(&S);
                // 置空
                p = NULL;
            }
        }
    }
}

需要注意,访问完一个节点后应将其置空,否则下一次循环又会使该结点入栈并不断向左深入,造成重复处理和死循环:

  • p != NULL:表示还要沿着当前节点继续向左深入;
  • p == NULL:表示当前这条向下的路已经走完,需要回到栈中处理祖先节点。

6.3.3 - 层序遍历(广度优先, BFS)

一、什么是广度优先遍历

BFS 是一种通用的搜索策略,层序遍历是 BFS 在树结构上的典型应用。

  • DFS(深度优先搜索):优先沿一条路径不断深入,无法继续时再回溯。
  • BFS(广度优先搜索):优先访问距离起点较近的结点,逐层向外扩展。

层序遍历:若树为空,则直接返回;否则从第一层(根节点)开始访问,从上而下逐层遍历,在同一层中按从左到右的顺序逐个结点访问。

遍历顺序是:ABCDEFGHI

二、层序遍历思路

DFS 是利用栈后进先出(LIFO)的特性实现的;而 BFS 希望先发现的结点先被处理,因此利用的是队列先进先出(FIFO)的特性。

每处理一个结点,都做相同的三件事:

  1. 从队首取出一个结点;
  2. 访问该结点;
  3. 将该结点非空的左、右孩子依次加入队尾。

为什么可保证从左到右、从上到下的顺序?

  • 每一层中:双亲结点在将孩子入队时,都是先左孩子、再右孩子的顺序;
  • 对于各层:开始处理下一层的结点时,原先层的结点一定已经全部入队了,新的层总是排在原先层的所有结点之后,保证了从上到下逐层遍历。
一个例子

再次以这个二叉树为例

如上图中,初始时根节点 A 先入队:

  • 根节点 A 出队,依次让 B、C 入队(B C);
  • 队首的 B 出队、D 入队(C D);
  • C 出队、EF 入队(D E F);
  • D 出队、GH 入队(E F G H);
  • E 出队,I 入队(F G H I);
  • 队列中剩下的结点依次出队。

三、代码实现

用 C 语言实现 BFS(front:指向队首元素;rear:指向下一个可入队的位置)

void LevelOrder(TreeNode *root) {
    if (root == NULL)
        return;
 
    TreeNode *queue[MAXSIZE];
    int front = 0;
    int rear = 0;
 
    // 1. 根结点入队
    queue[rear++] = root;
 
    // 2. 队列非空时,持续遍历
    while (front < rear) {
        // 取出队首结点
        TreeNode *p = queue[front++];
 
        // 访问当前结点
        printf("%c ", p->data);
 
        // 左孩子入队
        if (p->left != NULL)
            queue[rear++] = p->left;
 
        // 右孩子入队
        if (p->right != NULL)
            queue[rear++] = p->right;
    }
}

6.3.4 - 根据遍历序列重建二叉树

一、推导遍历结果(知二推一)

有一种常见的数据结构题目,是给出前序和中序遍历结果,要求写出后序遍历的结果(或给后 / 中求前,如果不给出中序遍历是无法确定一个二叉树的)。

  • 找根:前序第一个元素、后序最后一个元素为根节点;
  • 中序分左右:利用根信息,分出左右子树,即 [左子树所有节点] 根 [右子树所有节点] ;
  • 再次找根、再分左右:在前后序中,再找子树的根节点,然后再去中序分左右,重复直到还原整个二叉树。

例题:

由中序 / 后续遍历推导前序遍历的方法

二、二叉树的建立

立二叉树的核心思想,就是利用前序遍历(根→左→右)把一串字符序列还原为一棵树的结构;

  • 仅凭前序遍历序列,无法确定唯一的一棵二叉树的结构,因为我们不知道哪些结点有空子树;
  • 为解决歧义,我们在每个结点的空指针处补上虚结点“#”,得到扩展二叉树。

代码实现:

通过一个字符串建立一个二叉链表结构的二叉树:

#include <stdio.h>
#include <stdlib.h>
 
#define OVERFLOW -2
 
typedef char TElemType;
 
typedef struct BiNode {
    TElemType data;           // 结点数据域
    struct BiNode *lchild;    // 左孩子指针
    struct BiNode *rchild;    // 右孩子指针
} BiNode, *BiTree; 
 
 
/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树,构造二叉链表表示二叉树T */
void CreateBiTree(BiTree *T)
{
    TElemType ch;
 
    scanf("%c", &ch);
    ch = str[index++];
 
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiNode));
        if (!*T)
            exit(OVERFLOW);
        (*T)->data = ch;               /* 生成根结点 */
        CreateBiTree(&((*T)->lchild)); /* 构造左子树 */
        CreateBiTree(&((*T)->rchild)); /* 构造右子树 */
    }
}
  • 遇到“#”,则将指针设为 NULL,表示一个空结点,然后返回上一层;
  • 遇到正常字符,malloc 动态生成一个结点,赋值,然后递归建立左右子树。

6.3.5 - 二叉树遍历的应用

一、求二叉树高度

回顾二叉树高度:从根结点到最远叶子结点所经过的边数(或结点数,根据定义不同略有差异,通常指最大层数)。

思路:后序遍历

  • 一棵树的高度等于其左子树高度和右子树高度的较大值,再加上根结点这一层(+1);
  • 后序遍历是在完整地访问了所有的左、右子树之后才访问根节点,天然适合这个问题,每个结点的“访问”操作就是计算【左、右子树高度的较大值 + 1】并返回。

代码实现:

int treeHeight(TreeNode* root) {
    // 退出条件
    if (root == NULL) {
        return 0; // 空树高度为 0
    }
    int leftH = treeHeight(root->left);   // 递归求左子树高度
    int rightH = treeHeight(root->right); // 递归求右子树高度
    
    // 当前树高度 = 左右子树较大值 + 1
    return (leftH > rightH ? leftH : rightH) + 1;
}

二、统计结点数

思路:后序遍历

  • 通过遍历整棵树,就可以解决这个问题;
  • 每个结点的“访问”操作是【将左、右子树的高度求和 + 1】。

代码实现:

int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    // 左子树结点数 + 右子树结点数 + 根结点本身 (1)
    return countNodes(root->left) + countNodes(root->right) + 1;
}

三、统计叶子结点数

思路:叶子节点的特征是左、右孩子都为空,只在这种情况下返回 1,其他时候就只返回【左、右子树的叶子数求和】即可,而不再每次都 + 1(也就是让实际的数量增加只发生在叶子节点)

代码实现:

int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    // 左右子树都为空,说明是叶子结点
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    // 递归累加左右子树中的叶子结点数
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

四、判断两棵二叉树是否相同

“相同”的定义:两棵树的结构完全一致,并且对应位置上的结点值完全相同。

核心思路:同时遍历两棵树的对应结点,逐一比对

  1. 如果两棵树的当前结点都为空,说明对应位置匹配,返回 true。
  2. 如果其中一棵为空、一棵不为空,说明结构不匹配,返回 false。
  3. 如果两棵树都不为空,但根结点的值不相等,返回 false。
  4. 状态转移: 当前根结点相同后,还需判断“左子树相同”且“右子树相同”。

代码实现:

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL && q == NULL)    return true;
    if (p == NULL || q == NULL)    return false;
    if (p->val != q->val)          return false;
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

五、二叉树的镜像与结构变换

二叉树镜像(翻转二叉树)

给定一棵二叉树的根节点 root,要求把整棵树变成它的镜像树:

  • 对树中的每一个节点,都把它的左子树和右子树交换;

  • 节点中存储的值不变;

  • 空节点仍然为空;

  • 返回翻转后的根节点。

思路:

  • 递归终止条件:如果当前结点为空,返回 NULL (空树的镜像还是空树);
  • 处理当前结点:交换左、右孩子;
  • 递归处理左右子树;

代码实现:

TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    
    // 交换当前结点的左右子树指针
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    // 递归对左右子树内部进行镜像翻转
    invertTree(root->left);
    invertTree(root->right);
    
    return root;
}