知道二叉树的前序和后序,问中序排列怎么排?有什么方法吗?希望有图

如题所述

中序遍历的规则就是把根放在中间,从左到右。即左——根——右。

以下图为例:

则是先遍历左子树(即以B为根的子树),再遍历根结点,最后遍历右子树(以E为根结点的子树)。

首先在遍历左子树(以B为根的子树)的时候,同样用中序遍历的规则(左——根——右),此时,我们把左子树当成一个独立的树来看。那么在这个左子树里面,遍历的顺序就应该是CBD。(暂且把结果放一边)

然后遍历根结点,就是输出A(根结点就是A嘛!)

最后遍历右子树(以E为根的子树),按照前面第一步的方法,暂且把这个右子树当成一个独立的树来看,遍历结果应该是EF(因为在这个子树里,它的左子树为空)。

最后一步,我们把上面三步的结果顺序串联起来,就可以得到遍历的结果:CBDAEF

PS:不管哪一种遍历,只要把各个子树当成一个“大结点”来看。在各个“大结点”内部又各自依相应的遍历方式遍历,最终将结果返回即可得到所要的遍历结果(呃!不知道会不会说复杂了!总之就是一个递归的过程!你要好好体会一下!) 

PSS:还有另一种简单的方法,需要另一张图……楼主可以M我。

温馨提示:答案为网友推荐,仅供参考