通过先序遍历和中序遍历后的序列还原二叉树(实现方法)_前序中序还原二叉树 - CSDN文库

135 浏览量更新于2023-03-03 2 收藏 222KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

通过先序遍历和中序遍历后的序列还原二叉树通过先序遍历和中序遍历后的序列还原二叉树(实现方法实现方法)

下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的，现在

就分享给大家，也给大家做个参考。一起跟随小编过来看看吧

当我们有一个当我们有一个

先序遍历序列：先序遍历序列：1,3,7,9,5,11

中序遍历序列：中序遍历序列：9,7,3,1,5,11

我们可以很轻松的用笔写出对应的二叉树。但是用代码又该如何实现？

下面我们来简单谈谈基本思想。

首先，先序遍历的顺序是根据根根-左孩子左孩子-右孩子右孩子的顺序遍历的，那么我们可以率先确认的是先序遍历序列的第一个数就是根

节点，然后中序遍历是根据左孩子左孩子-根根-右孩子右孩子的顺序遍历的。我们通过先序遍历确认了根节点，那么我们只需要在中序遍历

中找到根节点的位置，然后就可以很好地区分出，那些属于左子树的节点，那些是属于右子树的节点了。如下图：

我们确定数字1为根节点，然后根据中序遍历的遍历顺序确定，中序遍历序列中数字1的左边全部为左子树节点，右边全部为

右子树。通过左子树节点的个数，得出先序遍历序列中从根节点往后的连续3个数是属于左子树的，剩下的为右子树。这样再

在左右子树的序列中重复以上步骤，最终找到没有子节点为止。

实现代码如下：

package com.tree.traverse;

import java.util.ArrayList;

import java.util.List;

/**

* @author Caijh

*

* 2017年6月2日下午7:21:10

*/

public class BuildTreePreOrderInOrder {

/**

* 1

* / \

* 3 5

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_38717579

粉丝: 2
资源: 887

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈