赞
踩
下面以自己画的一个二叉树为例,来说明一下各种遍历方法。
访问根节点;先序遍历左子树;先序遍历右子树(ABDGHECFI)
中序遍历左子树;访问根节点;中序遍历右子树(GDHBEACIF)
后序遍历左子树;后序遍历右子树;访问根节点(GHDEBIFCA)
(本来想着给大家再写一下这些遍历的代码实现。最近一直没有在学习,所以给大家推荐一篇大神的文章,里面递归实现和堆栈实现都有些,写的也挺详细的。大家自行参考哦!二叉树遍历方式代码实现)
首先必须要知道中序遍历,这样才能通过先序或者后序遍历来判断根的左右子树,从而逐个的判断出每个数所在的位置。
**举个栗子(搞错了,For example):**已知一个二叉树的先序遍历序列(ABDGHECFI)和中序遍历序列(GDHBEACIF),求该二叉树的后序遍历?
解答:
- 首先通过先序遍历序列确定序列(GDHBEACIF)根节点为A;其次通过中序遍历序列得出A节点左边(左子树以及其下的子树)为GDHBE,右边为CIF。
- 再首先通过先序遍历序列确定序列(GDHBE)根节点为B,确定序列(CIF)根节点为C;再其次通过中序遍历序列得出B节点左边为GDH,右边为E(即为B的右子树)、得出C节点左边为没有,右边为E(即为B的右子树)。
- 再再首先通过先序遍历序列确定 序列(GDH)根节点为D;再再其次通过中序遍历序列得出D节点的左边为G(即为左子树),右边为H(即为右子树)。
最后就得出了这个二叉树的真实排布方式,从而可以简单的写出它的后续遍历序列。是不是被我的文字所折服——“首先~ 其次~ 。 再首先~ 再其次~ ”。其实后面的“再首先~ 再其次~”都和前面的“首先 其次”中讲的方法都是一样的。便于大家观察理解,我画一个草图吧。最终可以轻松计算其后续遍历序列为:GHDEBIFCA
(条件有限,大家就这样看吧,应该能看清楚。摸摸哒)
("自己做的每一次决定,都请你不要后悔。生活本就是未知的,为何不放手一搏呢?
FIGHTING…")
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。