中序遍历的规则就是把根放在中间,从左到右。即左——根——右。
以下图为例:
则是先遍历左子树(即以B为根的子树),再遍历根结点,最后遍历右子树(以E为根结点的子树)。
首先在遍历左子树(以B为根的子树)的时候,同样用中序遍历的规则(左——根——右),此时,我们把左子树当成一个独立的树来看。那么在这个左子树里面,遍历的顺序就应该是CBD。(暂且把结果放一边)
然后遍历根结点,就是输出A(根结点就是A嘛!)
最后遍历右子树(以E为根的子树),按照前面第一步的方法,暂且把这个右子树当成一个独立的树来看,遍历结果应该是EF(因为在这个子树里,它的左子树为空)。
最后一步,我们把上面三步的结果顺序串联起来,就可以得到遍历的结果:CBDAEF
PS:不管哪一种遍历,只要把各个子树当成一个“大结点”来看。在各个“大结点”内部又各自依相应的遍历方式遍历,最终将结果返回即可得到所要的遍历结果(呃!不知道会不会说复杂了!总之就是一个递归的过程!你要好好体会一下!)
PSS:还有另一种简单的方法,需要另一张图……楼主可以M我。