没有合适的资源?快使用搜索试试~ 我知道了~
二叉树遍历问题 二叉树遍历求解问题
资源推荐
资源详情
资源评论
邮箱:CALF-LOVE@qq.com。有什么问题,可以大家一起讨论!
二叉树的遍历
首先得明白二叉树的遍历方式:
参照百科里的定义:
1.中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
2.先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
3.后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。
简言之:前序:根左右 中序:左根右 后序:左右根
举三个例子:
例一:已知前序和中序,求后序?
前序:abdgcefh 中序:dgbaechf 后序:?
前序:根左右 中序:左根右 后序:左右根
求解:
根据各种遍历的方式,我们知道,中序中间的那一个一定会是根结点,前
序中第一个是根结点 a 这样,通过比较,我们就把树以根结点分成两部分(dgb
和 echf)。再通过这种方式,我们就把剩下来的树找出来了。
由 bdg(前)和 dgb(中)知 b 为此子树的根结点,由 dg 不变,再由先左后右,
知 d 再为根结点,g 为 d 的右子树。由 cefh(前)和 echf(中)知 e 为此子树的根结点,
c 为 e 的左子树,fh 为 e 的右子树。因为 fh(前)和 hf(中)不同,再由先左后右,
知 f 为根,h 为此子树的左结点。
所有后序结果为:gdbehfca
a a
bdg echf b c
d e f
g h
资源评论
计码源泉
- 粉丝: 2
- 资源: 74
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功