DS-5-树
2021-08-01 14:38:55 0 举报AI智能生成
登录查看完整内容
数据结构第五章-树 知识点整理
作者其他创作
大纲/内容
ie. 叶子结点比二分支结点多一个
n0=n2+1
总结点数
n=n0+n1+n2
结点数=总度数+1
n=n1+2n2+1
二叉树第i层最多有2^(i-1)个结点
m叉树第i层最多有m^(i-1)个结点
高度为h的二叉树至多有2^h-1个结点（满二叉树取等）
高度为h的m叉树至多有(m^h-1)/(m-1)个结点（满m叉树取等）
考点
常见性质和考点
度=2; 不存在度=1的点
只有最后一层存在叶子结点
按层序从1开始编号，结点的左孩子为2i，右孩子为2i+1，父结点为i/2或(i-1)/2 (如果有)
外框
满二叉树
最后一层不满，且只有最右侧的结点缺失
定义
存在的结点与满二叉树编号一一对应
只有最后两层可能有叶子
最多一个度=1的结点
i≤floor(n/2)为分支结点，i>floor[n/2]为叶子结点
特性
具有n个结点的完全二叉树高度h=ceil(log2(n+1))或floor(log2(n))+1
n0=n2+1→n0+n2是奇数
完全二叉树
左子树关键字<根结点<右子树关键字
每个子树都是二叉排序数
对BST中序遍历得到递增序列
定义和特性
搜索=小于根结点→左子树，大于根结点→右子树，叶子结点仍不匹配→失败
空间复杂度：O(h) (最差O(n))
比较关键字的次数，反映时间复杂度
所有查找路径的平均
ASL平均查找长度
注意查找成功和失败时ASL不同要补充失败的结点
查找长度
效率分析
查
不同的序列构造不同的二叉排序树
构造
直接插入
目标树是空树
小于根结点？插入到左子树：插入到右子树
注意是插入到树而不是插入。
目标树非空
所以必然会被插到叶子结点
插入
增
直接删
叶子
用左右子树代替当前结点
只有左右子树
在左子树中找最大结点替代当前树结点
在右子树中找最小结点替代当前树结点
有左右子树
删
方法
二叉排序树BST
任何结点的左右子树深度差不超过1
数据域
左子树深度-右子树深度
平衡因子
左右子树（ptr）
结点结构
以之为根结点的树称最小不平衡子树
从插入点向上找到第一个不平衡结点
LL
RR
LR
RL
插入点分析(插入到哪个孩子的哪个子树？)
以LL为例 (RR对称)最小不平衡子树的：左子树根结点→新根结点原根结点→新右子树原左子树的右子树→新右子树的左子树插入节点→新左子树
以LR为例 (RL对称)最小不平衡子树的：左旋转：LRL→LLR，LL→LLL，LR→L，LRR→LR右旋转(基于上一步结果)：L→Root，Root→R，LR→RL，R→RR
调整(再平衡)
span class=\"equation-text\" data-index=\"0\" data-equation=\
设为深度h的AVL树中最少的节点数
ie. 最坏的情况下，含结点的AVL树不超过层，参见上式
另有
参照BST，然后再平衡
平衡二叉树AVL高性能二叉排序树总高度尽量低
根到该结点的路径边数
路径
结点的权
只计算叶子结点
WPL最小的树就是哈夫曼树
带权路径长度
带权路径长度：该结点权路径长度
将给定结点每个都视为一棵树，组成森林F
用其中权值最小的两个结点构造一颗新树T，T根结点的权值设为其权值和
用T的根结点替代之前的两个结点
重复操作直到F中只有一棵树T
操作
结点总数，合并次数
不存在度=1的点
不唯一，WPL最小且相同均为最优
性质
降低内容编码的总长度，字符出现频率越高编码越短
没有任何一个编码是另一个编码的前缀
均为树的叶子结点
编码均为前缀编码，最终编码不存在歧义，可以自分割
应用：数据压缩
应用：哈夫曼编码(可变长度编码)
哈夫曼树(最优二叉树)
红黑树
特殊的二叉树
如果不是完全二叉树，紧密的链式存储将失去根据结点编号确定逻辑结构的性质
必须按照完全二叉树的编号顺序进行存储，对于非完全二叉树的存储，浪费大量空间，且降低性能
顺序存储
非完全二叉树总会存在一部分空指针域，可以用来构造线索二叉树
链式存储二叉链表
存储结构
先中后指的是对当前结点的访问与访问两孩子的先后关系
时间复杂度：O(n)空间复杂度：O(h) (最坏O(n))
应用：存储并输出算数表达式的前/中/后缀表达式注意：中序遍历记得加括号
应用：求树的深度
先/中/后序遍历
队列非空？对首结点出队，访问，其孩子入队(如有)：结束
队列法
层次遍历层序遍历
遍历
给定一种遍历方式和其遍历序列不能唯一确定二叉树
前序列：Root-lChild-rChild→第一个肯定是根结点中序列：lChild-Root-rChild
由前序列可推出根节点，从而可推出lC与rC，其在两序列中长度相同
递归得到子序列的结构
前+中
后+中
层序列：Root-lChildRoot-rChildRoot→第一个肯定是根结点中序列：lChild-Root-rChild
由前序列可推出根结点 ，左子树根，右子树根，从而可推出lC与rC
层+中
其他序列组合不能唯一确定
给定特定两种遍历方式和其遍历序列可以唯一确定二叉树
根据遍历序列构建二叉树
具有n个结点的二叉树具有n+1个空指针域
没有前驱线索，除非三叉链表(有父结点指针)
先序线索二叉树
中序线索二叉树
没有后继线索，除非三叉链表(有父结点指针)
后续线索二叉树
所谓线索，是指向遍历序列的前后继的指针。因此，有三种遍历序列，就有三种线索二叉树
分别称为前驱线索(ptr)和后继线索(ptr)，不存在前后就是nullptr
额外用ltag和rtag表示lChild和rChild是否是线索
考察方式：画出
创建线索二叉树
二叉树
某一结点的子结点的数量
结点总数=Σ度+1
度
从1开始计数。根结点是第一层
层
深度
成员
基本概念
先后指的是对当前结点的访问与访问孩子的先后关系
对多个孩子的情况，需要循环判定是否遍历完了所有孩子
先/后根遍历
树的遍历
访问森林中第一棵树的根结点
先序遍历该树
先序遍历其余的树构成的森林
对森林的先序遍历等价于将森林转化为二叉树之后的对该树的先序遍历
先序遍历
中序遍历第一棵树
访问该树的根结点
中序遍历其余的树构成的森林
中序遍历
森林的遍历
保存一个指向父结点序号的值，用-1表示该结点为根结点
要删除所有指向该结点的结点，参见“查”
改
极不方便
双亲表示法(顺序存储)
保存一个子结点序号，再保存下一个孩子的指针。
孩子表示法(顺序+链式存储)
左指针指向孩子，右指针指向右兄弟
应用：树↔二叉树 转化
应用：森林↔二叉树 转化把不同的树的根结点看成兄弟
孩子兄弟表示法(链式存储)
森林转化的二叉树根结点有两个子树，树转化的二叉树根结点只有左子树
树
职业：暂无
0 条评论
回复 删除
下一页
