PS：本文为转载文章，原文可读性会更好。文末有原文链接。一、数组、链表、树存储方式的区别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。链表存储方式的优点：对a一定程度上优化了数组的存储方式，例如：插入一个值节点，只需要将插入的节点链接到链表中，删除效率也很高。缺点：在查找的时候，效率还是很低。比如查找某个值时，需要从头节点开始遍历。假设一个链表中有一堆元素{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，再与左孩子比较node3of7,发现需要删除node3的node比node3小，再对比leftchildnodeof3of3，最后相等，最后node3的leftchildnode设置为空。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的路径为731（见图3）。(8)层次：将处于同一层级或一层的归于同一层次，例如：节点7在第一层，节点3和10在第二层（见图3）。(9)子树：从这个节点扩展出的子节点也扩展出子节点，那么这个节点的子节点形成的树就称为子树，例如：节点3、节点1、节点5形成的小树是节点7的子树（参见图3）。(10)树高：一棵树的最大层数，例如：图3中一棵树的最大层数为3，则树的高度为3。(11)森林：多个子树组成一棵树森林，对于树中的每个节点，其子树的集合就是森林。2.2二叉树的概念2.2.1二叉树的每个节点最多只能有两个子节点的树称为二叉树。例如：图4中的树都是二叉树；二叉树的所有叶子节点都在最后一层，节点总数=2n-1，其中n为层数，那么我们称它为满二叉树，而上图3其实就是一棵满二叉树树。2,2,3完全二叉树如果一棵二叉树的叶子节点都在最后一层或倒数第二层，并且最后一层的叶子节点在左边是连续的，则倒数第二层右边是连续的，我们称它为完全二叉树，满二叉树也认为是完全二叉树；下图5中的树都是完全二叉树；图片是本文的结尾。由于技术水平有限，文章中难免有错误。欢迎大家批评指正。
