由遍历序列构造二叉树--王道
【摘要】 目录前序遍历 + 中序遍历序列后序+中序遍历序列层序遍历+中序遍历序列若只给出一棵二叉树的前/中/后/层 序遍历序列的一种，不能唯一确定一棵二叉树 编辑前序遍历 + 中序遍历序列 前序遍历：根结点、前序遍历左子树，前序遍历右子树 中序遍历：中序遍历左子树，根结点，中序遍历右子树 例子：编辑（图有问题，绿色的点应该是c） 我们分析前序遍历第一个出现的结点一定为根结点，所以A为根结点，而...
目录
若只给出一棵二叉树的前/中/后/层 序遍历序列的一种，不能唯一确定一棵二叉树
前序遍历 + 中序遍历序列
前序遍历：根结点、前序遍历左子树，前序遍历右子树
中序遍历：中序遍历左子树，根结点，中序遍历右子树
例子：
（图有问题，绿色的点应该是c）
我们分析前序遍历第一个出现的结点一定为根结点，所以A为根结点，而中序遍历左边一定为左子树遍历的序列即BDC，右边右子树为E。
而同样的道理看BDC的话，由前序排列知D为根结点，由中序遍历知左子树为B，右子树为E。
后序+中序遍历序列
后序遍历： 前序遍历左子树 、 前序遍历右子树、根节点
中序遍历：中序遍历左子树，根结点，中序遍历右子树
例子
我们看这个题目后序遍历最右边为根结点，由中序遍历 可分为 左：EAF 右：HCBGI
看左边的序列 EAF ，而在后序遍历那为EFA，可知A为“根结点”，左：E 右：F
看右边的序列HCBGI，前序遍历那为HCIGB，可知B为“根结点”，左：HC 右：GI
最后可知 H在左，C在右，G在左 ，I 在右
层序遍历+中序遍历序列
开始时知道D在层序序列为第一个遍历所以，D为根结点，左子树：EAF，右子树：HCBGI
之后由中序遍历层序遍历知A为左子树的根结点，B为右子树的根结点，然后不难知A的左孩子为 E，右孩子为F。
由层序遍历知，EF后面为CG所以它俩在中间，C 和 G 分别在中间，在看中序遍历序列
C的左边挂H，G的右边挂I
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）