二叉树的遍历以及笔试题

曾经终败给现在 2022-11-28 13:34 247阅读 0赞

本篇介绍二叉树最常见的三种遍历方式：先序、中序和后序遍历方式。

### 1、定义 ###

二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。例如从L、D、R分别表示遍历左子树、访问根节点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称为先(根)序遍历、中(根)序遍历和后(根)序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。  
**先序遍历二叉树的操作定义如下：**  
若二叉树为空，则空操作；否则  
(1) 访问根结点；  
(2) 先序遍历左子树；  
(3) 先序遍历右子树。  
**中序遍历二叉树的操作定义如下：**  
若二叉树为空，则空操作；否则  
(1) 中序遍历左子树；  
(2) 访问根结点；  
(3) 中序遍历右子树。  
**后序遍历二叉树的操作定义如下：**  
若二叉树为空，则空操作；否则  
(1) 后序遍历左子树；  
(2) 后序遍历右子树；  
(3) 访问根结点。

### 2、举例，给一棵树写出其先、中、后序遍历的结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center]  
若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序序列为：-+a\*b-cd/ef；中序序列为：a+b\*c-d-e/f；后序序列为：abcd-\*+ef/-

### 3、已知一颗二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,画出这颗树 ###

（1）由后序遍历特征，根结点比在后序序列尾部，即根结点是A;  
（2）由中序遍历特征，根结点必在中间，而且其左边必须全部是左子树子孙(BDCE),其右部必全部是右子树子孙(FHG);  
（3）继而根据后序中的DECB子树可确定B为A的左孩子，根据HGF得出F为A的右孩子；依次类推，可以唯一确定一棵二叉树如图1所示。  
但是，由一棵二叉树的先序序列和后序序列不能唯一确定一棵二叉树，因为无法确定左右子树两部分。例如，如果有先序序列AB,后序序列BA,因为无法确定B为左子树还是右子树，所以可以得到如图2所示的两棵不同的二叉树。

**图1(由中序序列和后序序列确定的二叉树)**

![在这里插入图片描述][20200817231223661.png_pic_center]

**图2(两颗不同的二叉树)**

![在这里插入图片描述][20200817231137190.png_pic_center]

### 4、笔试题：二叉树的后序序列为DBFEGCA中序序列为DBAFECG,求它的先序序列 ###

(1) 由后序序列为DBFEGCA得到二叉树的根为A,由中序序列为DBAFECG得到二叉树的左子树子孙为：DB，右子树子孙为：FECG。  
(2)我们先看它的左子树子孙，由后序序列为DB，中序序列为DB得到B为A的左孩子，D为B的左孩子。  
(3)再看它的右子树子孙，由后序序列FEGC，中序序列FECG得到C为A的右孩子，C的左子树子孙为FE右孩子为G,又由后序序列FE，中序序列FE得到E为G的左孩子，F为G的左孩子  
得到二叉树如下图：  
![r)][r]  
它的先序序列为：ABDCEFG

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/2f0a8be9906f490b9abb7c720d33e552.png
[20200817231223661.png_pic_center]: /images/20221124/0d3ab2fe57d04f15b49c7508aec6849c.png
[20200817231137190.png_pic_center]: /images/20221124/9fbe2dff330941e8aa0a81a87ab5fc24.png
[r]: /images/20221124/c775de50f9b04eedbc4768423c5fae13.png