二叉树(一)——遍历方式

缺乏、安全感 2022-07-16 09:12 156阅读 0赞

**1、二叉树的遍历方式**  
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。  
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。  
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。  
![这里写图片描述][20161013084400610]

如上图所示的二叉树，若按前序遍历，则其输出序列为 ABDCEFGH。若按中序遍历，则其输出序列为 BDAFEHGC。若按后序遍历，则其输出序列为 DBFHGECA。

**2、前序遍历**  
根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH。

**3、中序遍历**  
先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。  
再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC。

**4、后序遍历**  
B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA。

**5、实例**  
5.1 有下列二叉树，对此二叉树前序遍历的结果为（ ）。  
![这里写图片描述][20161013084609027]

A）ACBEDGFH B）ABDGCEHF  
C）HGFEDCBA D）ABCDEFGH  
解析：先根A，左子树先根B，B无左子树，其右子树，先根D，在左子树G，连起来是ABDG。 A的右子树，先根C，C左子树E，E无左子树，有右子树为H，C的右子树只有F，连起来是CEHF。整个连起来是B答案 ABDGCEHF。

5.2 已知二叉树后序遍历是DABEC，中序遍历序列是DEBAC，它的前序遍历序列是( ) 。

A）CEDBA B）ACBED C）DECAB D）DEABC  
解析：由后序遍历可知，C为根结点，由中序遍历可知，C左边的是左子树含DEBA，C右边无结点，知根结点无右子树。先序遍历先访问根C，答案中只有A以C开头，为正确答案。

5.3 如下二叉树中序遍历的结果是（　　）。  
![这里写图片描述][20161013084637236]

A). ACBDFEG B). ACBDFGE C).ABDCGEF D).FCADBEG  
解析:首先中序遍历根F会把左右子树分开，F不会在答案的开头和结尾，排除C和D。在看F的右子树，G是E的右子树，中序遍历先访问E，再访问G，E在G前面，排除B。答案为A。

例5：如下二叉树后序遍历的结果是（　　）。  
![这里写图片描述][20161013084652408]

A) ABCDEF B) DBEAFC C)ABDECF D)DEBFCA  
解析：后序的最后一个必须是二叉树的根，快速判断答案为D。

[20161013084400610]: /images/20220716/bf758358187a4859b7fa11d58645aa03.png
[20161013084609027]: /images/20220716/e642b0e3144e48d9b9029e8a4b72168a.png
[20161013084637236]: /images/20220716/fbf27516b30e4e11a514cde9d9c9d762.png
[20161013084652408]: /images/20220716/a1140561b17542298625e0ac3b81e135.png