已知二叉树的先序遍历和中序遍历画出该二叉树.pdf

已已知知⼆⼆叉叉树树的的先先序序遍遍历历和和中中序序遍遍历历画画出出该该⼆⼆叉叉树树

对⼀棵⼆叉树进⾏遍历，我们可以采取3中顺序进⾏遍历，分别是序遍历、中序遍历和后序遍历。

这三种⽅式是以访问⽗节点的顺序来进⾏命名的。

假设⽗节点是N，左节点是L，右节点是R，那么对应的访问遍历顺序如下：

序遍历N－L－R

中序遍历L－N－R

后序遍历L－R－N

所以，对于以下这棵树，三种遍历⽅式的结果是

序遍历ABCDEF

中序遍历CBDAEF

后序遍历CDBFEA

已已知知⼆⼆叉叉树树的的序序遍遍历历和和中中序序遍遍历历，，如如何何得得到到它它的的后后序序遍遍历历

其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的⼀种遍历⽅式的顺序，这⾥我们只是以：

知道序遍历和中序遍历，推断后序遍历作为例⼦，其他组合⽅式原理是⼀样的。要完成这个任务，我们⾸先要利⽤以下⼏

个特性：

特性A，对于序遍历，第⼀个肯定是根节点；

特性B，对于后序遍历，最后⼀个肯定是根节点；

特性C，利⽤序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左⼦树和右⼦树；

特性D，对左⼦树和右⼦树分别做⾯3点的分析和拆分，相当于做递归，我们就可以重建出完整的⼆叉树；

我们以⼀个例⼦做⼀下这个过程，假设：

序遍历的顺序是:CABGHEDF

中序遍历的顺序是:GHBACDEF

第⼀步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左⼦树是：GHBA，右⼦树是：DEF。

C

/\

GHBADEF

第⼆步，取出左⼦树，左⼦树的序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左⼦树的⽗节点是A，并且A没有右⼦

树。

C

/\

ADEF

/

GBH

第三步，使⽤同样的⽅法，序是BGH，中序是GHB，得出⽗节点是B，GH是左⼦树,没有右⼦树。

C

/\

ADEF

/

B

/

GH

第四步,序是GH,中序是GH,所以G是⽗节点,H是右⼦树,没有左⼦树.

C

/\

ADEF

/

B

/

G

\

H

第四步，回到右⼦树，它的序是EDF，中序是DEF，依然根据特性A和C，得出⽗节点是E，左右节点是D和F。

C

/\

AE

//\

BDF

/

G

\

H

到此，我们得到了这棵完整的⼆叉树，因此，它的后序遍历就是:HGBADFEC