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的树都是完全二叉树;

图片

本篇文章写到这里就结束了,由于技术水平有限,文章中难免会出错,欢迎大家批评指正。

你可能感兴趣的