首页  思维导图  详情



 



树与二叉树考研

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; //结点是否为空 }；

链式储存

n个结点 n-1个指针域有n+1个空链域【可以构造线索二叉树】

三叉链表增加父节点指针方便寻找父节点

线索二叉树【方便寻找前驱和后继】

n个结点  有n+1个空链域

线索化

中序线索二叉树线索→ 中序前驱和中序后继

中序线索化的实现

中序线索二叉树找中序后继

中序线索二叉树找中序前驱

先序线索二叉树  线索 → 先序前驱和先序后继

先序线索化的实现 当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必然都是最小值

哈夫曼编码

每个字符作为一个叶子结点  各个字符出现的频度作为结点的权值

用于数据压缩

章节技巧

度m的树和m叉树区别

易错点

二叉树线索化的实现中最后一个结点的rchild和rtag的处理

 Collect

Get Started

考研树与二叉树知识点笔记总结

 Collect

Get Started

二叉树

 Collect

Get Started

二叉树

 Collect

Get Started

平衡二叉树





0 条评论

下一页