1. 遍历顺序

遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

p.s. 前序遍历又叫先序遍历.

前中后序遍历顺序如下:

前序遍历:根节点->左子树->右子树 (根左右)

中序遍历:左子树->根节点->右子树 (左根右)

后序遍历:左子树->右子树->根节点 (左右根)

1.1. 前序遍历

前序遍历: 先遍历根结点,然后遍历左子树,最后遍历右子树。

1.2. 中序遍历

中序遍历: 先遍历左子树,然后遍历根结点,最后遍历右子树。

1.3. 后序遍历

后序遍历: 先遍历左子树,然后遍历右子树,最后遍历根节点。

1.4. 层次遍历

层次遍历: 即按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)。

2. 画二叉树

前序(前根序列): 根左右
中序(中根序列): 左根右
后序(后根序列): 左右根

只要知道中序遍历顺序, 再加上前序或后序任一个遍历顺序即可确定唯一的二叉树。

画二叉树口诀:

前后序定根, 中序定左右;
前序前找根, 后序后找根。

例如已知:

中根序列: C, B, D, E, A, G, I, H, J, F
后根序列: C, E, D, B, I, J, H, G, F, A
画出二叉树并写出前根序列。

解答思路:

1. 根据前序或后序先确定根;
2. 再根据中序确定左右子树。

按递归思想, 根据口诀逐一分步成思路中的1, 2步, 即可快速画出如下二叉树:

二叉树

由得出的二叉树可知前根序列为:A, B, C, D, E, F, G, H, I, J