二叉树的遍历（一）

FROM:http://blog.163.com/qhx_405/blog/static/6338992620098140352928/

二叉树的遍历有三种方式&＃xff0c;如下&＃xff1a;

&＃xff08;1&＃xff09;前&＃xff08;先&＃xff09;序&＃xff08;根&＃xff09;遍历&＃xff08;DLR&＃xff09;&＃xff0c;首先访问根结点&＃xff0c;然后遍历左子树&＃xff0c;最后遍历右子树。简记根-左-右。

&＃xff08;2&＃xff09;中序&＃xff08;根&＃xff09;遍历&＃xff08;LDR&＃xff09;&＃xff0c;首先遍历左子树&＃xff0c;然后访问根结点&＃xff0c;最后遍历右子树。简记左-根-右。

&＃xff08;3&＃xff09;后序&＃xff08;根&＃xff09;遍历&＃xff08;LRD&＃xff09;&＃xff0c;首先遍历左子树&＃xff0c;然后遍历右子树&＃xff0c;最后访问根结点。简记左-右-根。 

例1&＃xff1a;如上图所示的二叉树&＃xff0c;若按前序遍历&＃xff0c;则其输出序列为?若按中序遍历&＃xff0c;则其输出序列为?若按后序遍历&＃xff0c;则其输出序列为?

前序&＃xff1a;根A&＃xff0c;A的左子树B&＃xff0c;B的左子树没有&＃xff0c;看右子树&＃xff0c;为D&＃xff0c;所以A-B-D。再来看A的右子树&＃xff0c;根C&＃xff0c;左子树E&＃xff0c;E的左子树F&＃xff0c;E的右子树G&＃xff0c;G的左子树为H&＃xff0c;没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH

中序&＃xff1a;先访问根的左子树,B没有左子树&＃xff0c;其有右子树D&＃xff0c;D无左子树&＃xff0c;下面访问树的根A&＃xff0c;连起来是BDA。

再访问根的右子树&＃xff0c;C的左子树的左子树是F&＃xff0c;F的根E&＃xff0c;E的右子树有左子树是H&＃xff0c;再从H出发找到G&＃xff0c;到此C的左子树结束&＃xff0c;找到根C&＃xff0c;无右子树&＃xff0c;结束。连起来是FEHGC,  中序结果连起来是BDAFEHGC

后序&＃xff1a;B无左子树&＃xff0c;有右子树D&＃xff0c;再到根B。再看右子树&＃xff0c;最下面的左子树是F&＃xff0c;其根的右子树的左子树是H&＃xff0c;再到H的根G&＃xff0c;再到G的根E&＃xff0c;E的根C无右子树了&＃xff0c;直接到C&＃xff0c;这时再和B找它们其有的根A&＃xff0c;所以连起来是DBFHGECA

例2:有下列二叉树&＃xff0c;对此二叉树前序遍历的结果为&＃xff08;    &＃xff09;。

A&＃xff09;ACBEDGFH                                          B&＃xff09;ABDGCEHF

C&＃xff09;HGFEDCBA                                          D&＃xff09;ABCDEFGH

解析&＃xff1a;先根A&＃xff0c;左子树先根B&＃xff0c;B无左子树&＃xff0c;其右子树&＃xff0c;先根D&＃xff0c;在左子树G&＃xff0c;连起来是ABDG。 A的右子树&＃xff0c;先根C&＃xff0c;C左子树E&＃xff0c;E无左子树&＃xff0c;有右子树为H&＃xff0c;C的右子树只有F&＃xff0c;连起来是CEHF。整个连起来是B答案 ABDGCEHF。

例3&＃xff1a;已知二叉树后序遍历是DABEC&＃xff0c;中序遍历序列是DEBAC&＃xff0c;它的前序遍历序列是(       )  。

A&＃xff09;CEDBA  B&＃xff09;ACBED C&＃xff09;DECAB D&＃xff09;DEABC

解析&＃xff1a;由后序遍历可知&＃xff0c;C为根结点&＃xff0c;由中序遍历可知&＃xff0c;C左边的是左子树含DEBA&＃xff0c;C右边无结点&＃xff0c;知根结点无右子树。先序遍历先访问根C&＃xff0c;答案中只有A以C开头&＃xff0c;为正确答案。

例4&＃xff1a;  如下二叉树中序遍历的结果是&＃xff08;　　&＃xff09;。

A). ACBDFEG  B). ACBDFGE  C).ABDCGEF  D).FCADBEG

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

例5&＃xff1a;如下二叉树后序遍历的结果是&＃xff08;　　&＃xff09;。

A)  ABCDEF  B) DBEAFC  C)ABDECF  D)DEBFCA

解析&＃xff1a;后序的最后一个必须是二叉树的根&＃xff0c;快速判断答案为D。