在前文中我们已经了解了二叉樹的原理及二叉树的三种遍历方式,假设父节点是N左节点是L,右节点是R:
对于下面的二叉树遍历结果分别为
其实,只要知道其中任意兩种遍历的顺序我们就可以推断出剩下的一种遍历方式的顺序,这里我们只是以:知道前序遍历和中序遍历推断后序遍历作为例子,其他组合方式原理是一样的要完成这个任务,我们首先要利用以下几个特性:
- 特性A对于前序遍历,第一个肯定是根节点;
- 特性B对于後序遍历,最后一个肯定是根节点;
- 特性C利用前序或后序遍历,确定根节点在中序遍历中,根节点的两边就可以分出左子树和右子树;
- 特性D对左子树和右子树分别做前面3点的分析和拆分,相当于做递归我们就可以重建出完整的二叉树;
我们以一个例子做一下这个过程,假设:
- 我们根据特性A可以得知根节点是C,然后根据特性C,我们知道左子树是:GHBA右子树是:DEF。
- 取出左子树左子树的前序遍历是:ABGH,中序遍历是:GHBA根据特性A和C,得出左子树的父节点是A并且A没有右子树。
- 使用同样的方法前序是BGH,中序是GHB得出父节点是B,G和H分别昰左右节点
- 回到右子树,它的前序是EDF中序是DEF,依然根据特性A和C得出父节点是E,左右节点是D和F
到此,我们得到了这棵完整的二叉树因此,它的后序遍历就是:GHBADFEC
下面我们使用程序来实现根据前序遍历和中序遍历得到后续遍历。
首先我们需要建立节点的实体类