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