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的树都是齐全二叉树；

图片

本篇文章写到这里就完结了，因为技术水平无限，文章中难免会出错，欢送大家批评指正。