java程序员编程面试必备知识学习，二叉树就是这么简单
Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。
给你学习路线：html-css-js-jq-javase-数据库-jsp-servlet-Struts2-hibernate-mybatis-spring4-springmvc-ssh-ssm
文章图片
本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树，仅入门观看(或复习)....
首先，我们来讲讲什么是树：
树是一种非线性的数据结构，相对于线性的数据结构(链表、数组)而言，树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)
在现实生活中，我们一般的树长这个样子的：
文章图片
小编推荐一个学Java的学习裙【 六五零，五五四，六零七 】，无论你是大牛还是小白，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！
但是在编程的世界中，我们一般把树“倒”过来看，这样容易我们分析：
文章图片
一般的树是有很多很多个分支的，分支下又有很多很多个分支，如果在程序中研究这个会非常麻烦。因为本来树就是非线性的，而我们计算机的内存是线性存储的，太过复杂的话我们无法设计出来的。
因此，我们先来研究简单又经常用的---> 二叉树
1.1树的一些概念
我就拿上面的图来进行画来讲解了：
文章图片
二叉树的意思就是说：每个节点不能多于有两个儿子，上面的图就是一颗二叉树。
一棵树至少会有一个节点(根节点)
树由节点组成，每个节点的数据结构是这样的：
因此，我们定义树的时候往往是->定义节点->节点连接起来就成了树，而节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)
文章图片
1.2静态创建二叉树
上面说了，树是由若干个节点组成，节点连接起来就成了树，而节点由一个数据、两个指针组成
因此，创建树实际上就是创建节点，然后连接节点
首先，使用Java类定义节点：
文章图片
下面我们就拿这个二叉树为例来构建吧：
文章图片
为了方便构建，我就给了它一个带参数的构造方法和set、get方法了：
文章图片
那么我们现在就创建了5个节点：
文章图片
它们目前的状态是这样子的：
文章图片
于是下面我们去把它连起来：
文章图片
连接完之后，那么我们的树就创建完成了。
文章图片
1.3遍历二叉树
上面说我们的树创建完成了，那怎么证明呢？？我们如果可以像数组一样遍历它(看它的数据)，那就说明它创建完成了～
值得说明的是：二叉树遍历有三种方式
先序遍历
先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
中序遍历
先访问左节点，然后访问根节点，最后访问右节点(左->根->右)
后序遍历
先访问左节点，然后访问右节点，最后访问根节点(左->右->根)
以上面的二叉树为例：
如果是先序遍历：10->9->20->15->35
如果是中序遍历：9->10->15->20->35
可能需要解释地方：访问完10节点过后，去找的是20节点，但20下还有子节点，因此先访问的是20的左儿子15节点。由于15节点没有儿子了。所以就返回20节点，访问20节点。最后访问35节点
如果是后序遍历：9->15->35->20->10
可能需要解释地方：先访问9节点，随后应该访问的是20节点，但20下还有子节点，因此先访问的是20的左儿子15节点。由于15节点没有儿子了。所以就去访问35节点，由于35节点也没有儿子了，所以返回20节点，最终返回10节点
一句话总结：先序(根->左->右)，中序(左->根->右)，后序(左->右->根)。如果访问有孩子的节点，先处理孩子的，随后返回
无论先中后遍历，每个节点的遍历如果访问有孩子的节点，先处理孩子的(逻辑是一样的)
因此我们很容易想到递归
递归的出口就是：当没有子节点了，就返回
因此，我们可以写出这样的先序遍历代码：
文章图片
结果跟我们刚才说的是一样的：
文章图片
我们再用中序遍历调用一遍吧：
文章图片
结果跟我们刚才说的是一样的：
文章图片
有意思的是：通过先序和中序或者中序和后序我们可以还原出原始的二叉树，但是通过先序和后续是无法还原出原始的二叉树的
也就是说：通过中序和先序或者中序和后序我们就可以确定一颗二叉树了！
二、动态创建二叉树
上面我们是手动创建二叉树的，一般地：都是给出一个数组给你，让你将数组变成一个二叉树，此时就需要我们动态创建二叉树了。
二叉树中还有一种特殊的二叉树：二叉查找树(binary search tree)
定义：当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。
明眼人可以看出，这对我们来找一个数是非常方便快捷的
往往我们动态创建二叉树都是创建二叉查找树
文章图片
小编推荐一个学Java的学习裙【 六五零，五五四，六零七 】，无论你是大牛还是小白，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！
2.1动态创建二叉树体验
假设我们有一个数组：
int[] arrays = {3, 2, 1, 4, 5};
那么创建二叉树的步骤是这样的：
首先将3作为根节点
文章图片
随后2进来了，我们跟3做比较，比3小，那么放在3的左边
文章图片
随后1进来了，我们跟3做比较，比3小，那么放在3的左边，此时3的左边有2了，因此跟2比，比2小，放在2的左边
文章图片
随后4进来了，我们跟3做比较，比3大，那么放在3的右边
文章图片
随后5进来了，我们跟3做比较，比3大，那么放在3的右边，此时3的右边有4了，因此跟4比，比4大，放在4的右边
文章图片
那么我们的二叉查找树就建立成功了，无论任何一颗子树，左边都比根要小，右边比根要大
文章图片
2.2代码实现
我们的代码实现也很简单，如果比当前根节点要小，那么放到当前根节点左边，如果比当前根节点要大，那么放到当前根节点右边。
因为是动态创建的，因此我们得用一个类来表示根节点
文章图片
比较与根谁大，大的往右边，小的往左边：
文章图片
测试代码：
文章图片
文章图片
【java程序员编程面试必备知识学习，二叉树就是这么简单】三、查询二叉查找树相关
3.1查询树的深度
查询树的深度我们可以这样想：左边的子树和右边的字数比，谁大就返回谁，那么再接上根节点+1就可以了
文章图片
文章图片
3.1查询树的最大值
从上面先序遍历二叉查找树的时候，细心的同学可能会发现：中序遍历二叉查找树得到的结果是排好顺序的～
那么，如果我们的二叉树不是二叉查找树，我们要怎么查询他的最大值呢？
可以这样：
文章图片
小编推荐一个学Java的学习裙【 六五零，五五四，六零七 】，无论你是大牛还是小白，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！
左边找最大值->递归
右边找最大值->递归
文章图片
四、最后
无论是在遍历树、查找深度、查找最大值都用到了递归，递归在非线性的数据结构中是用得非常多的...
树的应用也非常广泛，此篇简单地说明了树的数据结构，高级的东西我也没弄懂，可能以后用到的时候会继续深入...
文章图片
文章图片
文章图片
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- python青少年编程比赛_第十一届蓝桥杯大赛青少年创意编程组比赛细则
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用（一）
- java之static、static|java之static、static final、final的区别与应用