Java版的数据结构和算法（三） java

PS：本文系转载文章，阅读原文可读性会更好，文章末尾有原文链接
目录
1、数组、链表、树存储方式的区别

1、1 数组的存储方式 1、2 链表的存储方式 1、3 树的存储方式

2、二叉树

2、1 二叉树的常用术语 2、2 二叉树的概念2、2、1 二叉树2、2、2 满二叉树2、2、3 完全二叉树

1、数组、链表、树存储方式的区别
1、1 数组的存储方式
优点：通过下标形式访问元素，速度快；如果是有序数组，还可以使用折半查找算法、插值查找算法和斐波纳契查找算法提高查找速度。
缺点：如果是按一定顺序插入值会整体移动，效率会很低；如果是数组要进行扩容，每次在底层都需要创建新是数组要将原来的数据拷贝到数组，并插入新的数据，ArrayList 底层就是这样实现的，ArrayList 中维护了一个 Object 类型的数组 elementData，如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容 elementData 为 10，如果需要再次扩容的话，则扩容 elementData 为1.5倍。
假设一个 ArrayList 里装的元素是{1,2,3,5,6}，然后往 ArrayList 中索引为3的地方插入一个元素4，我们看一下 ArrayList 插入数据的流程图（图1）；
图片
可以看到索引为3以及索引大于3的元素都会往后移动位置，也就是5和7往后移动一个位置
1、2 链表的存储方式
优点：在一定程度上对数组存储方式进行了优化，例如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很高。
缺点：在进行查找时，效率仍然还很低，比如，查找某个值时，需要从头节点开始遍历。
假设一条链表里有一堆元素{1,2,3,5,6}，往这条链表里索引为3的位置插入一个4的元素，我们看一下链表插入数据的流程图（图2）；
图片
可以看到插入索引的前一个索引的元素指向新的元素（即3指向4），新的元素指向插入索引的前一个索引元素原来指向的元素（即4指向5），可以看出链表的插入不用移动元素。
1、3 树的存储方式
优点：利用二叉排序树，我们可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度，所以在这方面树的存储方式能提高数据存储，读取的效率。
好，我们列举一下二叉排序树添加、删除和查找过程，我们假设一个数组 arr={7,3,10,1,5,9,13}，然后将数组 arr 转换成对应的二叉树（转换规则先不用理会），然后就得到了一个二叉树图（图3）；
图片

首先我们说一下这棵二叉树的一些概念和规律，一棵树分为根节点、左子节点和右子节点，像7这个节点就是根节点，像3这个节点就是7的左子节点，像10这个这个节点就是7的右子节点；这棵树是有一定规律的，看左子节点总是小于根节点，而根节点总是小于右子节点。

（1）查找，假设查找的节点是13，查找的节点跟根节点7做比较，发现查找的节点大于根节点7，然后就往7的右子节点10做比较，也发现查找的节点大于节点10，又然后往10的左子节点13做比较，终于相等了，一共做了3次比较。
（2）添加，假设要添加的节点是14，要添加的节点跟根节点7做比较，发现要添加的节点大于根节点7，然后就往7的右子节点10做比较，也发现要添加的节点大于节点10，又然后往10的左子节点13做比较，又发现节点14大于节点13且节点13的左右子节点为空，按照上面所说的概念和规律，节点14添加为节点13的右子节点。
（3）删除，假设要删除的节点是1，要删除的节点跟根节点7做比较，发现要删除的节点小于根节点7，然后就往7的左子节点3做比较，也发现要删除的节点小于节点3，又然后往3的左子节点1做比较，终于相等了，最终将节点3的左子节点置为空。
2、二叉树
2、1 二叉树的常用术语
（1）节点：每个小圆圈就是一个节点，说白了就是对象，也可以称之为节点对象。
（2）根节点：就是就是节点7（看图3），节点7往上就没有父节点了。
（3）父节点：节点7是节点3和节点10的父节点（看图3），同时节点3也是节点1和节点5的父节点，其他以此类推。
（4）子节点：节点3和节点10是节点7的子节点（看图3），节点1和节点5是节点3的子节点，其他以此类推。
（5）叶子节点：没有子节点的节点就叫叶子节点，例如：节点1、节点5、节点9和节点13 。
（6）节点的权：例如根节点7的编号是7（看图3），那么7就是根节点的权。
（7）路径：从根节点找到该节点的路线，例如：节点1的路径是7 3 1（看图3）。
（8）层：把在同一个级别的，或者说一个层面的，归结于同一层，例如：节点7在第一层，节点3和节点10是在第二层（看图3）。
（9）子树：该节点延伸出来的子节点还延伸出子节点，那么该节点的子节点形成的树就叫子树，例如：节点3、节点1和节点5形成的一棵小树就是节点7的子树（看图3）。
（10）树的高度：一棵树的最大层数，例如：图3中一棵树的最大层数是3，那么树的高度就是3 。
（11）森林：多颗子树构成森林，对于树中的每个节点而言，其子树的集合就是森林。
2、2 二叉树的概念
2、2、1 二叉树
每个节点最多只能有两个子节点形成的树就称为二叉树，例如：图4里面的树都是二叉树；
图片
2、2、2 满二叉树
若该二叉树的所有叶子节点都在最后一层，且节点总数=2n - 1，其中n为层数，则我们称为满二叉树，上面的图3其实就是一颗满二叉树。
2、2、3 完全二叉树
如果一棵二叉树的叶子节点都在最后一层或者倒数第二层，且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称之为完全二叉树，其中满二叉树也算是完全二叉树；下面图5的树都是完全二叉树；
图片
【Java版的数据结构和算法（三）】本篇文章写到这里就结束了，由于技术水平有限，文章中难免会出错，欢迎大家批评指正。