二叉树中的先序,中序,后续遍历很容易让人迷糊,记录一下概念。
遍历是将二叉树中的结点信息由非线性排列变为某种意义上的线性排列。也就是说,遍历操作使非线性结构线性化。
一棵二叉树由根结点、左子树和右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树的遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式:DLR(先序 遍历)、LDR(中序遍历)和 LRD(后序遍历)。
我们对如下树进行先序遍历(DLR)、中序遍历(LDR)和 后序遍历(LRD),大家试着写出各种遍历后的字母排列后再看答案。
1、先序遍历(DLR)
先序遍历的基本思想是:首先访问根结点,然后先序遍历其左子树,最后先序遍历其右子树。
A B D H I E J C F G
2、DRL
DRL的基本思想是:首先访问根结点,然后先序遍历其右子树,最后先序遍历其左子树。
A C G F B E J D I H
3、中序遍历(LDR) 中序遍历的基本思想是:首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历其右子树。
H D I B J E A F C G
4、RDL
RDL的基本思想是:首先中序遍历根结点的右子树,然后访问根结点,最后中序遍历其左子树。
G C F A E J B I D H
5、后序遍历(LRD) 后序遍历的基本思想是:首先后序遍历根结点的左子树,然后后序遍历根结点的右子树,最后访问根结点
H I D J E B F G C A
6、RLD
RLD的基本思想是:首先后序遍历根结点的右子树,然后后序遍历根结点的左子树,最后访问根结点
G F C J E I H D B A