Java初阶数据结构二叉树实现+练习完整（工程文件后序会进行上传）

i1.二叉树的概念

1.二叉树的定义

（1）二叉树可以是一个节点的有限集合

（2）可以为空

（3）或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成的

（4）二叉树的每一个节点都是小于等于2的。

（5）二叉树的子树是有左右之分的，分别为左树和右树

2.二叉树的组成

（1）首先数据结构分为线性结构和树状结构，其中二叉树就是一个树状结构的数据结构，他是由多个节点组成的

（2）一个二叉树是由一个根结点以及多个子树来组成的。

（3）二叉树的代码实现原理图（代码逻辑）

都指向他的堂兄弟节点，如果没有堂兄弟节点那么就遍历他的该节点的左子树然后再看这个左子树有没有堂兄弟节点

2.二叉树节点名称

结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6 树的度：一棵树中，所有结点度的最大值称为树的度；

度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

根结点：一棵树中，没有双亲结点的结点；如上图：A 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4 树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等节点为分支结点

兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点 结点的祖先：从根到该结点所经分支上的所有结点；

如上图：A是所有结点的祖先 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>=0）棵互不相交的树组成的集合称为森林 

3.二叉树的两个特殊种类

3.1满二叉树（特殊的完全二叉树）

2^(k-1)是他这一层的节点数

k是层数

2^k-1 总节点数就是

3.2完全二叉树

定义：从上到下，从左到右依次存放就是完全二叉树，我搞编号(编号七没了自己想象)了方便大家更好理解

满二叉树是一个特殊的完全二叉树

4.二叉树的性质

4.1二叉树性质的解析

 度指的就是这个节点的两边有几个。

扩容知识

（1）一颗N个节点的树中有N-1个边

  (2)具有n个结点的完全二叉树的深度k为log2（n+1）取整

（3）节点编号减一除二得到父亲节点编号（n是总节点数）

左孩子2i+1

有孩子2i+2

等于n就代表这个孩子节点没有

4.2二叉树性质的习题解析

1.题目一

2.题目二 

3. 题目三

在完全二叉树中度为2的节点和度为1的节点永远是2比1多1个节点，

节点数偶数有度为1的节点为1个，所以只剩下度为0和2的+1.

节点数为奇数没有度为1的节点

 5二叉树如果进行存储

5.1.二叉树的链式存储

5.1.1二叉树链式存储的方式介绍

（1）链表存储是用一个节点一个节点来引用起来的，常见的有二叉和三叉表示方式

（2）双孩子双亲表示法就是红黑树那些，我们会在高级数据结构中进行讲解 

我们的初级数据结构中使用的就是孩子表示法

5.2 二叉树链表式存储实现（孩子表示法）

代码实现

定义三个类

测试类

节点类

二叉树类

（1）这三个类会整体实现这个二叉树

（2）定义一个一般的二叉树的节点类型

（3）接下来我会用穷举的方法来实现二叉树，因为不这样搞你们看不懂

图解 

 我会定义这些节点然后用手动的方式拼接起来。

拼接完毕以后 ，我们要考虑的就是输出这个树，所以我们要找到根然后返回A根节点

之后我们在测试了Frank中来实例化这个对象，然后来输出这个二叉树。

这时候打断点进行测试 可以发现没啥问题

6.二叉树习题（让你更好了解二叉树）

6.1.前情提要

（1）二叉树有4种遍历方式（自己blibli上面看看视频，我要写太多了而且我写了你们也看不懂还是视频比较好）

前序遍历 根左右

中序遍历 左根右

后续遍历 左右根

层序遍历一层一层遍历从上到下从左到右

6.2二叉树习题讲解

（1）后续遍历前序遍历都可以得到根是哪一个，再推导出来中序遍历

 6.3.通过代码实现二叉树

     实现前序中序后序三种遍历方式

 6.3.1前序遍历的实现

先根然后遍历左边的所有树，再遍历右边的所有数。

每次遍历完往下面走就将其当成一个完整的树进行遍历

代码实现

递归左边然后右边就前序遍历完成了。 

图解

6.3.2中序遍历的实现 

代码实现

图解

 6.3.3后序遍历的实现

图解

代码实现

7.二叉树的具体实现

7.1获取树中节点总数（正常思路和子问题思路）

正常思路

 代码实现

子问题思路

大家会疑惑再size2中为什么tmp可以等于这个东西它是如何计算的？

我们通过图解来给大家讲解

图解：

 7.2获取二叉树的叶子节数方法（正常思路和子问题思路）

正常思路：

总体原理：进行递归然后当左右递归都为null 就是叶子节点（左子树的叶子加上右子树的叶子）

两种思路自己看一下

 正常思路

子问题思路 （总节点个数等于左子树节点个数+右子树节点个数+root）

0 + 0 =1!!!!!!!!!!!

图解思路

 7.3求第k层节点的个数

子问题思路：k层的左右相加在向上递归最后加起来总和就可以了

 所以我们要先求左树的高度然后再求右树的高度然后进行比较再加一就可以了

图解（递归图解）

代码思路

 图解

还有三目运算符也是可以的：自己写一下我喜欢用max

7.4查找这个元素在二叉树中是否存在

这个方法本身不会抛出异常，但是运行的时候由于我们return了一个null在结尾的时候，这时候就会发生空指针异常，所以在使用的时候要用try catch语句进行包裹来抛出异常

遍历整个二叉树，然后找到这个节点输出

子问题思路：

（1）根节点是不是要找的数据

（2）去左子树找再去右子树找

（3）如果root的val不等于你找的val就ruturn null找到了就return true

图解

代码实现 

代码思路ctrl加鼠标滚轮方法自己看

 

7.5 层序遍历（后序补充，看到这里去看二叉树练习）

7.6判断一棵树是不是完全二叉树（后序补充，看到这里去看二叉树的练习）