共计 2301 个字符，预计需要花费 6 分钟才能阅读完成。
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 的树都是齐全二叉树；
图片
本篇文章写到这里就完结了，因为技术水平无限，文章中难免会出错，欢送大家批评指正。
