考研数据结构知识框架笔记
2022-10-31 10:57:32 0 举报AI智能生成
考研数据结构知识框架笔记
作者其他创作
大纲/内容
n个结点则为n阶矩阵
图：有边/弧为1，否则为0
网：有边/弧为权值，否则为∞
ltbgt邻接矩阵lt/bgt(适用于稠密图)
数组(弧尾结点)+链表(邻接点)+个数
ltbgt邻接表lt/bgt(适用于稀疏图)
ltbgt图的存储结构lt/bgt
辅助用栈，结果不唯一
访问某节点，从该结点出发
沿某路径依次访问未被访问的结点
若有顶点未访问，则选取一个未访问结点出发
重复上述过程，直到无未被访问结点
过程
：深搜过程就是对搜索树先序遍历的过程
ltbgt深度优先搜索lt/bgt
辅助用队列，结果不唯一
依次访问邻接点，再从邻接点出发
广搜过程就是对搜索树层次遍历的过程
ltbgt广度优先搜索lt/bgt
图的遍历
实质上是带权无向图。最小生成树是权值之和最小的生成树，不唯一
特点：只与顶点个数n有关，与边的个数e无关，适用于稠密图
V为连通网顶点集，U为生成树顶点集，TE为生成树边集
U={v₀}，TE=∅
计算U到其他顶点的最小代价，将该顶点纳入U，边纳入TE
重复上一步骤，知道U=V
普利姆(Prim)算法
特点：只与边的个数n有关，与顶点个数e无关，适用于稀疏图
不构成环条件下，每次选最小的边(做题技巧，不要过程时使用)
克鲁斯卡尔(Kruskal)算法
时间复杂度： ltbgtPrimnbsp ltfont color=quot#c41230quotgtO(n²)lt/fontgt，Kruskalnbsp ltfont color=quot#c41230quotgtO(e log₂e)lt/fontgtlt/bgt
ltbgt最小生成树lt/bgt
两顶点之间带权路径长度最短的路径
初始化数组
ltbgtvⱼlt/bgt为当前所求最短路径终点，另求ltbgtS∪{j}nbsplt/bgt
修改此时从ltbgtv₀出发到集合V-Slt/bgt上任意顶点ltbgtvₖlt/bgt最短路径的长度
若ltbgtdist[j]+arcs[j][k]ltdist[k]lt/bgt则令ltbgtdist[k]=dist[j]+arcs[j][k]nbsp path[k]=jlt/bgt
重复2、3、4步骤n-1次，知道S中包含全部顶点
ltbgtDijkstralt/bgt算法
使用邻接矩阵ltbgtA⁽⁰⁾、A⁽¹⁾、A⁽²⁾······、A ⁽ⁿ⁾lt/bgt
第n次计算从起点经过n-1个顶点到达某个顶点最小带权之和
若到某个顶点有更小的权值之和，则替换之前的值并修改路径
直到到达终点
ltbgtFloydlt/bgt算法
ltbgt最短路径lt/bgt
有向无环图：一个有向图中不存在环，简称DAG图
AOV网：用DAG图表示一个工程，顶点为活动，有向边为优先级，这样的网络为AOV网
由一个有向无环图的顶点组成的序列，满足一下要求，则称该图的拓扑排序
若顶点A在B的前面，则图中不存在从B到A的路径
每个顶点只出现一次
要求：
ltbgt拓扑排序lt/bgt
AOE网：用DAG图表示一个工程，顶点代表事件，边代表活动，这样的网络为AOE网
AOE网只有一个入度/出度为0的顶点，称为ltbgt源点lt/bgt/ltbgt汇点lt/bgt
整个工程完工需要多多长时间
哪些活动影响工程进度？
问题：
事件(顶点)：最早发生时间ltbgtVe(i)lt/bgt，最晚发生时间ltbgtVl(i)lt/bgt
整个工程完工的时间就是终点的最早发生的时间，关键路径就是路径长度最长的路径。
对顶点进行拓扑排序ltigt（*是任意前驱事件）lt/igt
ltbgtVe(1)=0lt/bgt
计算ltbgtVe(j)lt/bgt
ltbgtVl(n)=Ve(n)lt/bgt
计算ltbgtVl(i)lt/bgt
算法：
ltbgt关键路径lt/bgt
ltbgt应用lt/bgt
图lt/bgt
顺序存储和链式存储，时间复杂度ltbgtO(n)lt/bgt
按顺序逐个比较，直到找到或者找不到
成功ASL=ltbgt(n-1)/2lt/bgt，失败ASL=ltbgtn/2+n/(n+1)lt/bgt
ltbgt顺序查找lt/bgt
仅适用于有序的顺序表，时间复杂度ltbgtO(log₂n)lt/bgt
先从中间开始比较，比较一次抛弃一半元素逐渐缩小范围
ASL=ltbgtlog₂(n+1)+1lt/bgt
ltbgt折半查找lt/bgt
索引顺序查找，顺序查找+折半查找
块内元素可以无序，但块之间必须有序
ltbgt分块查找lt/bgt
阶：所有结点的孩子结点数的最大值
只能随机检索
ltbgtnlt/bgt个关键字，ltbgtmlt/bgt阶B树高度ltbgthlt/bgt：ltbgtlogₘ(n+1)≤h≤logₘ ₂[(n+1)/2]+1lt/bgt
每个ltbgt结点lt/bgt最多有ltbgtmlt/bgt棵子树
非叶根结点至少有ltbgt2lt/bgt棵子树
除根结点以外的所有非终端结点至少有ltbgtm/2lt/bgt(取上界)棵子树
非终端结点有ltbgtnlt/bgt个关键字和ltbgtn+1lt/bgt棵子树，关键字个数n：ltbgt(m/2)-1≤n≤m-1lt/bgt
所有叶子在同一层，不含信息
B树
可以顺序查找和随机查找
每个ltbgt分支结点lt/bgt至多ltbgtmlt/bgt棵子树
非叶根节点至少有ltbgt2lt/bgt棵子树
除根节点以外的所有非终端结点至少有ltbgtm/2lt/bgt(取上界)棵子树
结点的子树个数与关键字个数均为ltbgtm/2lt/bgt(取上界)
叶子结点包含全部关键字，且按顺序排列
B+树
ltbgtB树和B+树lt/bgt
哈希(Hash)查找
散列表/哈希表：建立了关键字与存储地址之间的一种映射关系
散列函数/哈希函数：把关键字映射到其对应存储地址的函数
装填因子：α=n/m，n个记录，m个地址空间
ltbgtltfont color=quot#c41230quotgt散列表的平均查找长度lt/fontgtlt/bgt与n和m不直接相关，而是ltbgtltfont color=quot#c41230quotgt取决于装填因子和处理冲突的方法lt/fontgtlt/bgt
不可随意删除某个元素，否则会造成查找失败
ltbgt线性探测法lt/bgt：易引起堆积现象，降低效率
ltbgt二次(平方)探测法lt/bgt：避免堆积，但无法探测到所有单元
再散列法
伪随机序列
ltbgt开放定址法lt/bgt
把所有同义词存放在一个线性链表中，散列表存放头指针
适用于经常插入和删除的情况
ltbgt链地址法lt/bgt
冲突处理
ltbgt散列查找lt/bgt
ltbgt查找
时间复杂度ltbgtO(n²)，lt/bgt空间复杂度ltbgtO(1)lt/bgt
ltbgt顺序存储和链式存储lt/bgt，ltbgt稳定lt/bgt算法
直接插入排序
时间复杂度ltbgtO(n²)lt/bgt，空间复杂度ltbgtO(1)lt/bgt
ltbgt顺序存储lt/bgt，ltbgt稳定lt/bgt算法
折半插入排序
ltbgt插入排序lt/bgt
时间复杂度ltbgtO(n¹˙⁵)lt/bgt，空间复杂度ltbgtO(1)lt/bgt
ltbgt顺序存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法
增量序列逐渐缩小到1
ltbgt希尔排序lt/bgt
一次比较相邻元素，逆序则交换，重复n-1次
ltbgt冒泡排序lt/bgt
时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtltfont color=quot#c41230quotgtO(log₂n)lt/fontgtlt/bgt
ltbgt顺序存储和链式存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法
选1个元素为轴从前向后、从后向前扫描，抓大放小，分成两部分后依次进行快排
ltbgt快速排序lt/bgt
第i次排序在剩余待排记录选一个最小(大)的放在第i个位置。
比较次数为nbspltbgtn(n-1)/2lt/bgt
ltbgt简单选择排序lt/bgt
时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtO(1)lt/bgt
小顶堆堆顶为最小元素，大顶堆堆顶为最大元素
对具有双亲结点的结点从大到小编号做出以下调整
ltbgt①lt/bgt 若孩子结点皆小于双亲结点，则该结点调整结束
ltbgt②lt/bgt 若孩子结点大于双亲结点，则将最大的孩子结点与双亲结点交换
ltbgt③lt/bgt 对交换后的堆再次重复①②，直到出现①结束
堆的初始化
将堆顶元素与编号最后一个的元素交换后弹出
对堆进行初始化，并再次重复上述步骤，直到堆空结束
堆排序
ltbgt堆排序lt/bgt
时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtO(n)lt/bgt
归并：两个或两个以上的有序表合成一个新的有序表
划分+排序（直接插入排序）
ltbgt二路归并排序lt/bgt
时间复杂度ltbgtO(d(n+r))lt/bgt，空间复杂度ltbgtO(r)lt/bgt
ltbgtltfont color=quot#c41230quotgt不基于比较lt/fontgtlt/bgt，ltbgt稳定lt/bgt算法
最高位优先MSD
最低位优先LSD
基于关键字各位的大小进行排序，分为
采用“分配”与“收集”策略
对ltbgtnlt/bgt个数据进行基数排序，每个数据基数为nbspltbgtrlt/bgt，有ltbgtdlt/bgt位数字
一趟分配和收集用时ltbgtn+rlt/bgt（分配用ltbgtnlt/bgt，收集用nbspltbgtrlt/bgt），共需ltbgtnlt/bgt趟
辅助空间用到nbspltbgtrnbsplt/bgt个队列
特点
ltbgt基数排序lt/bgt
排序
ltbgtltfont color=quot#c41230quotgt线性结构、集合、树状结构、图状结构lt/fontgtlt/bgt（后三种为非线性结构）
逻辑结构
ltbgtltfont color=quot#c41230quotgt顺序存储、链式存储、索引存储、散列存储/哈希存储lt/fontgtlt/bgt
存储结构/物理结构
数据的运算
ltbgt数据结构的内容lt/bgt
三元组：ltbgt数据对象、数据关系、基本操作lt/bgt
ltbgt抽象数据类型（例如：栈）的表示lt/bgt
ltfont color=quot#c41230quotgtltbgtO(1)＞O(log₂n)＞O(n)＞O(nlog₂n)＞O(n²)＞O(n³)＞O(n!)＞O(nⁿ)lt/bgtlt/fontgt
ltbgt时间复杂度和空间复杂度lt/bgt
ltbgt绪论lt/bgt
用一组连续存储单元依次存储线性表的数据元素
插入nbspnbsp平均移动次数：ltbgtltfont color=quot#c41230quotgtn/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，需要移动元素
删除nbsp nbsp平均移动次数：ltbgtltfont color=quot#c41230quotgt(n-1)/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，需要移动元素
按值查找nbsp nbsp平均移动次数：ltbgtltfont color=quot#c41230quotgt(n+1)/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，顺序访问
按位查找nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(1)lt/fontgtlt/bgt，随机访问
基本操作
ltbgt顺序表lt/bgt
线性表的链式存储
建立单链表：ltbgtltfont color=quot#c41230quotgt头插法lt/fontgtlt/bgt(头结点之后)、ltbgtltfont color=quot#c41230quotgt尾插法lt/fontgtlt/bgt(尾结点之后)
删除nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，不需要移动元素
查找nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，不需要移动元素，顺序访问
ltbgt单链表lt/bgt
尾结点指向下一个节点的指针不是NULL，而是头结点
若常做操作在表头表尾，可对循环链表不设头指针而仅设尾指针，提高效率
ltbgt循环链表lt/bgt
在单链表的机车上增加一个指向前驱结点的指针
ltbgt双向链表lt/bgt
借用数组来描述链表(非顺序存储)
ltbgt静态链表lt/bgt
ltbgt链表lt/bgt
ltbgt线性表lt/bgt
后进先出的线性表，抽象数据结构
栈的顺序存储(类似顺序表)，插入删除操作均在表尾
优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢
共享栈：栈底在共享空间两端，栈顶向空间中部延伸
用不带头节点的单链表实现，指针指向栈顶，所有操作均在栈顶完成
ltbgt栈的链式存储lt/bgt
ltbgt合法出栈个数：C(上标2n 下标n)/(n+1)lt/bgtnbsp
左括号则入栈
右括号，若匹配则弹出栈顶，不匹配则序列非法
遍历完毕，若栈非空则序列非法
ltfont color=quot#0076b3quotgtltbgt括号匹配lt/bgtlt/fontgt
中缀表达式转化为后缀/前缀表达式
1.按优先级对所有运算单位加括号
前缀：把运算符移到对应括号前
后缀：把运算符移到对应括号后
2.
3.去掉括号
简便做法
ltbgtltfont color=quot#0076b3quotgt表达式求值lt/fontgtlt/bgt
ltfont color=quot#0076b3quot style=quotquotgtltbgt递归转化为非递归常使用栈来完成lt/bgtlt/fontgt
ltbgt栈nbsplt/bgt
先进先出的线性表，队头删除队尾插入，抽象数据结构，
队列的顺序存储，两个指针分别指向队头队尾
队列的链式存储，两个指针分别指向头结点和尾结点
ltbgt队列长度：ltfont color=quot#c41230quotgt(Q.rear+MaxSize-Q.front)%MaxSizelt/fontgtlt/bgt
空:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rearlt/fontgtlt/bgt
满:ltbgtltfont color=quot#c41230quotgtQ.front==(Q.rear+1)%MaxSizelt/fontgtlt/bgt
牺牲一个存储单元nbsp nbspltbgtltfont color=quot#c41230quotgtnbspnbsplt/fontgtlt/bgtltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt
空:ltbgtltfont color=quot#c41230quotgtQ.size==0nbspnbsplt/fontgtlt/bgt
满:ltfont color=quot#c41230quotgtltbgtQ.size==MaxSizelt/bgtlt/fontgt
增加记录个数的变量(Q.size)nbsp nbspltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt
空:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rear tag==0nbspnbsplt/fontgtlt/bgt
满:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rear tag==1lt/fontgtlt/bgt
增加tag标识nbsp nbspltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt
ltbgt判空/满lt/bgt
ltbgt循环队列lt/bgt
ltbgt应用：lt/bgtltfont color=quot#0076b3quot style=quotfont-weight: boldquotgt树的层次遍历一般利用队列完成lt/fontgt
ltbgt队列lt/bgt
逻辑结构。线性表的推广，每个元素受到n个线性关系的约束
存储结构：多用顺序存储
目标：节约存储空间；方法：不存储0，多值相同存储一个
需ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtlt/bgt个单元空间
元素aij与他的存储位置sa[k]的关系
ltbgtltfont color=quot#c41230quotgti(i-1)/2+j-1lt/fontgtlt/bgtnbsp ltbgt当i≥jlt/bgt
ltbgtltfont color=quot#c41230quotgtj(j-1)/2+i-1lt/fontgtlt/bgtnbsp ltbgt当i＜jlt/bgt
ltbgtk=lt/bgt
ltbgt对称矩阵lt/bgt
需ltbgtltfont color=quot#c41230quotgtn(n+1)/2+1lt/fontgtlt/bgt个单元空间
ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtnbsp 当i＞jlt/bgt
ltbgtltfont color=quot#c41230quotgt(i-1)(2n-i+2)/2+j-ilt/fontgtnbsp 当i≤jlt/bgt
ltbgt上三角区，k=lt/bgt
ltbgtltfont color=quot#c41230quotgti(i-1)/2+j-ilt/fontgtnbsp 当i≥jlt/bgt
ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtnbsp 当i＜jlt/bgt
ltbgt下三角区，k=lt/bgt
ltbgt三角矩阵lt/bgt
中心地带宽为d，非0元素(2d+1)*n-(1+d)*d个
元素aij与他的存储位置sa[k]的关系 ltbgtltfont color=quot#c41230quotgtk=2i+j-3lt/fontgtlt/bgt
ltbgt对角矩阵lt/bgt
利用三元组(行标，列标，值)存储
稀疏矩阵压缩后，失去了随机存取的特性
ltbgt稀疏矩阵lt/bgt
ltbgt应用：ltfont color=quot#0076b3quotgt特殊矩阵的压缩存储lt/fontgtlt/bgt
ltbgt数组lt/bgt
ltbgt栈、队列、数组lt/bgt
度：该结点的子结点个数，树中最大的度称为树的度
高/深度：叶子结点向上数为高度，根节点向下数为深度，最大高/深度为树的高/深度
有/无序树：树中结点的各子树从左向右是否有序
概念
ltbgtnlt/bgt个结点的树，只有ltbgtn-1lt/bgt条边
结点数=所有结点的度+1
度为ltbgtmlt/bgt的树中第ltbgtilt/bgt层上至多有ltbgtmⁱ⁻¹lt/bgt个结点(i≥1)
ltbgtnlt/bgt个结点的ltbgtmlt/bgt叉树最小高度为ltbgtlogₘ(n(m-1))+1lt/bgt（取上界）
结点为nbspltbgtltfont color=quot#c41230quotgtilt/fontgtlt/bgt，双亲ltbgtltfont color=quot#c41230quotgt[i/2]lt/fontgtlt/bgt(取下界)，左孩子ltbgtltfont color=quot#c41230quotgt2ilt/fontgtlt/bgt，右孩子ltbgtltfont color=quot#c41230quotgt2i+1lt/fontgtlt/bgt
性质
ltbgt树lt/bgt
ltbgt满二叉树lt/bgt：深度为ltbgtnlt/bgt，有ltbgtltfont color=quot#c41230quotgt2ⁿ-1lt/fontgtlt/bgt个结点
ltbgt完全二叉树lt/bgt：n个结点的完全二叉树中结点在对应满二叉树中编号1-n
二叉树第ltbgt i lt/bgt层上至多有nbspltfont color=quot#c41230quot style=quotfont-weight: boldquotgt2ⁱ⁻¹ lt/fontgtltfont color=quot#000000quot style=quotquotgt个结点lt/fontgt
深度为ltbgtnlt/bgt的二叉树至多有ltbgtltfont color=quot#c41230quotgt 2ⁿ-1 lt/fontgtlt/bgt个结点
非空二叉树叶子结点数等于度为ltbgtltfont color=quot#c41230quotgt2lt/fontgtlt/bgt的节点数ltbgtltfont color=quot#c41230quotgt+1lt/fontgtlt/bgt
深度为ltbgtltfont color=quot#c41230quotgt log₂(n+1)lt/fontgtlt/bgt(取上界)
ltbgtinbsplt/bgt的双亲是ltbgti/2lt/bgt(取下界)
ltbgtilt/bgt 的左孩子是ltbgt2ilt/bgt，若2igtn，则无左孩子
ltbgti lt/bgt的右孩子是ltbgt2i+1lt/bgt，若2i+1gtn则无右孩子
ltbgtnlt/bgt个结点的完全二叉树ltfont color=quot#000000quotgtlt/fontgt
顺序存储：用数组把编号 i 的结点存放在 i-1 处，适用于存储完全二叉树
用二叉链表存储ltbgtnlt/bgt个结点的二叉树，共有ltbgtn+1lt/bgt个ltbgt空指针域lt/bgt
用三叉链表存储n个结点的二叉树，共有n+2个空指针域
链式存储(二叉链表)
存储结构
方法：从上至下、从左至右、利用队列
将根放入队列，若队列不空则取队头元素p
若p不空则访问，将其左右子树入列
循环直至队空
思路
ltbgt层次遍历lt/bgt
ltbgt先序遍历：根-左-右lt/bgt
ltbgt中序遍历：左-根-右lt/bgt
ltbgt后序遍历：左-右-根lt/bgt
先序/后序/层次+中序，可以确定ltbgt唯一二叉树，lt/bgt先序+后序不唯一
二叉树的遍历
线索：利用空指针指向前驱或后继结点
ltbgtlchild ltfont color=quot#f15a23quotgt|lt/fontgt LTag ltfont color=quot#c41230quotgt|lt/fontgt data ltfont color=quot#c41230quotgt|lt/fontgt RTag ltfont color=quot#c41230quotgt| lt/fontgtrchildlt/bgt
ltbgt0nbsplt/bgt lchild/rchild域指向左/右孩子
ltbgt1lt/bgtnbsp lchild/rchild域指向前驱/后继
LTag/RTag=
画线索二叉树：先写遍历序列，再画线索
ltbgt线索二叉树lt/bgt
特点：左小右大
判别：中序遍历得到结果从小到大有序
与根比较大小，大则去右子树，小则去左子树
平均查找长度：ltbgtltfont color=quot#c41230quotgt(n+1)/2lt/fontgtlt/bgt
ltbgt查找lt/bgt
ltbgt插入lt/bgt：先查找，无插入节点再将其插入最后访问节点的ltbgtltfont color=quot#c41230quotgt孩子nbsplt/fontgtlt/bgt
如果是叶子结点，直接删除
如果左子树或者右子树为空：将左子树接到双亲上
如果左右子树都不空：借左子树最大节点替换被删除节点
ltbgt删除lt/bgt
ltbgt二叉排序树lt/bgt
平衡因子BF为该节点的左子树深度减去右子树深度
平衡二叉树的平衡因子只有1、0、-1
右单旋：左子树的左子树多1
左单旋：右子树的右子树多1
先左后右：左子树的右子树多1
先右后左：右子树的左子树多1
ltbgt平衡化lt/bgt
构造平衡二叉树
平均查找长度：ltbgtltfont color=quot#c41230quotgtO(log₂n)lt/fontgtlt/bgt
ltbgtltfont color=quot#c41230quotgt0lt/fontgtlt/bgt，h=0
ltbgtltfont color=quot#c41230quotgt1lt/fontgtlt/bgt，h=1
ltbgtltfont color=quot#c41230quotgtNₕ₋₁+Nₕ₋₂+1lt/fontgtlt/bgt，h≥2
n个结点的平衡二叉树的最少结点，ltbgtNₕ=lt/bgt
ltbgt平衡二叉树lt/bgt
ltbgt二叉树lt/bgt
数组指向双亲结点
找双亲快。但找孩子慢
双亲表示法
数组指向孩子结点
找孩子快。但找双亲慢
孩子表示法
便于转换为二叉树，找孩子快。但找双亲慢
孩子兄弟表示法
ltbgt树的存储结构lt/bgt
树转化为二叉树，根节点没有右孩子
森林转化为二叉树，森林的第一棵树的根作为对应二叉树的根
先序遍历
中序遍历
后序遍历
森林的遍历
ltbgt树、二叉树与森林的转化lt/bgt
一类带权路径长度最短的树
方法：每次取两个最小的树组成二叉树
结果不唯一，但带权路径长度都是最小的
ltbgt哈弗曼树(编码)lt/bgt
ltbgtltfont color=quot#000000quotgt应用lt/fontgtlt/bgt
ltbgt树与二叉树lt/bgt
考研数据结构知识框架笔记
0 条评论
回复 删除
下一页
