王道数据结构第五章树与二叉树_思维导图模板

树与二叉树，，

树

基本概念

结点，根节点，分支结点，叶子结点，边，子树

空树：节点数为0的树

非空树的特性

有且仅有一个根节点

没有后继的结点称为叶子结点

有后继的结点称为分支结点

除了根节点外，任何一个结点都有且仅有一个前驱

树是一种递归定义的数据结构

基本术语

结点之间的关系描述

祖先结点/子孙结点

双亲结点（父节点）/孩子结点

兄弟结点/堂兄弟结点

两个节点之间的路径：只能从上往下

路径长度：路径上经过几条边

树的路径长度：从树根到每个结点的路径长度的总和

结点、树的属性描述

结点的层次（深度）：从上往下数

结点的高度：从下往上数

树的高度（深度）：总共多少层

结点的度：有几个孩子（分支）

非叶子节点的度>0

叶子结点的度=0

树的度：树中各结点的度的最大值

有序树，无序树

有序树：逻辑上看，树中节点的各子树从左至右是有次序的，不能互换

无序树：逻辑上看，树中节点的各子树从左至右是无次序的，可以互换

森林

森林是m（m≥0）棵互不相交的树的集合

树的常考性质

考点1

结点数=总度数+1

考点2

度为m的树

任意结点的度 ≤ m（最多m个孩子）

至少有一个结点度=m

一定是非空树

m叉树

任意结点的度 ≤ m（最多m个孩子）

允许所有结点的度都

可以是空树

考点3

度为m的树第i层至多有个结点（i ≥ 1）

m叉树的第i层至多有个结点（i ≥ 1）

考点4

高度为h的m叉树至多有个结点

高度为h的m叉树至少有h个结点

高度为h度为m的树至少有h+m-1个结点

考点5

具有n个结点的m叉树的最小高度为

树的存储结构

双亲表示法

每个结点中保存指向双亲的“指针”

根节点存储在0，-1表示没有双亲

新增数据元素无需按逻辑上的次序存储

优点：查指定结点的双亲很方便

缺点：查指定结点的孩子只能从头遍历

孩子表示法

顺序+链式存储

指针指向第一个孩子

优点︰找孩子方便

缺点:找父节点不方便

孩子兄弟表示法

用二叉链表存储树--左孩子右兄弟

孩子兄弟表示法存储的树，从存储视角来看形态上和二叉树类似

考点:树与二叉树的相互转换。本质就是用孩子兄弟表示法存储树

重要考点：树、森林与二叉树的转换

本质:用二叉链表存储森林--左孩子右兄弟

森林中各个树的根节点之间视为兄弟关系

树和森林的遍历

树的遍历

先根遍历

先根，后子树

树的先根遍历序列与这棵树相应二叉树的先序序列相同

后根遍历

先子树，后根

树的后根遍历序列与这棵树相应二叉树的中序序列相同

层序遍历（用队列实现）

广度优先遍历

深度优先遍历

森林的遍历

先序遍历

若森林为非空，则按如下规则进行遍历：
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历

中序遍历

若森林为非空，则按如下规则进行遍历：
中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行后根遍历

二叉树

基本概念

二叉树是n(n≥0)个结点的有限集合

或者为空二叉树，即n=0

或者由一个根结点和两个互不相交的被称作根的左子树和右子树组成。

特点

每个结点至多只有两棵子树

左右子树不能颠倒（二叉树是有序树）

二叉树是递归定义的数据结构

树转化为二叉树：左孩子，右兄弟

几种特殊的二叉树

满二叉树

一棵高度为h，且含有个结点的二叉树

特点

只有最后一层有叶子结点

不存在度为1的结点

按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为i/2（如果存在的话）

完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1-n的结点一一对应，称为完全二叉树

特点

只有最后两层可能有叶子结点

最多只有一个度为1的结点

按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为[i/2]（如果存在的话）

i≤n/2为分支结点，i≥n/2为叶子结点

如果某个节点只有一个孩子，那这个孩子一定是左孩子

二叉排序树

左子树上所有结点的关键字均小于根节点的关键字；右节点上所有结点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树。

用于元素的排序，搜索

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1

平衡二叉树能有更高的搜索效率

常见考点

考点1

设非空二叉树中度为0、1和2的结点个数分别为,和，则（叶子结点比二分支结点多一个）

考点2

二叉树第i层至多有个结点（i≥1）

考点3

高度为h的二叉树至多有个结点（满二叉树）

考点4

具有n个（n＞0）个结点的完全二叉树的高度h为[]或[]+1

编号为i的结点所在层次为[]或[]+1

考点5

对于完全二叉树，可以由结点数推出度为0，1和2的结点个数为,和

二叉树的存储结构

顺序存储

只适合存储完全二叉树

链式存储

n个结点的二叉链表共有n+1个空链域

二叉树的遍历

按照某种次序把所有节点都访问一遍

先序遍历

根左右

得到前缀表达式

中序遍历

左根右

得到中缀表达式（未加界限符）

后序遍历

左右根

得到后缀表达式

考点：求遍历序列

分支结点逐层展开法

从你的全世界路过法

先序——第一次路过时访问

中序——第二次路过时访问

后序——第三次路过时访问

脑补空结点，从根节点出发，画一条路：
如果左边还有没走的路，优先往左边走
走到路的尽头（空结点）就往回走
如果左边没路了，就往右边走
如果左、右都没路了，则往上面走

求树的深度

层次遍历

算法思想

初始化一个辅助队列

根节点入队

若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾（如果有的话）

重复上一步直至队列为空

由遍历序列构造二叉树

若只给出一个二叉树的前/中/后/层序遍历队列中的一种，不能唯一确定一棵二叉树

前序+中序遍历队列

后序+中序遍历队列

层序+中序遍历队列

前序、后序、层序
序列的两两组合无法唯一
确定一棵二叉树

时间复杂度O(n)

线索二叉树

线索二叉树的作用

方便从一个指定结点出发，找到其前驱、后继；方便遍历

线索二叉树的存储结构

三种线索二叉树

先序线索二叉树——线索指向
先序前驱、先序后继

中序线索二叉树——线索指向
中序前驱、中序后继

后序线索二叉树——线索指向
后序前驱、后序后继

几个概念

线索

指向前驱/后继的指针称为线索

中序前驱/中序后继;先序前驱/先序后继;后序前驱/后序后继

手算画出线索二叉树

①确定线索二叉树类型——中序、先序、or后序?

②按照对应遍历规则，确定各个结点的访问顺序，并写上编号

③将n+1个空链域连上前驱、后继

二叉树的线索化

中序线索化-得到中序线索二叉树

先序线索化-得到先序线索二叉树

后序线索化-得到后序线索二叉树

核心

中序/先序/后序遍历算法的改造，当访问一个结点时，连接该结点与前驱结点的线索信息

用一个指针pre记录当前访问结点的前驱结点

易错点

最后一个结点的rchild . rtag的处理

先序线索化中，注意处理爱滴魔力转圈圈问题，当ltag==0时，才能对左子树先序线索化

找前驱，找后继

中序线索二叉树

前驱

p的左子树中最右下结点

后继

p的右子树中最左下结点

先序线索二叉树

前驱

①如果能找到p的父节点，且p是左孩子，则p的父节点为其前驱

②如果能找到p的父节点，且p是右孩子，其左兄弟为空，则p的父节点即为其前驱

③如果能找到p的父节点，且p是右孩子，其左兄弟非空，则p的前驱为其左兄弟子树最后一个被先序遍历的结点

④如果p是根节点，则p没有先序前驱

后驱

①若p有左孩子，则先序后继为左孩子

②若p没有左孩子，则先序后继为右孩子

后序线索二叉树

后继

①如果能找到p的父节点，且p是右孩子，p的父节点即为其后继

②如果能找到p 的父节点，且p是左孩子，其右兄弟为空，p的父节点即为其后继

③如果能找到p 的父节点，且p是左孩子，其右兄弟非空，则p的后继为其右兄弟子树中第一个被后序遍历的结点

④如果p是根节点，则p没有后序后继

前驱

①若p有右孩子，则后序前驱为右孩子

②回若p没有右孩子，则后序前驱为左孩子

二叉树在线索化之后，仍不能有效求解的问题：后续线索二叉树中求后序后继，仍需要栈的支持

哈夫曼树

带权路径长度

结点的权:某种特定含义的数值

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和

哈夫曼树（最优二叉树）的定义

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

哈夫曼树的构造

每次选两个根节点权值最小的树合并，并将二者权值之和作为新的根节点的权值

哈夫曼树的特点

每个初始结点最终都成叶结点，且权值最小的结点到根节点的路径长度越长

哈夫曼树的结点总数为2n-1（n为叶结点数，也为初始结点数）

哈夫曼树中不存在度为1的结点

哈夫曼树不唯一，但WPL必然相同且为最优

哈夫曼编码

固定长度编码——每个字符用相等长度的二进制位表示

可变长度编码——允许对不同字符用不等长的二进制位表示

前缀编码——没有一个编码是另一个编码的前缀

将字符频次作为字符结点权值，构造哈夫曼树，按照左0右1构造编码，即可得哈夫曼编码，可用于数据压缩

并查集

如何表示集合关系

算法思想

将各个元素划分为若干个互不相交的子集

把同一个集合里的元素组织成一棵树

如何查一个元素到底属于哪个集合？

从指定元素出发，一路向北，找到根节点

如何判断两个元素是否属于同一个集合？

对比两个元素的根节点是否相同

如何把两个集合并为一个集合？

让一棵树成为另一棵树的子树

并查集的代码实现

双亲表示法

初始化

初始化并查集，将所有数组元素初始化为-1

Find(S[],x)

查，找到元素x所属集合

时间复杂度O(n)

Union(S[],root1,root2)

并，将两个集合并为一个集合

时间复杂度O(1)

并查集的优化

用根节点的绝对值表示一棵树（集合）的结点总数

Union操作合并两棵树时，小树并到大树

优化后，Find操作的时间复杂度优化为O()

并查集的进一步优化

优化Find

压缩路径

每次Find操作先找到x所属根节点，再将查找路径上的所有结点都直接挂在根结点下面

关联

王道数据结构第五章树与二叉树

模板简介

猜你喜欢

相关文章

王道 数据结构 第五章 树与二叉树

模板简介

猜你喜欢

相关文章

王道数据结构第五章树与二叉树