树与二叉树考研
2020-07-07 13:38:43 0 举报AI智能生成
树与二叉树_计算机数据结构考研
作者其他创作
大纲/内容
版权∈ 本人所有
严禁擅自转载和商用 受法律保护
严禁擅自转载和商用 受法律保护
更新记录
2020.5.19 开坑
树
基本概念
除了根节点 任意结点有且只有一个前驱
深度
结点的层次 上往下数
结点的高度
下往上数
树的高度/深度
总共多少层
结点的度
有几个分支
叶子结点 =0
非叶子结点 ≠0
树的度
各结点的度最大值
森林
m棵互不相交的树的集合
公式性质
结点数 = 结点总度数【树的分支】 +1【根节点】
高度为h的m叉树
至多由 m^h-1/m-1 个结点
至少有h个结点
高度为h 度为m的树
至少有h+m-1个结点
高度最小即 所有结点都有m个孩子
存储结构
顺序存储
双亲表示法 双亲的"指针" int型变量并非真指针
顺序+链式存储
孩子表示法
链式存储
孩子兄弟表示法 左孩子右兄弟 树和二叉树的转换
树、森林的遍历
树的遍历
先根遍历
后根遍历
层次遍历
森林的遍历
先序遍历 可先转换为二叉树 或 依次单独看成一个树递归遍历
中序遍历 可先转换为二叉树 或 依次单独看成一个树递归遍历
应用
文件系统
二叉树
基本概念
就是m叉树
在m叉树的情形下， 结点i的第一个子女编号为j=（i-1）*m+2
特殊二叉树
满二叉树
完全二叉树
在满二叉树基础上去掉若干编号更大结点
在满二叉树基础上去掉若干编号更大结点
二叉排序树
平衡二叉树
公式性质
二叉树
叶子结点比二分支结点多一个
高度为h
二叉树至少有2^h-1结点【满二叉树】
m叉树至多有m^h-1/m-1个结点
完全二叉树
n个结点的高度h为 log2(n+1) 或 log2n+1
结点n 得到度为0的n0 度为1的n1 度为2的n2
储存结构
顺序存储
#define MaxSize 100
struct TreeNode{
ElemType vlue；//结点中的数据元素
bool isEmpty; //结点是否为空
}；
struct TreeNode{
ElemType vlue；//结点中的数据元素
bool isEmpty; //结点是否为空
}；
链式储存
n个结点 n-1个指针域 有n+1个空链域【可以构造线索二叉树】
三叉链表 增加父节点指针 方便寻找父节点
线索二叉树【方便寻找前驱和后继】
n个结点 有n+1个空链域
线索化
中序线索二叉树 线索→ 中序前驱和中序后继
中序线索化的实现
中序线索二叉树找中序后继
中序线索二叉树找中序前驱
先序线索二叉树 线索 → 先序前驱和先序后继
先序线索化的实现
当Ltag==0时 才能对左子树先序线索化
当Ltag==0时 才能对左子树先序线索化
找先序后继
后序线索二叉树 线索 → 后序前驱和后序后继
后序线索化的实现
遍历算法
先序遍历
根左右 前缀表达式
同一个先序遍历可以对应多种二叉树形态
同一个先序遍历可以对应多种二叉树形态
中序遍历
左根右 中缀表达式 需要加()
同一个中序遍历可以对应多种二叉树形态
同一个中序遍历可以对应多种二叉树形态
后序遍历
左右根 后缀表达式
同一个后序遍历可以对应多种二叉树形态
同一个后序遍历可以对应多种二叉树形态
层序遍历
确定唯一形态的二叉树
仅先/中/后序遍历无法确定一颗二叉树
先序+中序
后序+中序
层序+中序
应用
二叉排序树
定义
左子树 结点上的值 ＜ 根 结点上的值 ＜ 右子树 结点上的值
基本操作
查找操作
插入操作
删除操作
构造操作
不同关键字序列可能得到同款或不同款二叉排序树
不同关键字序列可能得到同款或不同款二叉排序树
查找效率分析
平均查找长度ASL
查找成功
查找失败
最好情况
最小高度为log2n+1 → 时间复杂度 O(log2n)
平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过1
最坏情况
树高为结点数n → O(n)
平衡二叉树AVL
定义
任一结点的左子树和右子树的深度之差不超过1
结点的平衡因子 = 左子树高度 - 右子树高度
0 -1 1 才是平衡二叉树
插入新结点的“不平衡”处理
调整第一个不平衡结点 即 最小不平衡子树
左孩子用右旋操作 右孩子用左旋操作
LL 【在A的左孩子的左子树中插入】
RR 【在A的右孩子的右子树中插入】
代码思路
LR 【在A的左孩子的右子树中插入】
RL 【在A的右孩子的左子树中插入】
查找效率分析
树高为h 查找最多比较h次
哈夫曼树 /最优二叉树
定义
结点的权
某结点上的值
结点的带权路径长度
从树根出发 各权的相乘
树的带权路径长度WPL
树中所有叶结点的带权路径长度之和
含有n个带权叶结点的二叉树 WPL最小的二叉树即为哈夫曼树
哈夫曼树构造
不唯一 但WPL必然都是最小值
不唯一 但WPL必然都是最小值
哈夫曼编码
每个字符作为一个叶子结点 各个字符出现的频度作为结点的权值
用于数据压缩
章节技巧
度m的树和m叉树区别
易错点
二叉树线索化的实现中 最后一个结点的rchild和rtag的处理
0 条评论
下一页
