数据结构学习3
树型结构：
1、树的基本概念：
一种表示层次关系（一对多）的数据结构
有且仅有一个特定节点，该节点没有前趋节点，称为这棵树的根节点
剩余有n个（n>=0）有限个多节点组成互不相交的子集，每个子集都可以是一棵树，都被称为根节点的子树
注意：树中有树，树型结构具有递归性
2、树的表示方式：
倒悬树、凹凸法、嵌套法
3、树的相关专业术语（不同资料不同说法）：
节点（结点）：组成树的基础元素，同时它也可以是一棵树
节点的度，该节点子树（直接相关的子节点）的数量
树的度（密度）：树中所有节点的数量
树的层次：从根节点算第一层，依次往下递增
节点的层次：从该节点起算第一层，依次往下递增
树的深度：树的最大层次数
叶子节点：节点的度为0的节点
双亲节点和孩子节点（父节点、子节点）：
节点的直接节点称为该节点的子节点，该节点就是它们子节点的父节点。
兄弟节点：具有同一个父节点的节点，互为兄弟节点
堂兄弟节点：双亲在同一层时节点互为堂兄弟节点
祖先节点：从该节点出发，该节点是经过的所有节点的祖先节点
森林：由n个不相交的树组成的集合称为森林。
4、普通树的存储方式
树可以顺序存储，也可以链式存储，还可以混合存储，以存储的信息为依据，有以下不同的存储表示方式：
双亲表示法：顺序
位置（下标） data 双亲位置
0 A -1
1 B 0
2 C 0
3 D 0
优点：查找双亲很方便
缺点：查找孩子效率较低
孩子表示法：
顺序存储：
位置（下标） data sub_arr(存储子节点位置下标的数组)
0 A 1 2 3
1 B 4 5
2 C 6
3 D 7 8
4 E 9
5 F
6 G 10
7 H
8 I
9 J
10 K
缺点：非常了浪费空间
链式+顺序：
位置（下标） data ListHead(指向第一个子节点链表)
0 A 1->2->3->NULL
1 B 4->5->NULL
2 C 6->NULL
3 D 7->8->NULL
4 E 9->NULL
5 F
6 G 10->NULL
7 H
8 I
9 J
10 K
优点：节省空间
优点：查找孩子方便
缺点：查找双亲不方便
兄弟表示法：
双亲只存储第一个子节点，然后链式指向所有的兄弟节点
数据项：
第一个孩子 数据 指向兄弟的指针
优点：方便查找兄弟节点，找孩子节点也方便
缺点：不方便找双亲
总结：普通树不常用，一般要转换成二叉树表示。
二叉树：
使用常用的一种数据结构，处理起来比普通树要方便的多，并且普通树容易转移成二叉树
普通树转二叉树：孩子变左子树，兄弟变右子树（二叉树的每个节点的左节点表示普通树节点的第一个子节点）
树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子。
例子：
A A
/|\ /
B C D ——> B
/\ /\ /
E F G H E C
\
F D
/
G
H
定义：节点的度最多为2
特殊的二叉树：
满二叉树：
如果一颗二叉树只有度为0的节点和度为2的节点，并且度为0度节点在同一层，则这颗树叫做满二叉树。
完全二叉树：
深度为k，有n个节点的二叉树当且仅当起每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，
称为完全二叉树。
除最后一层外，其他层全满，且最后一层的节点要从左到右排列，便是完全二叉树。
有序二叉树、排序二叉树、搜索二叉树、查找二叉树、平衡二叉树AVL树、堆（大顶堆、小顶堆）、红黑树、哈夫曼树、线索二叉树
二叉树的性质（重点）：
1、二叉树的第i层上至多有2^(i-1)个节点，其中i>1，要是每层都满足这个的话，那么该树便是满二叉树。
2、深度为h的二叉树中，至多含有2^h-1个节点
3、若在任意一颗二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1；
4、具有n个节点的满二叉树深为log2n+1
5、若对一颗有n个节点的完全二叉树进行顺序编号（1<=i<=n）,那么，对于编号为i（i>=1） 的节点
当i=1时，该节点为根，它无双亲节点
当i>1时，该节点的双亲节点编号为i/2
若2i<=n时，则有编号为2i的左节点，否则没有左节点
若2i+1<=n，则有编号为2i+1的右节点，否则没有右节点。
6、对于节点为n的二叉树，其深度为log2（n）+1；
二叉树的操作：
构建、销毁、遍历、高度、密度、插入、删除、查询、求左、求右
二叉树的遍历（重点）：
前序：根、左、右
中序：左、根、右
后序：左、右、根
层序：从上到下、从左到右依次遍历一棵树，必须配合队列完成。
注意：前中后序遍历取决于根的遍历顺序，左右子树的遍历顺序不会改变的
注意：可以根据前序+中序 或者 后序+中序 就可以还原一颗树，但是只有一个遍历或者前序+后序是无法还原的
要会写遍历结果，能倒推还原树。
二叉树的存储：
顺序：必须按照完全二叉树（并不是满二叉树）的顺序格式存储节点数据，如果有空位置那么就用特殊符号代替（就如‘#’）。
数据项：
存储节点的内存首地址
容量
一、有序二叉树
有称为二叉排序树、二叉搜索树、二叉查找树
左子树的数据小于根的数据，根的数据小于右子树数据，这种树称为有序二叉树
有序二叉树中的中序遍历的结果是从小到大排序，因此有序二叉树也可以是一种排序算法。
并且对有序二叉树的查找天然是二分查找，所以有序二叉树经常考。
注意：需要根据插入的数据来还原一颗有序二叉树
二、线索二叉树
规律：在有n个节点的链式二叉树，必定存在n+1个空指针域。
在链式二叉树中，有很多没被使用的空指针会造成一定的浪费，在有序二叉树中，可以让这些指针指向下一个\前一个节点，
这种树就被称为线索二叉树，以中序遍历时，可以不用递归，而是通过循环即可，从而提高树的遍历的效率和节约内存。
中序线索二叉树节点数据项：
数据
左子树指针
右子树指针
右子树是否是线索标志（为真：右子树线索；为假：右子树不是线索）
实现线索二叉树的过程：
1、生成得到一颗普通的有序二叉树
2、按照中序来遍历整棵树进行创建线索
3、按照线索来循环遍历线索二叉树
LTag = 0 lchild域指示节点的左孩子
1 lchild域指示节点的前驱
RTag = 0 rchild域指示节点的右孩子
1 lchild域指示节点的后继
三、选择树（胜者树、败者树）
是一种完全二叉树，把待比较的数据存储在最后一层，根节点是左右子树中的其中一个，是他们的最大或最小值，不停的比较形成一颗选择树。
作用：能快速的找出最大值或者最小值，如果带比较数据有部分更新，重新选择的速度也很快。
四、堆 heap
是一种完全二叉树，不适合使用链式存储，适合用顺序存储
不适合使用链式存储，适合使用堆存储
大顶堆（大根堆）：
根节点比左右子树大
小顶堆（小根堆）：
根节点比左右子树小
数据项：
存储数据的首地址
容量
数量
操作：
创建、添加、删除、空堆、满堆、堆顶、
堆的顺序存储是指使用数组来表示堆，而不是使用链表。这是因为堆的顺序存储具有以下优点：
1、索引计算简单：使用数组存储堆可以通过索引计算来访问和操作元素。
对于完全二叉树，父节点和子节点之间的关系可以通过简单的索引计算得到。
例如，对于节点i，其父节点的索引为(i-1)/2，左子节点的索引为2i+1，右子节点的索引为2i+2。
这种索引计算的方式非常高效，并且不需要额外的指针来表示节点之间的关系。
2、内存连续性：数组在内存中是连续存储的，这对于计算机的缓存系统来说更加友好。
当我们访问数组中的一个元素时，由于内存连续性，计算机可以预加载相邻的元素到缓存中，提高访问效率。
而链表的存储方式是通过指针连接的，节点之间的内存地址可能是分散的，这会导致缓存不命中，访问效率较低。
3、空间效率高：链式存储需要为每个节点额外存储指针信息，而顺序存储则只需要存储节点的值即可。
因此，顺序存储相对于链式存储来说，具有更高的空间效率。
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于
走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
从1/2提高到2/3；
一、平衡二叉树
平衡二叉搜素树
它是一棵有序二叉树，它的左右子树高度差不超过1，且它的所有子树都满足这个条件
如果有一个有序的二叉树接近单支状，它的查找效率很接近链表，因此只有当它达到平衡时它的查找效率是最高的
由于是有序二叉树，节点的位置是受到值的影响，所以只能通过调整节日关系来达到平衡状态
平衡二叉树不平衡的基础原因：
x y
/ \ /
y t1 以y为轴向右选择 z x
/ \ / \ /
z t2 t3 t4 t2 t1
/
t3 t4
x y
/ \ / \
t1 y 以y为轴向左选择 x z
/ \ / \ / \
t2 z t1 t2 t3 t4
/ \
t3 t4
x x z
/ \ / \ / \
y t1 z t1 y x
/ \ / \ / \ / \
t2 z y t4 t2 t3 t4 t1
/ \ / \
t3 t4 t2 t3
以z为轴左旋转 以z为轴右旋转
x x z
/ \ / \ / \
t1 y t1 z x y
/ \ / \ / \ / \
z t2 t3 y t1 t3 t4 t2
/ \ / \
t3 t4 t4 t2
以z为轴右旋转 以z为轴左旋转
注意：都是找中间值为轴 进行左旋右旋
二、红黑树
是一种自平衡的二叉树，但不是严格遵循高度差不超过1的原则，是一种伪平衡的二叉树，是通过节点的高度以及节点的颜色来达到相对平衡的状态
红黑树的特征：
（1）每个节点或者是黑色，或者红色
（2）根节点是黑色
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树的优缺点：（为什么要选择红黑树？）
优点：插入、删除效率要比AVL树要高，因为旋转调整的频率没有AVL树高
缺点：没有AVL树那么平均，查找效率没有AVL树那么高，但是也不差
红黑树的综合性能是最优的，很多的标准库的数据结构的底层实现是使用红黑树
三、哈夫曼树\霍夫曼树
基本概念：
路径长度：从一个节点开始到另一个节点之间的路径条目数
根节点到第L层上的任意节点的路径长度为L-1；
树的路径长度：从根节点出发到每个节点的路径长度之和
节点的权：将树中的节点额外赋予某种含义的数值，该数值就称为节点的权
节点的带权路径长度：从根节点出发到该节点之间的路径长度与该节点权的乘积
树的带权路径长度：所有叶子节点的带权路径长度之和，简称WPL
WPL是衡量一颗带权二叉树优劣的关键
哈夫曼树是一颗带权二叉树，并且它的WPL最小
构建一颗哈夫曼树：
1、把n个带权节点存入集合F中，每个节点左右子树置空
2、从F中选取根节点的权值最小的两个节点，作为左右子树构建成一颗新的二叉树，把左右子树的权值之和作为该树的根节点的权值
3、从F中删除刚刚选择的两个节点，把新的到的二叉树放入F中
4、重复2、3步骤，直到F中只剩下一棵树，便是哈夫曼树
四、哈夫曼编码
目的：当年是为了解决远距离通信时传输数据的最优解问题
待发送文字：ABCAA EEDFB
方法1:转成二进制发送
A 000 B 001 C 010 D 011 E 100 F 101
总共要发送30个0\1
方法2:
1、根据待发送文字的频率、构建一颗哈夫曼树
假设频率：A27 B8 C15 D15 E30 F5
2、设置哈夫曼树的左分支为0、右分支为1，从根节点出发到每个叶子节点经过的路径分支组成的0\1的编码便是所谓的哈夫曼编码
作用：数据、文件压缩的一种方式
图（Graph）型结构：
什么是图型结构：由有穷且非空的顶点和顶点之间的边组成，通常表示为G（V，E）
G表示一个图，V是图中顶点的集合，E是图中的边（顶点之间的关系）的集合
图的基本概念：
简单图：不存在顶点到自己的边，不存在重复的边，数据结构中只研究简单图
无向图，边是用（A，B）方式表示，表示顶点A到B是互通的
完全无向图：在无向图中，任意两个顶点之间都有边，在含有n个顶点的完全无向图中，有n（n-1)/2条边
有向图：边是用<A，B>方式表示，仅表示从A到B方向有边，在有向图中边也叫做弧，A表示弧尾，B是弧头
完全有向图：在有向图中，任意两个顶点之间都有方向相反的弧，在含有n个顶点的完全有向图中，有n(n-1)条弧。
稀疏图：图中顶点多、边少，具体多少没有规范
稠密图：图中边的数量多
带权图：给图中的边赋予某种含义的数值，称之为该边的权重，图中所有边都有权重的图称之为带权图，也称为网度，依附于某个顶点的边的数量
称为该顶点的度，在有向图中，又分出度（从该顶点出发的弧数量）、入度（其他顶点指向该顶点的弧数量）
路径：从某个顶点到另一个顶点之间经过的边，称之为两个顶点之间的路径
路径的长度：两个顶点之间路径上的边的条目数
环：图中有顶点能经过边后能回到自身，称该图有环
回路：专指有向图中，从某点出发，最终通过弧回到该点，称图中有回路，在回路上的顶点一定有出度、入度，顶点序列中存在不重复出现的路径称为简单路径
连通：如果顶点V1到顶点V2之间有路径，则称V1V2是连通的
连通图：任意两个顶点之间是连通的，n个顶点的图中，至少需要n-1条边才可能形成连通图，也称为生成树，如果给边配上权值，其中权重的代价最小的生成树，称为最小生成树
图的遍历方式：
深度优先遍历（DFS）：
从每个顶点出发，一直往下一个顶点遍历，直到没有下一个顶点为止，再返回上一个顶点的其他路径继续进行深度优先，直到该出发顶点的所有深度优先遍历结束，同样的
操作对每个顶点都进行一次，该过程中会有顶点被重复遍历，需要记录是否被遍历过的标志位，防止结果重复。
广度优先遍历（BFS）：
从某个顶点出发，把所有的下一层顶点都进行依次遍历，结束后再对该层每个顶点广度优先遍历，直到该出发顶点的广度优先遍历结束，同样的操作对每个顶点都进行一次。
可以借助队列完成
无论是DFS\BFS遍历结果不唯一，与顶点顺序有关
图的存储方式
邻接矩阵：
用一个一堆数组存储n个顶点，根据顶点数量使用n*n的二维数组来存储边
char V[n] = {A,B,C,D,E,F,G};
char E[n][n]
A B C D E F G
A
B
C
D
E
F
G
在二维数组E[i][j]的值为1时，则表示V[i][j]之间有边
注意：由于不存在自己到自己的边，所以左对角线上的值一定为0
注意：如果存储的是无向图，那么一定沿左对角线对称，可以进行压缩成一维数组（参考矩阵的压缩）
优点：计算顶点的度、出度、入度都很方便
缺点：当图越稀疏时，会越浪费存储空间，
邻接表：
边：
顶点下标
指向下一条边的指针
顶点：
数据
指向第一条边的指针
图：
由顶点组成的数组
顶点数量
优点：可以节约存储空间、计算出度简单
缺点：计算入度麻烦
十字链表：
专门存储有向图
优点：找出度、入度都很方便、也不浪费空间
邻接多重表：
专门存储无向图
优点：找某个顶点相关的边