二叉树的遍历

太过爱你忘了你带给我的痛 2024-04-18 23:58 13阅读 0赞

# 二叉树的遍历 #

## 概念 ##

二叉树的遍历是指按照某种顺序访问二叉树中的每一个结点,使每一个结点都被访问一次且仅被访问一次。遍历是二叉树中经常用到的一种操作。在实际应用中，常常需要按一定顺序对二叉树中的每一个结点逐个进行访问，查找具有某一特性的结点，然后对这些满足条件的结点进行相关处理操作。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。

由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树等三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有6中：DLR、DRL、LDR、LRD、RDL和RLD。

如果限定在遍历时必须先左后右，则有三种遍历方式，即DLR（称为先序遍历）、LDR（称为后序遍历）和LRD（称为后续遍历）。

### 先序遍历二叉树(DLR) ###

若二叉树非空,则

1.  访问根结点
2.  先序遍历根的左子树
3.  先序遍历根的右子树

### 中序遍历二叉树(LDR) ###

若二叉树非空,则

1.  中序遍历根的左子树
2.  访问根结点
3.  中序遍历根的右子树

### 后序遍历二叉树(LDR) ###

若二叉树非空,则

1.  后序遍历根的左子树
2.  后序遍历根的右子树
3.  访问根结点

![20190914184311572.png][]

对于如图所示的二叉树,按照先序遍历所得到的结点序列为A B D G C E F,按照中序遍历所得到的结点序列为 D G B A E C F,按照后序遍历所得到的结点序列为 G D B E F C A。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70][]

对于如图所示的二叉树:

先序遍历序列为: A B D E H I J K C F G

中序遍历序列为: D B H E J I K A F C G

后序遍历序列为: D H J K I E B F G C A

例题1:

已知一棵二叉树的先序序列和中序序列分别为K、A、F、G、I、B、E、D、H、J、C和A、G、F、K、E、D、B、H、J、I、C，试画出这棵二叉树。

分析：先序序列中的第一个元素一定是（子）树的根结点，而中序序列中左子树遍历完成才会访问根结点，所以在中序序列中，排在这个根结点前面的结点一定是其左子树上的结点，排在这个根结点后面的结点一定是其右子树上的结点。如此依次作用于各个子树，就可以画出整个二叉树的树形，而且是唯一的，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70 1][]

例题2:

已知一棵二叉树的后序序列和中序序列分别为F、B、C、G、I、E、J、D、A、H和B、F、G、C、H、I、E、A、D、J，试画出这棵二叉树。

分析：后续序列中的最后一个元素一定是（子）树的根结点，而中序序列中的左子树遍历完成才访问这个根结点，所以在中序序列中，排在这个根结点前面的结点一定是其左子树上的结点，排在这个根结点后面的结点一定是其右子树上的结点。如此依次作用于各个子树，就可以画出整个二叉树的树形，而且是唯一的，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70 2][]

参考：数据结构（第2版） 秦玉平 主编

[20190914184311572.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8940ade9b8fd434da5fa76fedf877aba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e85a0adac2bf45ca81446aa7b83852d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c1d1ab48f9ab48d892bda6c6f76785bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pZXZlcg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0ad53841197e460a8ab2b72229d93104.png