Java常见数据结构与算法 .pdf

Java常见数据结构与算法 ⼀、线性表 1.数组实现 2.链表 ⼆、栈与队列 三、树与⼆叉树 1.树 2.⼆叉树基本概念 3.⼆叉查找树 4.平衡⼆叉树 5.红⿊树 ⼀、线性表 线性表是最常⽤且最简单的⼀种数据结构，它是n个数据元素的有限序列。 实现线性表的⽅式⼀般有两种，⼀种是使⽤数组存储线性表的元素，即⽤⼀组连续的存储单元依次存储线性表的数据元素。另⼀种是使⽤链 表存储线性表的元素，即⽤⼀组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。 链表是⼀种物理存储单元上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由⼀系列节 点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下⼀个节点，这样当添加或者删除时，只需 要改变相关节点的Next的指向，效率很⾼。 常见的链表有循环单链表，双向链表，循环双向链表。 循环单链表 主要是链表的最后⼀个节点指向第⼀个节点，整体构成⼀个链环。 双向链表 主要是节点中包含两个指针部分，⼀个指向前驱元，⼀个指向后继元，JDK中LinkedList集合类的实现就是双向链表。 循 环双向链表 是最后⼀个节点指向第⼀个节点。 ⼆、栈与队列 栈和队列也是⽐较常见的数据结构，它们是⽐较特殊的线性表，因为对于栈来说，访问、插⼊和删除元素只能在栈顶进⾏，对于队列来说， 元素只能从队列尾插⼊，从队列头访问和删除。 栈是限制插⼊和删除只能在⼀个位置上进⾏的表，该位置是表的末端，叫作栈顶，对栈的基本操作有push(进栈)和pop(出栈)，前者 相当于插⼊，后者相当于删除最后⼀个元素。栈有时⼜叫作LIFO(Last In First Out)表，即后进先出。 队列是⼀种特殊的线性表，特殊之处在于它只允许在表的前端 （front）进⾏删除操作，⽽在表的后端 （rear）进⾏插⼊操作，和栈⼀ 样，队列是⼀种操作受限制的线性表。进⾏插⼊操作的端称为队尾，进⾏删除操作的端称为队头。 三、树与⼆叉树 树型结构是⼀类⾮常重要的⾮线性数据结构，其中以树和⼆叉树最为常⽤。在介绍⼆叉树之前，我们先简单了解⼀下树的相关内容。 树 是由n（n=1）个有限节点组成⼀个具有层次关系的集合。它具有以下特点 ：每个节点有零个或多个⼦节点 ；没有⽗节点的节点称 为 根 节点 ；每⼀个⾮根节点有且只有⼀个 ⽗节点 ；除了根节点外，每个⼦节点可以分为多个不相交的⼦树。 定义 ⼆叉树是每个节点最多有两棵⼦树的树结构。通常⼦树被称作“左⼦树”和 “右⼦树”。⼆叉树常被⽤于实现⼆叉查找树和⼆叉堆。 相关性质 ⼆叉树的每个结点⾄多只有2棵⼦树(不存在度⼤于2的结点)，⼆叉树的⼦树有左右之分，次序不能颠倒。 ⼆叉树的第i层⾄多有2^(i-1)个结点；深度为k的⼆叉树⾄多有2^k-1个结点。 ⼀棵深度为k，且有2^k-1个节点的⼆叉树称之为 满⼆叉树 ； 深度为k，有n个节点的⼆叉树，当且仅当其每⼀个节点都与深度为k的满⼆叉树中，序号为1⾄n的节点对应时，称之为 完全⼆叉树 。 三种遍历⽅法 在⼆叉树的⼀些应⽤中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点进⾏某种处理，这就涉及到⼆叉树的遍历。⼆叉树 主要是由3个基本单元组成，根节点、左⼦树和右⼦树。如果限定先左后右，那么根据这三个部分遍历的顺序不同，可以分为先序遍历、中 序遍历和后续遍历三种。 (1) 先序遍历 若⼆叉树为空，则空操作，否则先访问根节点，再先序遍历左⼦树，最后先序遍历右⼦树。 (2) 中序遍历 若⼆叉树为空，则 空操作，否则先中序遍历左⼦树，再访问根节点，最后中序遍历右⼦树。(3) 后序遍历 若⼆叉树为空，则空操作，否则先后序遍历左⼦树访 问根节点，再后序遍历右⼦树，最后访问根节点。 树和⼆叉树的区别 (1) ⼆叉树每个节点最多有2个⼦节点，树则⽆限制。 (2) ⼆叉树中节点的⼦树分为左⼦树和右⼦树，即使某节点只有⼀棵⼦树，也要指明 该⼦树是左⼦树还是右⼦树，即⼆叉树是有序的。 (3) 树决不能为空，它⾄少有⼀个节点，⽽⼀棵⼆叉树可以是空的。 ⼆叉查找树就是⼆叉排序树，也叫⼆叉有哪些信誉好的足球投注网站树。⼆叉查找树或者是⼀棵空树，或者是具有下列性质的⼆叉树： (1) 若左⼦树不空，则左⼦树 上所有结点的值均⼩于它的根结点的值 ；(2) 若右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值 ；(3) 左、右⼦树也分别为⼆ 叉排序树；(4)