2022-08-05 第四组 王佳齐 学习笔记

学习笔记

1.树前提知识：数据结构—-树结点：节点是数据结构中的基础，构成复杂数据结构基本组成单位

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

在任意非空树中1.有且只有一个节点叫根结点2.当n>1时，其余结点可分为m个互不相交的有限集

定义树的时候

1.根结点是唯一的，不能存在多个根结点2.子树的个数没有限制，但他们一定互不相交树的定义中，使用了递归的方式，递归在树中的学习过程中有重要作用

结点的度

结点拥有子结点的数量叫做结点的度

结点关系

结点子树的根节点称为该结点的孩子结点相应该结点称为孩子结点的父结点（双亲结点）

结点层次

树的深度

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

二叉树

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

（一）二叉树的特点：1.每个结点最多只有两个子树，所以二叉树不存在度大于二的结点

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.非叶子节点的度一定是23.在同样深度的二叉树中，满二叉树的结点个数最多，叶子数也最多

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

（六）二叉树的存储结构1.顺序存储使用一维数组存储二叉树中的节点，并且结点的存储位置就是数组的下标索引，当二叉树为完全二叉树时，结点数刚好填满数组，如果二叉树不是完全二叉树时，采用顺序存储，顺序存储结构中已经出现了空间浪费的情况比如右斜树极端情况，采用顺序存储的方式是十分浪费空间顺序存储只适用于完全二叉树

（七）二叉链表顺序结构不能满足二叉树的存储要求，采用链式存储二叉树的每个结点都有两个孩子可以将结点数据结构定义成一个数据和两个指针域

（八）数据节点

（九）二叉树遍历：重点考察二叉树的遍历从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次二叉树的访问次序可以分为四种：

1.递归遍历自上而下，从左到右，每个结点会走三次

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

3.后序遍历从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问（左右根）

4.中序遍历从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左再向右的方向访问（左根右）

5.层次遍历按照树的层次自上而下的遍历的二叉树ABCDEFGHIJ

其他的树分类

1.二叉查找树（二叉搜索树，二叉排序树）

（1）若左子树不为空，左子树的所有的值小于他根结点的值‘                  

（2）若右子树不为空，右子树的所有的值大于他根节点的值

（3）左右子树也是一个二叉查找树

（4）没有键值相等的点

2.平衡二叉树（AVL树）含有相同结点的二叉树的不同形态，找出一个查找平均长度最小的一颗二叉查找树

（1）要么是一棵空树，要么其根节点的左右子树深度之差的值不超过1

（2）左右子树也是平衡二叉树

（3）二叉树结点的平衡因子定义为该结点的左子树深度减去右子树深度平衡因子=左子树深度-右子树深度

3.红黑树（HashMap重点应用）自平衡的二叉树，又增加了一个颜色的属性，结点的颜色只能是红色或者黑色

（1）根节点只能是黑色

（2)红黑树中，所有的叶子节点后面再接上左右两个空姐点，保持算法的一致性

（3）其他的结点要么是黑色，要么是红色，红色节点的父节点和左右孩子结点都是黑色

（4）在任一棵子树中，从根节点向下走到空结点的路径上所经历的黑结点数

4.B-树（B树）B-树是一种平衡多路查找树，他在文件系统中很有用，一颗m阶B-树

（1）树中每个子结点至多有m棵子树

（2）若根节点不是叶子节点，则至少有2棵子树

（3）除根结点外所有非终端节点至少有[m/2]棵子树

（4）每个结点的信息结构（A0，A1…….Kn，An），其中n表示关键字的个数，K 为关键字，A是指针

（5）所有的叶子节点都出现在同一层次上，且不带任何信息5.B+树B-树和B+树，后续在数据库阶段才会重点应用

 

 

集合

 

集合框架（重要）

集合：容器，存放数据的一个容器

使用集合的目的：更方便的存储和操作数据，CRUD。 集合继承结构 Collection ：存放单值的最大父接口

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

Set 也是线性表，检索元素效率低，删除和插入的效率高，插入和删除不会引起 元素移位。

Map ：存放对值的最大父接口 Map（映射）用于保存具有映射关系的数据，Map保存着两组数据：key和value。 key和value都可以是任意的引用数据类型，但key不能重复。

List，Set继承自Collection，Map不是

 

1.如果初始化集合尽量指定初始化容量，如果确定不了，默认指定为16

2.使用泛型，数据的类型时候，一定要使用引用数据类型。

 

List集合中存放的数据：

1.数据有顺序（添加的先后顺序）

2.数据可以重复

 

学习笔记：今天上午学了树，感觉知识太多了，下午学的集合和数组有很多相似的地方。