20220805—第八组—王凌霄—学习笔记

树和集合

集合的前提知识：数据结构—树

结点：结点是数据结构中的基础，构成复杂数据结构的基本组成单位

树（Tree）：是n（n >= 0）个节点的有限集，n = 0时称为空树

在任意的非空数中：

1.有且仅有一个特定的称为根结点

2.当n > 1时，其余节点可分为m个互不相交的有限集

定义树时：

1.根结点是唯一的，不能存在多个根结点

2.子树的个数没有限制，但他们一定是互不相交的

树的定义中，使用了递归的方式。递归在树的学习过程中，起着重要的作用。

结点的度：某一个结点拥有子结点的数量就成为结点的度

结点之间的关系：

结点子树的根结点称为该结点的孩子结点。

相应该结点称为孩子结点的父结点（双亲结点）。

结点层次

树的深度

树中结点的最大层数称为树的深度或高度。

二叉树：

二叉树是n个结点的有限集合，如果n = 0，那就成为空二叉树

二叉树的特点：

1.每个结点最多只有两颗子树，所以二叉树中不存在度大于2的结点

2.左子树和右子树是有顺序的，次序不能任意颠倒

3.技术树中某个结点只有一颗子树，也要区分它是左子树还是右子树

二叉树的性质：

1.在二叉树中第i层上最多有2^（i – 1）个结点（i >= 1）

2.二叉树中如果深度为k，那么最多有2^k – 1个结点

3.n0 = n2 + 1，n0表示度数为0的结点，n2表示度数为2的结点数

4.在完全二叉树中，具有n个结点的完全二叉树的深度为【log2n】 + 1。其中【log2n】是向下取整。

5.若对含n个结点的完全二叉树从上到下并且从左到右进行1至n的编号，则对完全二叉树任意一个编号为i的结点有如下特性：

（1）若i = 1，则该结点是二叉树的根，无父结点，否则编号为i / 2的结点为其父结点。

（2）若2i > n，则该结点无左子结点，否则编号为2i 的结点为其左子结点。

（3）若2i + 1 > n，则该结点无右子结点，否则编号为2i + 1的结点为右子结点

斜树：

所有的结点都只有左子树的二叉树叫做左斜树。所有结点都是只有右子树的二叉树叫做右斜树。

满二叉树：

在一棵二叉树中如果所有分支结点都存在左子树和右子树，并且所有的叶子（子结点）都在同一层上，这样的二叉树叫做满二叉树。

满二叉树的特点：

1.叶子只能出现在下一层。

2.非叶子（子结点）的度一定是2

3.在同样深度的二叉树中，满二叉树的结点的个数最多，叶子（子结点）数也最多。

完全二叉树：（特殊的满二叉树，可以少不能多）

对一颗具有n个结点的二叉树按层编号，如果编号为i（1 <= i <= n）的结点与同样深度的满二叉树中编号为i的结点位置完全相同，这颗二叉树就称为完全二叉树。

二叉树的存储结构：

1. 顺序存储

使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

当二叉树为完全二叉树时，结点数刚好填满数组。

如果二叉树不是完全二叉树，采用顺序存储的话，顺序存储结构中已经出现了空间浪费的情况。

比如右斜树这种极端情况，采用顺序存储的方式是十分浪费空间的。

一般顺序存储只适用于完全二叉树。

2. 二叉链表

顺序存储不能满足二叉树的存储要求，考虑采用链式存储。

二叉树的每个结点都有两个子结点，可以将结点数据结构定义成一个数据和两个指针域。

二叉树的遍历（重点考察）

二叉树的遍历从根结点除法，按照某种次序依次访问二叉树中所有的结点。（遍历）使得每个结点被访问一次，且仅被访问一次。

二叉树的访问次序可以分为四种：（用递归或者栈遍历）

自上而下，从左到右，每个结点会走三次（三种遍历方式）。

四种遍历方式：

前序遍历：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左再向右的方向。

中序遍历：从二叉树的根节点出发，当第二次到达结点时就输出结点数据，先向左再向右的方向访问。

后序遍历：从二叉树的根结点出发，当第三次到达结点时就输出结点数据，先往左再往右的方向。

层次遍历（常用）：按照树的层次自上而下的遍历二叉树。

用递归、用栈

其他的树分类：

1. 二叉查找树（二叉搜索树、二叉排序树）
   • 若左子树不为空，左子树的所有的值都小于它的根结点的值
   • 若右子树不为空，右子树的所有的值都大于它的根结点的值
   • 左右子树也分别是一个二叉查找树（二叉搜索树、二叉排序树）
   • 没有键值相等的点，要么大要么小（任何一个结点的值都不能相等）
2. 平衡二叉树（AVL树）

    含有相同结点的二叉树的不同形态，找出一个查找平均长度最小的一颗二叉查找树。

• 要么是一颗空树，要么其根结点的左右子树的深度之差的值不能超过1
• 左右子树也都是平衡二叉树
• 二叉树结点的平衡因子定义为该结点的左子树的深度减去右子树的深度。

    平衡因子  =   左子树的深度   –    右子树的深度

    平衡因子的绝对值不能超过1

3. 红黑树（HashMap阶段重点应用）

    一种自平衡的二叉树。又增加了一个颜色的属性。

    结点的颜色只能是红色或黑色。

• 根结点只能是黑色
• 红黑树中，所有的叶子结点后面再接上左右两个空结点，可以保持算法的一致性，所有的空结点也都是黑色
• 其他的结点要么是黑色要么是红色。如果是红色结点的父结点和左右子结点都是黑色。（黑红相间）
• 在任意一棵子树中，从根结点向下走到空结点的路径上所经历的黑结点数是相同的，保证是一个平衡二叉树。

4. B – 树（B树）

    是一种平衡的多路查找树，它在文件系统中很有用（数据库中）。一棵m阶级的B – 树的性质：

• 树中每个子结点至多有m棵子树
• 若根结点不是叶子结点，则至少有两棵子树（可以更多）
• 除根结点外所有非终端结点至少有【m / 2】棵子树
• 每个结点的信息结构（A0，K1，A1，…….Kn，An），其中n表示关键字，K为关键字，A是指针。
• 所有的叶子结点都出现在同一层次上，且不带任何信息。（保持算法的一致性）

5. B + 树

B – 树和B + 树在数据库重点应用

集合

什么是集合？

存放数据的一个容器

使用集合的目的：更方便的存储和操作数据，CRUD。

集合的继承结构

Collection< E >：存放单值的最大父接口

Collection类下的子接口：

List< E >：（列表）线性表：和数组类似，List可以动态增长，查找元素的效率高，插入删除元素的效率低，因为会引起其他元素位置的改变

Set< E >：也是一个线性表,检索元素的效率较低，删除和插入的效率高，插入和删除不会引起元素移位。

Map< K , V >：存放对值的最大父接口

Map< >：（映射）用于保存具有映射关系的数据，Map保存着两组数据：key和value都可以是任意的引用数据类型，但key不能重复。

List，Set继承自Collection，Map不是。

ArrayList内部结构是一个数组

集合转数组

数组转集合