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