<h1 align='center'>大话数据结构
第六章 树
二叉树
普通二叉树：仅满足 “每个节点最多 2 个子节点”
满二叉树：除叶子节点外，所有节点均有 2 个子节点；且叶子节点在同一层
完全二叉树：按 “层序遍历” 填充节点，中间无空缺
二叉搜索树|二叉排序树|二叉查找树（BST）
左子树所有节点值 < 根节点值；右子树所有节点值 > 根节点值（默认无重复值）
- 删除结点时，将前驱或后继填补上来。
二叉平衡搜索树
AVL树：基于 BST，额外要求：任一节点的左右子树高度差 ≤ 1
- 概念理解：最小不平衡子树、平衡因子（左子树高度-右子树高度）
- AVL树的节点插入可以分为三个步骤：
- 新节点的插入（该节点的祖先路径上的节点有可能会受到影响）
- 平衡因子的更新（双亲的右边++）（双亲的左边--）
- 通过平衡因子确定平衡性是否被打破，若平衡性被打破，进行旋转
- AVL树的旋转：（转的是最小不平衡子树的根）
- 左单旋（L）、右单旋（R）、左右双旋（LR）、右左双旋（RL）
- 旋转规则：
- 单右旋转 - 适用于左子树过高的情况。
- 单左旋转 - 适用于右子树过高的情况。
- 左-右双旋转 - 适用于左子树的右子树过高的情况。
- 右-左双旋转 - 适用于右子树的左子树过高的情况。
- 因子小于0 --> 右右 --> 左单
- 因子大于0 --> 左左 --> 右单
红黑树：基于 BST，通过 5 条规则（如根为黑、红节点父为黑）保证近似平衡
线段树：基于完全二叉树，每个节点代表一个 “区间”，叶子节点对应单个元素
多段查找树（B树）
每个结点的孩子数可以多于两个；且每一个结点处可以存储多个元素。
- 2-3树
- 2-3-4树
- B树（B-树）
- 一个m阶的B树具有如下属性：
- 每一个非根的分支结点都有k-1个元素和k个孩子，其中$[m/2]\le k\le m$。每一个叶子结点 n 都有k-1个元素，其中 $[m/2]\le k\le m$ 。
- 所有叶子结点都位于同一层次
- 所有分支结点包含下列信息数据（$n,A_0,K_1,A_1,K_2,A_2,\cdots,K_n,A_n$），其中：$K_i(i=1,2,\cdots,n)$为关键字，且$K_i \le K_{i+1}(i=1,2,\cdots,n-1)$ ；$A_i(i=0,2,\cdots,n)$为指向子树根结点的指针，且指针$A_{i-1}$ 所指子树中所有结点的关键字均小于$K_i(i=1,2,\cdots,n)$ ，$A_n$所指子树中所有结点的关键字均大于$K_n$，$n([m/2]-1 \le n \le m-1)$为关键字的个数（或n+1为子树的个数）
- B+树
多路查找树（B树）
3 阶及以上的平衡查找树：
- 每个节点最多存 m-1 个关键字、m 个子节点（m 为 “阶”）；
- 非叶子节点至少存⌈m/2⌉-1 个关键字；
- 所有叶子在同一层
B+树
基于 B 树优化：1. 仅叶子节点存完整数据；2. 叶子节点按顺序双向链接
Trie树（字典树）
节点存储 “字符”，从根到叶子的路径代表一个字符串；同前缀共享路径
后缀树
基于字符串的所有后缀构建，每个路径代表一个后缀
堆
基于完全二叉树，满足 “堆序性”：
- 大根堆：每个父节点值 ≥ 子节点值（根为最大值）；
- 小根堆：每个父节点值 ≤ 子节点值（根为最小值）。
哈夫曼树（最优二叉树）
又称 “最优二叉树”，是带权路径长度（WPL）最短的二叉树（WPL=Σ(节点权值 × 路径长度)，路径长度为根到节点的边数）
树状数组（二叉索引树）
又称 “二叉索引树”，是简化的线段树，通过二进制索引（如节点 i 对应二进制的最低位 1）快速定位数据。
2-3树/2-3-4树
B 树的特例（2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树），节点可存储 2~3 个关键字，子节点数比关键字数多 1
最小生成树
构造连通网的最小代价生成树称为最小生成树
- 普里姆算法（Prim）：每个结点的可选边中的最小权边作为路径
- 克鲁斯卡尔算法（Kruskal）：
知识
树的相关概念
结点的分类：
- 结点的度
- 叶结点、分支结点
结点间的关系：
- 结点的孩子、孩子的双亲、兄弟、堂兄弟
- 结点的祖先、结点的子孙
其他概念：
- 结点的层次、树的深度（高度）
- 有序树、无序树
- 森林
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
二叉树的性质
边数与结点数的关系。度数与结点数的关系。
树的性质：总度数 = 边数 × 2
二叉树中，总度数 = 总结点数 - 1
二叉树中，总边数 = 总结点数 - 1
（二叉树）：
- 性质1：在二叉树的第 i 层至多有 $2^{i-1}$ 个结点（$i\ge1$）
- 性质2：深度为 k 的二叉树至多有 $2^k-1$ 个结点（$k\ge1$）
- 性质3：对任何一颗二叉树T，如果其终端结点数为 $n_0$ ，度为2的结点数为 $n_2$ ，则 $n_0=n_2+1$
- $n=n_0+n_1+n_2$ ：度为0，度为1，度为2的所有结点的和
- $n=n_1+2n_2+1$ ：度为2的结点数×2+度为1的结点数+1个根结点
- 联立求解，即得性质3
（完全二叉树）：
- 性质4：具有 n 个结点的完全二叉树的深度为 $[\log_2n]+1$ （$[x]表示不大于x的最大整数$）
- 由性质1跟性质2的数学关系示，都化为$2^n$，然后根据范围大小，数学变化得到。
- 性质5：（完全二叉树如果对一棵有 n 个结点的完全二叉树（其深度为 $[\log_2n]+1$ ）的结点按层序编号（从第1层到第 $[\log_2n]+1$ 层，每层从左到右），对任一结点 i （$1\le i\le n$）有：
如果 i=1 ，则结点 i 是二叉树的根，无双亲；如果 i>1 ，则其双亲是结点 [i/2]。
如果 2i>n ，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。
如果 2i+1 > n ，则结点 i 无右孩子；否则其右孩子是结点 2i+1 。
快速记忆法：左孩子为2i，右孩子为2i+1。反着推，以孩子结点为视角，双亲结点就是[i/2]。（1/2=0.5，通过[]取整）
- 性质4：具有 n 个结点的完全二叉树的深度为 $[\log_2n]+1$ （$[x]表示不大于x的最大整数$）
对于一个有n个节点的完全二叉树，最后一个非叶子节点的编号是⌊n/2⌋
问：应用场景？
二叉树的存储结构
- 二叉树的顺序存储结构（数组存储）
- 二叉链表（左右孩子指针）
遍历二叉树
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
两个关键词：访问和次序（是否访问、第几个访问）
按照在一个只有3个结点的二叉树中，根结点的访问次序分为前、中、后序遍历。
前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。（进入并第一级访问）
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。（进入并第二级访问）
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。（进入并第三级访问）
层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
问：应用场景？
解题技巧
记住两点：
- 先序/后序遍历可以确定根节点。
- 中序遍历可以确定左子树和右子树。
做这种题就是，反复来回这两点。分段解题。确定一部分扔一部分。
问：为什么前序+后序无法确定二叉树的形状？
遍历算法
访问=printf
遍历=指针操作推导遍历结果
已知两种遍历的结点顺序，推导另外一种遍历的结点顺序。
例题：已知前（ABCDEF）、中（CBAEDF），推后。
已知前、中，可以唯一确定一棵二叉树。
已知后、中，可以唯一确定一棵二叉树。
已知前、后，不能唯一确定一棵二叉树。
问：原因？
至少知道中序遍历的顺序才能确定二叉树的形状。中序遍历可以确定左右子树的相对位置。不能连着两个子树。
二叉树的建立
同理遍历的原理，通过输入扩展二叉树建立一颗二叉树。打印改成保存结点值。
...（索引未理解）
6.11 树、森林与二叉树的转换
树转换为二叉树
- 加线。在所有兄弟结点之间加一条连线。
- 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
- 层次调整。
森林转换为二叉树
- 把每个树转换为二叉树。
- 第一棵二叉树不动，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。
二叉树转换为树
逆向过程
- 加线。若某结点存在左孩子结点，则将这个左孩子的 n 个右孩子结点都作为此结点的孩子结点。用线连接起来。
- 去线。删除原二叉树中所有结点与其右孩子结点的连线。
- 层次调整。
二叉树转换为森林
- 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除。
- 再查看分离后的二叉树，若右孩子存在，则连线删除，直到所有右孩子连线都删除为止，得到分离的二叉树。
- 再将每棵分离后的二叉树转换为树即可。
树与森林的遍历
先根遍历
先访问树的根结点，然后依次先根遍历根的每棵子树。
后根遍历
先依次后根遍历每棵子树，然后再访问根结点。
哈夫曼树及其应用
相关定义：
- 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
- 树的路径长度就是从树根到每一结点的路径长度之和。
- 其中带权路径长度WPL最小的二叉树称做哈夫曼树
若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。
一般地，设需要编码的字符集为{d,d₂,…,dn},各个字符在电文中出现的次数或频率集合为{W₁,W₂…,W。},以d,d₂…,d,作为叶子结点，以w₁,W₂,…,w作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支代表0,右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是哈夫曼编码。
第七章 图
图的定义
图是由顶点的有穷非空集合到顶点之间的集合组成的，通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
在图中数据元素称为顶点（Vertex）
任意两个顶点之间的逻辑关系用边来表示（Edge）
图的分类
稀疏图、稠密图。网。子图。
无向图中：
无向图、无向边。G(V,E)
无向完全图。含有 n 个顶点的无向完全图有 $\frac{n \times (n-1)}{2}$ 条边
互为邻接点
顶点的度记为TD(V)
$e = \frac{1}{2} \sum TD(V)$
有向图中：
- 有向图、有向边（弧Arc）。箭头是弧头。弧尾。G<V,E>
- 有向完全图。
- 顶点邻接到；邻接自。
- 入度记为ID(V)；出度记为OD(V)；TD(V)=ID(V)+OD(V)
- $e=\sum ID(V)=\sum OD(V)$
路径的长度是路径上的边或弧的数目。
第一个顶点到最后一个顶点相同的路径称为回路或环。
连通图。无向图中的极大连通子图称为连通分量。
第八章 排序
二叉排序树
将需要在查找时插入或删除的查找表称为动态查找表。
二叉排序树，又称为二叉查找树。
$$ \frac{(1 \times 1) + (2 \times 2) + (4 \times 3) + (1 \times 4)}{8} = \frac{1 + 4 + 12 + 4}{8} = \frac{21}{8} = 2.625 ) $$
刷题经验
- 待学习：
- 红黑树
- STL的实现原理了解
- 树的广度优先搜索算法，深度。复杂度讨论
- B树的添加+删除
- 各种树的应用场景
- B-树
- 手写STL。根据方法进行实现。
- B树插入序列的过程。
- 最小生成树
- 层序遍历二叉树的实现原理：队列
- 满二叉树调整成堆（堆）
STL实现原理
map确实是基于红黑树实现的二叉树遍历算法的区别
1. 实现方法不同:
- 前序、中序、后序遍历可以用递归和非递归(栈)两种方式实现
- 层序遍历需要使用队列来实现
- 不同实现方式在空间复杂度和时间效率上都有差异
2. 应用场景不同:
- 中序遍历常用于二叉搜索树得到有序序列
- 前序遍历常用于构造表达式树
- 后序遍历常用于释放节点内存
- 层序遍历常用于计算树的高度、判断完全二叉树等存储结构、逻辑结构
存储结构有：
顺序、链式、索引、散列
逻辑结构有：
线性、非线性结构常见的应用场景
B+树是应文件系统所需而产生的B-树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。
编译器中的词法分析使用有穷自动机和语法树。
网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。
系统一般使用空闲空间链表管理磁盘空闲块。树的结点的讨论
对于一个有n个节点的完全二叉树，最后一个非叶子节点的编号是[n/2]二叉排序树的查找成功平均查找长度 ASL
ASL = (第i层的结点数 × 第i层) / 结点数编程指针的引用
void swap(Node*& left, Node*& right) {Node* temp=left; left=right;right=temp;}
// *& 表示指向指针的引用
// * 用来修改指针指向的值
// *& 用来修改指针本身