1、先序遍历（先访问根节点）

先访问根节点

再先序遍历左子树

再先序遍历右子树

例：下图：先访问根节点A，再先序访问A的左子树B。A的左子树B是一个树 ，所以先访问树B的根节点B，再访问B的左子树D。B的左子树D是一个树，所以先访问D的根节点D，再访问D的左子树，D没有左子树，再访问D的右子树，D没有右子树，那么D访问完毕。再访问D的父亲B的右子树。B没有右子树，那么B访问完毕。这样A的左子树访问完毕，序号为ABD。再访问A的右子树C。先访问C的根节点C，再访问C的左子树E，由于E没有左子树和右子树，所以E访问完毕。再访问C的右子树F。F也是树，所以先访问F的根节点F，再访问F的左子树G。G也是一个数，所以先访问G的根节点G，而G没有左右子树，G访问完毕。再访问G的父亲F的右子树。F没有右子树，所以F访问完毕。因为F是C的右子树，所以F访问完毕则C访问完毕。C访问完毕则整个树访问完毕！

先序b遍历

2、中序遍历（中间访问根节点）

中序遍历左子树

再访问根节点

再中序遍历右节点

例：如下图：

第一步中序遍历A的左子树B，由于左子树B也是树，所以要先访问B的左子树D。由于左子树D也是树，所以要先访问D的左子树，D的左子树为空，所以第1个访问的是左子树的根节点D，再访问D的右子树，D的右子树为空。所以D访问完毕。D访问完毕则B的左子树访问完毕。第2个访问树B的根节点B。再访问B的右子树。因为B的右子树为空，所以B访问完毕。B访问完毕则A的左子树访问完毕，所以第3个访问的是A。再访问A的右子树C。因为C也是树，所以先访问C的左子树E。因为E也是树，所以先访问E的左子树，E的左子树为空，所以第4个访问的是E。再访问E的右子树，E的右子树为空，所以C的左子树访问完毕，接着访问C，所以第5个访问的是节点C。接着访问C的右子树F。因为F是树，所以先访问F的左子树G。因为G也是树，所以先访问G的左子树。G的左子树为空，所以第6个访问的是节点G。再访问G的右子树。G的右子树为空，所以节点G访问完毕。G访问完毕则F的左子树访问完毕，所以第7个访问的是节点F。F的右子树为空，所以F访问完毕，则C的右子树访问完毕，所以A的右子树访问完毕，整个树访问完毕！

中序遍历

3、后序遍历（最后访问根节点）

后序遍历左子树

后续遍历右子树

再访问根节点

后续遍历

已知两种遍历序列求二叉树：只有已知一个树的先序和中序或者是后序和中序，才可以还原出二叉树的样子。知道先序和后序是不可以还原出二叉树。

例1、已知先序和中序还原出二叉树：

例1：已知先序：ABCDEFGH

中序：BDCEAFHG

求后序

解：先序中第一个出现的一定是根节点，所以在先序中第一个出现的A是根节点。中序中找出该根节点左边为左子树，右边为右子树。由于中序是先访问左子树再访问根节点再访问右子树。所以在中序中A的左边是A的左子树，所以BDCE是A的左子树；

从先序中找到BDCE的顺序是BCDE所以B是A左子树的根节点；

在中序中B的左边一定是B的左子树。由于B左边没有，所以B没有左子树，DCE是B的右子树；

在先序中DCE三个个节点C是第一个出现的，所以C是B右子树的根节点；

再从中序中D和E分别在C的左右，所以D是C的左子树，E是C的右子树，这样A的左子树确定那个。

再同样确定A的右子树 在中序中A的右边FHG在先序中F第一个出现，所以F是A的右子树的根节点；

再从中序中F左边没有，所以F没有左子树；HG是F的右子树；

再从先序中确定HG第一个出现的是G，所以G是F的右子树的根；

再从中序中G左边是H，右边没有，所以H是G的左子是，G没有右子树。

这样还原出树和后序如下图：

例2、已知后序和中序求先序:

已知中序：BDCEAFHG

后序：DECBHGFA

求先序。

解：后序中最后一个一定是根节点，再在中序中找出做右子树。

从后序中求出根节点：A；

从中序中求出A的左子树：BDCE，右子树：FHG；

后序中求出A的左子树BDCE的根结点：B；

中序中求出B的左子树：空，右子树：DCE；

后序中求出树DCE的根节点：C；

中序中求出C的左子树：D，右子树：E；

后序中求出树A的右子树FHG根节点：F；

中序中求出F的左子树：空，右子树：HG；

先序中求出树HG的根节点：G；

中序中求出节点G的左子树：H，右子树：空。

这样还原出二叉树和其先序如下图：

~~~end~~~