女神一直不懂遍历二叉树，半夜突然给我发了一条消息

vlambda
2021-08-08

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

简介

作者简介：青铜码农，和大多数同学一样从零开始一步步学习，一步步积累。期待您的关注，让我们一起成长~注：本人学疏才浅，文章如有错误之处，敬请指正~

本章节内容简介：主讲二叉树的遍历原理、4大遍历方法、4大遍历算法。

一、二叉树的遍历原理

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点使得每个结点被访问一次，且仅被访问一次。
二叉树的遍历次序不同于线性结构。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点将面临不同的选择。

二、二叉树的遍历方法

二叉树的遍历方式主要分为以下4种：

前序遍历

中序遍历

后序遍历

层序遍历

1.前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图，遍历的顺序为：ABDGHCEIF

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

2.中序遍历

若树为空，则空操作返回，否则从根结点开始， (注意并不是先访问根结点) ，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图，遍历顺序为：GDHBAEICF

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

3.后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如下图，遍历顺序为：GHDBIEFCA

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

4.层序遍历

若树为空，则空操作返回，否则从树的第1层也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图，遍历顺序为：ABCDEFGHI

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

以上4种遍历的方法，给程序的实现带来了好处。因为对计算机来说，它只有循环、判断等方式来处理，也就是说它只会处理线性序列，而我们提到的4种遍历方法，其实都是把树中的结点变成某种意义的线性序列。

三、遍历算法

二叉树的定义是用递归的方式，所以实现遍历算法，也可以采用递归。

1.前序遍历算法

相关代码如下：

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

现在有如下图这棵二叉树T：

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

当调用 PreOrderTraverse( BiTree T ) 函数时，我们来看看程序是如何运行的：

这里有必要做个说明，请认真看，以免影响接下来的阅读。

下文出现的PT(T->lchild)代表PreOrderTraverse(T->lchild); 同样的，PT(T->rchild)代表PreOrderTraverse(T->rchild);

”往下执行“代表程序将运行到下一行代码。

”A左B”表示结点A的左孩子B，同样的，“A右C”表示结点A的右孩子C。

(过程难免有点繁琐，请一定要耐心看下去！)

(1)调用 PreOrderTraverse(T) ，T根结点不为null，所以执行 printf打印A

(2)往下执行PT(A->lchild)，访问了A左B，不为null， printf打印B

(3)再次递归调用PT(B->lchild)，访问了B左D，不为null， printf打印D

(4)再次递归调用PT(D->lchild)，访问了D左H，不为null， printf打印H

(5)再次递归调用PT(H->lchild)，访问了H的左孩子，为null，返回此函数调用处，也就是PT(H->lchild)处，才往下执行PT(H->rchild)，访问了H右K，不为null， printf打印K

(6)再次递归调用PT(K->lchild)，访问了K的左孩子，为null，返回PT(K->lchild)处，往下执行PT(K->rchild)，访问了K的右孩子，为null，返回PT(K->rchild)处，至此，此函数执行完毕。程序返回上一级函数PT(H->rchild)处，也执行完毕，返回上上一级函数PT(D->lchild)处，往下执行PT(D->rchild)，访问D的右孩子，为null，返回PT(D->rchild)处，又执行完毕。返回PT(B->lchild)处，往下执行PT(B->rchild)，访问了B右E，不为null， printf打印E

(7)执行PT(E->lchild)，访问E左，为null，返回PT(K->lchild)处，往下执行PT(K->rchild)，访问E右，为null，返回 PT(K->rchild)处，函数执行完毕，返回当初调用 PT(A->lchild)处，往下执行 PT(A->rchild)，访问A右C，不为null， printf打印C

(8)之后的步骤类似前面的递归调用，依次继续打印F、I、G、J

综上，前序遍历这棵二叉树的结点顺序是：ABDHKECFIGJ

女神一直不懂遍历二叉树，半夜突然给我发了一条消息

如果到这里能够明白前序遍历算法是怎么一回事，那么恭喜你，可以继续往下看。如果没看懂，也没关系，回去重复看几遍，先跟着文章思路一边理解一边自己写出来，到最后自己独立完整写一遍，在脑中把整个过程捋一遍。如果做到以上几点还是看不懂的话，那不是你的问题，是我的问题。

2.中序遍历算法
别担心，中序遍历算法和前序遍历算法仅仅是代码顺序上的差异。

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

让我们来看看当调用InOrderTraverse(BiTree T)函数时，程序是如何运行的：

(1)调用InOrderTraverse(T) ,T的根结点不为null，于是调用IT(B->lchild); 访问B左D，不为null，继续调用IT(D->lchild)，访问D左H，继续调用IT(H->lchild)，访问H左孩子，为null，返回IT(H->lchild)，往下执行printf打印H

(2)再往下执行IT(H->rchild)，访问H右K，不为null，执行IT(K->lchild)，访问K的左孩子，为null，返回IT(K->lchild)，往下执行printf打印K

(3)再往下执行IT(K->rchild)，访问K右孩子，为null，返回IT(K->rchild)，至此，此函数执行完毕。返回IT(D->lchild)处，往下执行printf打印D

(4)再往下执行IT(D->rchild)，访问D的右孩子，为null，返回IT(D->rchild)处，至此，此函数执行完毕。返回IT(B->lchild)处，往下执行printf打印B

(5)再往下执行IT(B->rchild)，访问B右E，不为null，执行IT(E->lchild)，访问E的左孩子，为null，返回IT(E->lchild)处，往下执行printf打印E

(6)再往下执行IT(E->rchild)，访问E的右孩子，为null，返回IT(E->rchild)，至此，结点B的递归函数执行完毕。回到最初的IT(A->lchild)处，往下执行printf打印A

(7)再往下执行IT(A->rchild)，访问A右C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J

综上，中序遍历这棵二叉树的结点顺序是：HKDBEAIFCGJ

3.后序遍历算法

代码如下:

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