详解java中二叉树的深度优先遍历

大敏大大_8782

大敏大大_8782

2020-06-28

3944人浏览

转载

这两天在做二叉树相关的算法题,做一点学习笔记。(连二叉树都不会?确实不熟练,平时工作也没有要去写二叉树相关的算法或者数据结构的场景。因为自己菜,所以更加要努力学!)

定义

先看下维基百科的解释:在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

由于二叉树本身定义的特点,具有高度的局部重复性,所以在深度优先遍历二叉树时,通常采用递归的方式去实现,这样实现出来的代码非常简洁漂亮,也比较容易看懂。

深度优先遍历

一般我们深度优先遍历二叉树有三种最常见的顺序遍历:前序、中序、后序。

前序的遍历顺序为:访问根结点 -> 遍历左子树 -> 遍历右子树

中序的遍历顺序为:遍历左子树 -> 访问根结点 -> 遍历右子树

后序的遍历顺序为:遍历左子树 -> 遍历右子树 -> 访问根结点

注意这里的左右是整个子树,而不是一个结点,因为我们需要遍历整棵树,所以每次遍历都是按照这个顺序去执行,直到叶子结点。

举个例子,假如有如下二叉树:

0.jpg

前序遍历得到的序列就是 A - B - C - D - E

中序遍历得到的序列就是 B - A - D - C - E

后序遍历得到的序列就是 B - D - E - C - A

思路我们就用前序遍历来讲(非常不建议去人肉递归,至少我的脑子吃不消三层。。。):

第一层递归:

先访问根结点,所以输出根结点 A,然后遍历左子树(L1),再遍历右子树(R1);

第二层递归:

对于 L1,先访问根结点,所以输出此时的根结点 B,然后发现 B 的左右子树为空,结束递归;

对于 R1,先访问根结点,所以输出此时的根结点 C,然后遍历左子树(L2),再遍历右子树(R2);

第三层递归:

对于 L2,先访问根结点,所以输出此时的根结点 D,然后发现 D 的左右子树为空,结束递归;

对于 R2,先访问根结点,所以输出此时的根结点 E,然后发现 E 的左右子树为空,结束递归;

前中后序特征

根据前中后序的定义,其实我们不难发现有如下特征:

• 前序的第一个一定是 root 节点,后序的最后一个一定是 root 节点

• 每种排序的左子树和右子树分布都是有规律的

• 对于每一个子树都遵循上面两个规律的树

2.jpg

这些特征也就是定义中对顺序的表现。

Java开发手册免费版
Java开发手册免费版

Java 开发规约速查手册,覆盖命名、异常、并发、数据库等 7 大维度核心规范。

下载

各种推导

这边列举一下对于二叉树的遍历最基本的几个算法题:

• 给定二叉树得出其前/中/后序遍历的序列;

• 根据前序和中序推导后序(或者推导整颗二叉树);

• 根据后序和中序推导前序(或者推导整颗二叉树);

对于二叉树的遍历,前面也讲过,通常采用递归来做,对于递归,有模版可以直接套用:

public void recur(int level, int param) {
    
    // terminator
    if (level > MAX_LEVEL) {
        // process result
         return;   
    }
    
    // process current logic
    process(level, param);
    
    // drill down
    recur(level+1, newParam);
    
    // restore current status
}

这个是我这两天看极客时间的算法训练营中超哥(覃超)讲到的比较实用的小技巧(这个模版对于新手特别好),遵循上面的三步骤(如果有局部变量需要释放或者额外处理则第四步去做)能比较有条理的写出递归代码。

这里拿根据前序和中序推导后序来举例:

先初始化两个序列:

int[] preSequence = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] inSequence = {2, 3, 1, 6, 7, 8, 5, 9, 4};

通过上面说到的几个特征,我们已经可以找到最小重复子问题了,每次递归

根据前序的第一个结点值去匹配中序中该结点值所在的索引 i,这样我们就能得到索引 i 的前后两部份分别对应左右子树,接着分别去遍历这两个左右子树,然后输出当前前序的第一个结点值,也就是根结点。

根据自顶向下的程序设计方法,我们可以先写出如下初始递归调用:

List<integer> result = new ArrayList();
preAndInToPost(0, 0, preSequence.length, preSequence, inSequence, result);</integer>

第一个参数表示前序序列的第一个元素索引;

第二个参数表示中序序列的第一个元素索引;

第三个参数表示序列长度;

第四个参数表示前序序列;

第五个参数表示后序序列;

第六个参数用于保存结果;

先来考虑终止条件是什么,也就是什么时候结束递归,当我们的根结点为空的时候终止,对应这里就是序列长度为零的时候。

if (length == 0) {
    return;
}

接着考虑处理逻辑,也就是找到索引 i:

int i = 0;
while (inSequence[inIndex + i] != preSequence[preIndex]) {
    i++;
}

然后开始向下递归:

preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
result.add(preSequence[preIndex]);

因为推导的是后序序列,所以顺序如上,添加根结点的操作是在最后的。前三个参数如何得出来的呢,我们走一下第一次遍历就可以得出来。

前序序列的第一个结点 1 在中序序列中的索引为 2,此时

左子树的中序系列起始索引为总序列的第 1 个索引,长度为 2;

左子树的前序序列起始索引为总序列的第 2 个索引,长度为 2;

右子树的中序系列起始索引为总序列的第 3 个索引,长度为 length - 3;

右子树的前序序列起始索引为总序列的第 3 个索引,长度为 length - 3;

完整代码如下:

/**
 * 根据前序和中序推导后序
 *
 * @param preIndex    前序索引
 * @param inIndex     中序索引
 * @param length      序列长度
 * @param preSequence 前序序列
 * @param inSequence  中序序列
 * @param result      结果序列
 */
private void preAndInToPost(int preIndex, int inIndex, int length, int[] preSequence, int[] inSequence, List<integer> result) {
    if (length == 0) {
        return;
    }

    int i = 0;
    while (inSequence[inIndex + i] != preSequence[preIndex]) {
        i++;
    }

    preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
    preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
    result.add(preSequence[preIndex]);
}</integer>
参考链接• 维基百科 - 二叉树(https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91)

推荐教程:《java教程》

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

java

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

60

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

60

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

60

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

40

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

160

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习