内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

10.1二叉树

10.1.1为什么需要树这种数据结构

1.数组存储方式的分析

优点:通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点:如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低[示意图]

画出操作示意图

2.链式存储方式的分析

优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

缺点:在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)【示意图】

操作示意图

3.树存储方式的分析

能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。【示意图,后面详讲】

案例: [7,3,10,1,5,9,12]

10.1.2树示意图

树的常用术语(结合示意图理解):

1.        节点

2.        根节点

3.        父节点

4.        子节点

5.        叶子节点(没有子节点的节点)

6.        节点的权(节点值)

7.        路径(从root节点找到该节点的路线)

8.        层

9.        子树

10.      树的高度(最大层数)

11.      森林:多颗子树构成森林

10.1.3二叉树的概念

1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

2)二叉树的子节点分为左节点和右节点

3)示意图

4)如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2'n-1,n为层数，则我们称为满二叉树。

5)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

10.1.4二叉树遍历说明

使用前序，中序和后序对下面的二叉树进行遍历

1.      前序遍历:先输出父节点，再遍历左子树和右子树

2.      中序遍历:先遍历左子树，再输出父节点，再遍历右子树

3.      后序遍历:先遍历左子树，再遍历右子树，最后输出父节点

4.      小结:看输出父节点的顺序，就确定是前序，中序还是后序

10.1.5二叉树遍历应用实例(前序,中序,后序)

应用实例的说明和思路

代码实现