二叉树是由根、左子树、右子树三部分组成。
二叉树的遍历方式又可以分为前序遍历,中序遍历,后序遍历。
前序遍历:根,左子树,右子树
中序遍历:左子树,根,右子树
后序遍历:左子树,右子树,根
比如定义一棵树:
它的前序遍历结果为:1 2 3 4 5 6
中序遍历结果为:3 2 1 5 4 6
后序遍历结果为:3 2 5 6 4 1
现在如果我们没有二叉树的图,只知道它的两种遍历的结果,如何求第三种遍历的结果呢?问题化简一下,我们只需知道完整的数的样子就能直接写出第三种遍历结果,所以我们需要用两种遍历的结果推出树的样子就好了。(两种遍历中必须包含中序遍历,只有前序遍历和后序遍历不能确定一棵树。)
首先观察三种遍历的特点,主要思路就是找根节点的位置。
比如给出一颗二叉树的中序遍历序列为JGDHKBAELIMCF,后序遍历序列为JGKHDBLMIEFCA。
由后续遍历最后一个是根结点,我们可以找到根是A。
再由中序遍历:根的左边是左子树,右边是右子树。所以A的左子树为JGDHKB,A的右子树为ELIMCF。
比较中序遍历的左右子树确定后序遍历中的左右子树
中:JGDHKB A ELIMCF
后:JGKHDB LMIEFC A
再次根据后续遍历找根,可以看出是B和C
然后在中序遍历的左右子树中再次找出根,左子树,右子树。一直重复直到最后只剩一个结点。下面以左子树为例。
2中:JGDHK B 此时没有右子树
2后:JGKHD B
根为D
3中:JG D HK
3后:JG KH D
根为G
4中:J G
4后:J G
所以可以得到树
所以它的前序遍历为:ABDGJHKCEILMF
前序+中序推后序与此类似。