夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 397 页PDF · 5.2MB
下载

文档在线预览

公开展示前 10 页
100%
1
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《005-第五讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 397 页 剩余 387 页未展示,请下载后查阅

下载

文档文本内容

第五讲:树和二叉树
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集CON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架考点框架
树的引入
树的定义
结点的分类
结点间的关系
树的其他概念考点一: 基本术语
1、树的引入
日常生活中随处可见的树结构。考点一: 基本术语
1、树的引入
一个算术表达式可以用表达式树来表示,并且具有以下两个特点(1)
叶子结点是操作数;(2)分支结点是运算符。
-
表达式:a+ b* (c– d) – e/ f
+ /
进行后序遍历转换为逆波兰式:
a b c d- * + e f/ -
a * e f
b -
c d考点一: 基本术语
1、树的引入
树型结构是一类非常重要的非线性结构。树型结构:
分支关系
一对多
层次结构
A
B C D
E F G H I J
K L M N考点一: 基本术语
2、树的定义
形式化定义(二元组)
树:T={D,R }。D是包含n个结点的有限集合(n≥0)。当n=0时为
空树,否则关系R满足以下条件:
有且仅有一个结点d∈D,它对于关系R来说没有前驱结点,结点
0
d称作树的根结点。
0
除根结点外,每个结点有且仅有一个前驱结点。
D中每个结点可以有零个或多个后继结点。考点一: 基本术语
2、树的定义
树:n(n≥0)个结点的有限集合 ,当 n=0 时,称为空树;任意一棵
非空树 T 满足以下条件:
(1)有且仅有一个特定的称为根的结点;
(2)当 n>1 时,除根结点之外的其余结点被分成 m(m> 0)个互不
相交的有限集合 T,T,… , T ,其中每个集合又是一棵树,并称为这个根
1 2 m
结点的子树。
树的定义是采用递归方法考点一: 基本术语
2、树的定义
互不相交使得树结构具有什么逻辑特征?
A 树与子树之间具有包含关系
B C
树中没有回路
D E F G
树结构具有层次性
H I考点一: 基本术语
2、树的定义
结点:结点不能属于多个子树
互不相交的具体含义是什么?
边:子树之间不能有关系
A A
A
B C B C
B E C
D E F G D F G
D F G
H I
子树相交 有回路考点一: 基本术语
3、结点的分类
• 结点的度:结点所拥有的子树的个数
• 树的度:树中各结点度的最大值
• 叶子结点:度为 0 的结点,也称为终端结点
• 分支结点:度不为 0 的结点,也称为非终端结点考点一: 基本术语
3、结点的分类
结点的度:树中一个结点的子树的个数称为该结点的度。树中各结点的度
的最大值称为树的度,通常将度为m的树称为m次树或者m叉树。
度为3
A
度为2
B C D
E F G H I
3叉树 J K L M考点一: 基本术语
3、结点的分类
度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端
结点或叶结点(或叶子结点)。
度为1的结点称为单分支结点;度为2的结点称为双分支结点,依此类推。
A
双分支
结点
B C D
E F G H I
叶结点
J K L M考点一: 基本术语
A
4、结点的关系
孩子:树中某结点子树的根结点称为这个结点的孩子结点
B C
双亲:这个结点称为它孩子结点的双亲结点
D E F G
兄弟:具有同一个双亲的孩子结点互称为兄弟
a a a a a
1 2 i-1 i n
H I
在线性结构中,逻辑关系表现为前驱——后继
在树结构中,逻辑关系表现为双亲——孩子考点一: 基本术语
4、结点的关系
在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女
结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。
具有同一双亲的孩子结点互为兄弟结点。
A的孩子结点有B、C、D
A
B、C、D的双亲结点为A
B C D
B、C、D的互为兄弟结点
E F G H I
J K L M考点一: 基本术语
4、结点的关系
树中的每个结点都处在一个层次上。结点的层次从树根开始定义,根
结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为
其双亲结点所在的层次加1。
1
A
结
点
2 的
B C D
层
次
3 或
E F G H I
深
度
4
J K L M考点一: 基本术语
4、结点的关系
结点所在层数:根结点的层数为 1;对其余结点,若某结点在第 k 层,则
其孩子结点在第 k+1 层
1
A
结
点
2 的
B C D
层
次
3 或
E F G H I
深
度
4
J K L M考点一: 基本术语
4、结点的关系
树中结点的最大层次称为树的高度(或树的深度)。
1
A
结
点
2 的
B C D
层
次
3 或
E F G H I
深
度
4
J K L M
树的高度为4考点一: 基本术语
4、结点的关系
树的宽度:树中每一层结点个数的最大值
1
A
结
点
2 的
B C D
层
次
3 或
E F G H I
深
度
4
J K L M
树的宽度为5考点一: 基本术语
4、结点的关系
双亲结点在同一层上的所有结点互称为堂兄弟结点。如图中结点E、G、
H、I。(同一层,但是不是兄弟结点)
1
A
结
点
2 的
B C D
层
次
3 或
E F G H I
深
度
4
J K L M考点一: 基本术语
4、结点的关系
两个结点d和d的结点序列(d,d ,…,d)称为路径。其中<d,d>
i j i i1 j x y
是分支。
路径长度等于路径所通过的结点数目减1(即路径上分支数目)。
A
A到K的路径为A,D,I,K,
其长度为3
B C D
E F G H I
J K L M考点一: 基本术语
4、结点的关系
层次路径:从根结点开始,到达某结点p所经过的所有结点成为结点p的层
次路径(有且只有一条)。
A
A到K的层次路径为A,D,I,K,
其长度为3
B C D
E F G H I
J K L M考点一: 基本术语
4、结点的关系
在一棵树中,一个结点的所有子树中的结点称为该结点的子孙结点。
从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。
A
L的祖先结点为A、D、I
所有结点都是A的子孙结点
B C D
E F G H I
J K L M考点一: 基本术语
5、树的其他概念
若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序
是不能随意变换的,则称为有序树,否则称为无序树。
中国
双亲
北京 上海 天津
老大 老二 老三
无序树
有序树
默认为有序树考点一: 基本术语
5、树的其他概念
n(n>0)个互不相交的树的集合称为森林。
把含有多棵子树的树的根结点删去就成了森林。
A
B C D B C D
E F G H I E F G H I
J K L M J K L M考点一: 基本术语
5、树的其他概念
给m(m>1)棵独立的树加上一个结点,并把这m棵树作为该结点
的子树,则森林就变成了一颗树。
A
A
B C D
D
B C
E F G H I
H I
E F G
J K L M
K L M
J考点一: 基本术语
A
a a a a a
1 2 i-1 i n
线性结构 B C
树结构
开始结点(只有一个):无前驱 根结点(只有一个):无双亲
D E F G
终端结点(只有一个):无后继 叶子结点(可以有多个):无孩子
H I
其它元素:一个前驱,一个后继 其它结点:一个双亲,多个孩子
一对一 一对多考点一: 基本术语
树的应用很广泛,在不同的实际应用中,树的基本操作不尽相同
ADT Tree
DataModel
树由一个根结点和若干棵子树构成,树中结点具有层次关系
Operation
InitTree:初始化一棵树
DestroyTree:销毁一棵树
PreOrder:前序遍历树
PostOrder:后序遍历树 简单起见,只讨论树的遍历
LeverOrder:层序遍历树
endADTTHANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架考点框架
树的性质
树的存储
树的遍历考点二:树的性质和存储
1、树的性质
性质1: 树中的结点数等于所有结点的度数之和加1。
 树中每个分支计为一个结点的度(每条分支线从一个结点引出来的)
 所有结点的度之和=分支数
A
B C D
分支数=12
结点的度之和=12
E F G H I
J K L M考点二:树的性质和存储
1、树的性质
 除了根结点,每条分支线都指向一个结点。给根结点加上一个分支:
A
A
B C D
B C D
E F G H I
E F G H I
J K L M
J K L M
这样分支数与结点数相同
 实际分支数 = n-1 n=度之和+1考点二:树的性质和存储
1、树的性质
性质2: 度为m的树中第i层上至多有mi-1个结点(i≥1)。
度为3的树第2层至多有3个结点考点二:树的性质和存储
1、树的性质
m h −1
性质3: 高度为h的m次树至多有 个结点。
m −1
m次树每层最多结点数:
第1层:1
第2层:m1
第3层:m2

第h层: mh-1考点二:树的性质和存储
1、树的性质
性质4:具有n个结点的m次树的最小高度为log (n(m-1)+1)。
m
m次树每层最多结点数:
第1层:1
第2层:m1
第3层:m2

第h层: mh-1考点二:树的性质和存储
1、树的性质
性质5:对于m度树,定义叶子结点个数为n ,度为1的结点个数为n ,…
0 1
度为m的结点个数为n , 于是有
m
n = n +2*n + 3* n +… +(m-1)* n + 1
0 2 3 4 m
结点个数表示:n为总结点个数,n为度为i(0≤i≤m)的结点个数
i
n=n+n+…+n
0 1 m考点二:树的性质和存储
1、树的性质
性质5:对于m度树,定义叶子结点个数为n ,度为1的结点个数为n ,…
0 1
度为m的结点个数为n , 于是有
m
n = n +2*n + 3* n +… +(m-1)* n + 1
0 2 3 4 m
在所有结点度之和中,一个度为1的结点贡献1个度,…,一个度为i
的结点贡献i个度,…,一个度为m的结点贡献m个度
 所有结点度之和 = n+2*n+…+m*n = n-1
1 2 m考点二:树的性质和存储
2、树的存储 A
实现树的存储结构,关键是什么?
B C
如何表示树中结点之间的逻辑关系
D E F G H
什么是存储结构?
数据元素及其逻辑关系在存储器中的表示
I
树中结点之间的逻辑关系是什么?
思考问题的出发点:如何表示结点的双亲和孩子考点二:树的性质和存储
2、树的存储
树的双亲表示法:用一维数组存储树中各个结点(一般按层序存储)的
数据信息以及该结点的双亲在数组中的下标
data parent
树中任何结点只有
0 A -1
A 唯一的双亲结点
1 B 0
2 C 0
B C
3 D 1
4 E 1
D E F G H
5 F 1
6 G 2
7 H 2
I
8 I 4考点二:树的性质和存储
2、树的存储
双亲存储结构的类型声明如下:
data parent
// 树的双亲表示法
#define MAXSIZE 100 0 A -1
typedef int ElemType;
1 B 0
typedef struct PTNode {
ElemType data; 2 C 0
int parent;
3 D 1
} PTNode;
4 E 1
typedef struct {
PTNode nodes[MAXSIZE]; 5 F 1
int root; // 根结点位置
6 G 2
int num; // 结点数
7 H 2
} PTree;
8 I 4考点二:树的性质和存储
2、树的存储
如何查找双亲结点?时间性能?O(1)
数据表示
O(n)
如何查找孩子结点?时间性能?
data parent firstchild
A 0 A -1
1
1 B 0
3
B C 2 C 0 6
3 D 1 -1
4 E 1
8
D E F G H
5 F 1 -1
6 G 2 -1
I 7 H 2 -1
8 I 4 -1考点二:树的性质和存储
2、树的存储
孩子链表示法 方案一:指针域的个数等于树的度
data child1 child2 …… childd
A
其中:data:数据域,存放该结点的数据信息
B C
child1~childd:指针域,指向该结点的孩子
D E F G H
I考点二:树的性质和存储
2、树的存储
孩子链表示法 方案一:指针域的个数等于树的度
A ∧
A
B C
B C ∧
D E F G H
D ∧ ∧∧ E ∧ F ∧ ∧∧ G ∧ ∧∧ H ∧ ∧∧
∧
I
缺点:浪费空间
I ∧ ∧∧考点二:树的性质和存储
2、树的存储
孩子链表示法 方案二:指针域的个数等于该结点的度
data degree child1 child2 …… childd
A
其中:data:数据域,存放该结点的数据信息
B C
degree:数据域,存放该结点的度
child1~childd:指针域,指向该结点的孩子
D E F G H
I考点二:树的性质和存储
2、树的存储
孩子链表示法 方案二:指针域的个数等于该结点的度
A
A 2
B C
B 3 C 2
D E F G H
D 0 E 1 F 0 G 0 H 0
I
I 0
缺点:结点结构不一致考点二:树的性质和存储
2、树的存储
树的孩子兄弟表示法(二叉链表)
链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针
A
某结点的第一个孩子是惟一的
某结点的右兄弟是惟一的
B C
D E F G H 设置两个分别指向该结点的
第一个孩子和右兄弟的指针
I考点二:树的性质和存储
2、树的存储
树的孩子兄弟表示法(二叉链表)
链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针
A
A ∧
B C
B C ∧
∧ D E ∧ F ∧ ∧ G ∧ H ∧
D E F G H
∧ I ∧
I考点二:树的性质和存储
2、树的存储
树的孩子兄弟表示法(二叉链表)
链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针
A ∧
firstchild data rightsib
B C ∧
typedef int ElemType;
typedef struct CSNode {
∧ D E ∧ F ∧ ∧ G ∧ H ∧
ElemType data;
struct CSNode *firstchild, *nextsibing;
∧ I ∧
} CSNode;考点二:树的性质和存储
2、树的存储
如何查找兄弟结点?时间性能? O(1)
A
A ∧
B C
B C ∧
D E F G H ∧ D E ∧ F ∧ ∧ G ∧ H ∧
∧ I ∧
I考点二:树的性质和存储
2、树的存储
O(1)
如何查找孩子结点?时间性能?
A
A∧
B C∧
B C
∧ D E ∧ F ∧ ∧ G ∧ H∧
D E F G H
∧ I ∧
I考点二:树的性质和存储
3、树的遍历
什么是遍历? 线性结构如何遍历?
简言之,遍历是对数据集合进行没有遗漏、没有重复的访问
a a a a
1 2 i n
树的遍历:从根结点出发,按照某种次序访问树中所有结点,并且每个结点仅被访问一次
前序(根)、后序(根)和层序(次)等
抽象操作,可以是对结点进行的各种处理,这里简化为输出结点的数据考点二:树的性质和存储
3、树的遍历
A
树的前序遍历操作定义:
若树为空,则空操作返回;否则
B C
(1)访问根结点
(2)从左到右前序遍历根结点的每一棵子树
D E F G
A B D E H I F C G
H I考点二:树的性质和存储
3、树的遍历
A
树的后序遍历操作定义:
B C
若树为空,则空操作返回;否则
(1)从左到右后序遍历根结点的每一棵子树
D E F G
(2)访问根结点
D H I E F B G C A
H I考点二:树的性质和存储
3、树的遍历
树的层序遍历操作定义:
从树的根结点开始,自上而下逐层遍历,在同一层中,按从左到
右的顺序对结点逐个访问 A
A B C D E F G H I B C
D E F G
H I【政哥题型总结】考点二:树的性质和存储
1.在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,
1个度为2的结点,10个度为1的结点,则树T的叶子结点个数是( )。
A.41 B.82 C.113 D.122考点二:树的性质和存储
1.在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,
1个度为2的结点,10个度为1的结点,则树T的叶子结点个数是( )。
A.41 B.82 C.113 D.122
性质5:对于m度树,定义叶子结点个数为n ,度为1的结点个数为n ,…
0 1
度为m的结点个数为n , 于是有
m
n = n +2*n + 3* n +… +(m-1)* n + 1
0 2 3 4 m考点二:树的性质和存储
1.在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,
1个度为2的结点,10个度为1的结点,则树T的叶子结点个数是( )。
A.41 B.82 C.113 D.122
B【解析】m = 4,n = n+n+n+n+n = n+10+1+10+20 =
0 1 2 3 4 0
n+41。n-1 = 度之和 = n+2n+3n+4n = 122,得n = 123。
0 1 2 3 4
n = n-41 = 123-41 = 82。
0考点二:树的性质和存储
2.深度为h的满m叉树的第k(1≤k≤h)层有( )个结点。
A.mk-1 B.mk-1 C.mh-1 D.mh-1考点二:树的性质和存储
2.深度为h的满m叉树的第k(1≤k≤h)层有( )个结点。
A.mk-1 B.mk-1 C.mh-1 D.mh-1
性质2: 度为m的树中第i层上至多有mi-1个结点(i≥1)。考点二:树的性质和存储
2.深度为h的满m叉树的第k(1≤k≤h)层有( )个结点。
A.mk-1 B.mk-1 C.mh-1 D.mh-1
A【解析】根据树的性质,满m叉树,说明这棵树每层的结点个数构成首项为
1,公比是m的等比数列,所以第k项就是mk-1。THANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架考点框架
二叉树的定义
二叉树的性质
完全二叉树和满二叉树
二叉树的存储【二叉树的定义】考点三: 二叉树
二叉树: n(n≥0)个结点的有限集合,该集合或者为空集(称为
空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结
点的左子树和右子树的二叉树组成。
A
二叉树是度为 2 的树吗?
B C
二叉树是度小于等于 2 的树吗?
A A D E F
B B
G考点三: 二叉树
二叉树的基本形态
二叉树有5种基本形态,如图所示。
A
A
(a) 空二叉树 (b) 单结点二叉树
(c) 右子树为空
A A
(d) 左子树为空
(e) 左、右子树都不空考点三: 二叉树
二叉树有什么特点?
(1)每个结点最多有两棵子树
(2)二叉树是有序的,其次序不能任意颠倒
A
为什么要研究二叉树?
B C
(1)二叉树是最简单的树结构
(2)将树转换为二叉树,
从而利用二叉树解决树的有关问题
D E F
G考点三: 二叉树
左斜树:所有结点都只有左子树的二叉树
右斜树:所有结点都只有右子树的二叉树
斜树:左斜树和右斜树的统称
A A
斜树有什么特点呢?
B B
(1)每一层只有一个结点
(2)结点个数与其深度相同
D D【二叉树的性质】考点三: 二叉树
i-1
性质1:在非空二叉树中,第i层上至多有2 个结点(i≧1)。
证明:用数学归纳法证明。
1-1 0
当i=1时:只有一个根结点,2 =2 =1,命题成立。
(i-1)-1
现假设对i>1时,处在第i-1层上至多有2 个结点。
i-2
由归纳假设知,第i-1层上至多有2 个结点。由于二叉树每个结点的度
最大为2,故在第i层上最大结点数为第i-1层上最大结点数的2倍。
即 2×2 i-2 =2i-1 证毕考点三: 二叉树
k
性质2:深度为k的二叉树至多有2 -1个结点(k≧1) 。
证明:深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点
数之和。
由性质1知,二叉树的第1层、第2层⋯第k层上的结点数至多有:
0 1 k-1
2 、2 …2 。
0 1 k-1 k
∴ 总的结点数至多有: 2 +2 + …+2 =2 -1 证毕考点三: 二叉树
性质3:对任何一棵二叉树,若其叶子结点数为n ,度为2的结点数
0
为n ,则n =n +1。
2 0 2
A
性质5:对于m度树,定义叶子结
B C D
点个数为n ,度为1的结点个数为
0
n ,…度为m的结点个数为n , 于是
E F G H I J 1 m
有n = n +2*n + 3* n +…
0 2 3 4
M
K L N
+(m-1)* n + 1
m考点三: 二叉树
性质4:结点个数等于所有结点的度之和加1。
A
B C D
E F G H I J
M
K L N考点三: 二叉树
性质5:具有n个结点的二叉树的最小高度为log (n+1)。
2
k
回顾性质2:深度为k的二叉树至多有2 -1个结点(k≧1) 。
n <= 2k-1;得出 k = log (n+1)
2【完全二叉树和满二叉树】考点三: 二叉树
满二叉树:所有分支结点都存在左子树和右子树,并且所有叶子都
在同一层上的二叉树
1
A
3
2
B C
5
4 6 7
D E F G
12
9 10 11 13 14 15
H I J K L M N O考点三: 二叉树
层序编号
1
A
3
2 h = 4
B C
n = 24-1
5
4 6 7 = 15
D E F G
12
9 10 11 13 14 15
8
H I J K L M N O
层序编号:1~2h-1
满二叉树:在一棵二叉树中:
高度为h的二叉树恰好有2h-1 个结点。考点三: 二叉树
满二叉树特点
(1)叶子只能出现在最下一层 (2)只有度为 0 和度为 2 的结点
(4)在同样深度的二叉树中叶子结点个数最多
(3)在同样深度的二叉树中结点个数最多
1
A
3
2
B C
5
4 6 7
D E F G
12
9 10 11 13 14 15
H I J K L M N O考点三: 二叉树
完全二叉树:在满二叉树中,从最后一个结点开始,连续去掉任意
个结点得到的二叉树
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
最多只有下面两层的结点的度数小于2
并且最下面一层的叶结点都依次排列在该层最左边的位置上。
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K
完全二叉树实际上是对应的满二叉树删除叶结点层最右边若干个结点得到的。考点三: 二叉树
完全二叉树特点
(1)叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树
的左面
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
完全二叉树特点
(2)完全二叉树中如果有度为 1 的结点,只可能有一个,且该结点
只有左孩子
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
完全二叉树特点
(3)深度为 k的完全二叉树在 k-1 层上一定是满二叉树
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
完全二叉树特点
(4)在同样结点个数的二叉树中,完全二叉树的深度最小
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K【完全二叉树的性质】考点三: 二叉树
i-1
性质1:在非空二叉树中,第i层上至多有2 个结点(i≧1)。
证明:用数学归纳法证明。
1-1 0
当i=1时:只有一个根结点,2 =2 =1,命题成立。
(i-1)-1
现假设对i>1时,处在第i-1层上至多有2 个结点。
i-2
由归纳假设知,第i-1层上至多有2 个结点。由于二叉树每个结点的度
最大为2,故在第i层上最大结点数为第i-1层上最大结点数的2倍。
即 2×2 i-2 =2i-1 证毕考点三: 二叉树
k
性质2:深度为k的二叉树至多有2 -1个结点(k≧1) 。
证明:深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点
数之和。
由性质1知,二叉树的第1层、第2层⋯第k层上的结点数至多有:
0 1 k-1
2 、2 …2 。
0 1 k-1 k
∴ 总的结点数至多有: 2 +2 + …+2 =2 -1 证毕考点三: 二叉树
性质3:对任何一棵二叉树,若其叶子结点数为n ,度为2的结点数
0
为n ,则n =n +1。
2 0 2
A
性质5:对于m度树,定义叶子结点
B C D
个数为n ,度为1的结点个数为
0
n ,…度为m的结点个数为n , 于是
E F G H I J 1 m
有n = n +2*n + 3* n +…
0 2 3 4
M
K L N
+(m-1)* n + 1
m考点三: 二叉树
性质4:结点个数等于所有结点的度之和加1。
A
B C D
E F G H I J
M
K L N考点三: 二叉树
性质5:深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深
度为k的完全二叉树。
其中 2k-1 ≦ n≦2k-1 。
完全二叉树是满二叉树的一部分,而满二叉树是完全二叉树的特例。
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
性质6:n个结点的完全二叉树深度为:㏒ n +1或者log (n+1) 。
2 2
其中符号: x表示不大于x的最大整数。
x 表示不小于x的最小整数。
回顾性质5:深度为k的满二叉树中编号从1到n的前n个结点构成了一棵
深度为k的完全二叉树。
其中 2k-1 ≦ n≦2k-1 。
则可以解出
(1) 2k-1 ≦ n 推出 k <= ㏒ n +1
2
(2) n≦2k-1 推出 k >= log (n+1)
2
高等数学夹逼定理:k = ㏒ n +1 = log (n+1)
2 2考点三: 二叉树
性质7:若完全二叉树的深度为k ,则所有的叶子结点都出现在第k层
或k-1层。
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
性质8:对于任一结点,如果其右子树的最大层次为L,则其左子树的最
大层次为L或L+1。
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
性质9:对一棵具有 n个结点的完全二叉树中从 1 开始按层序编号,对于
任意的序号为 i(1≤i≤n)的结点(简称结点 i),有:
(1)如果 i>1,则结点 i的双亲结点的序号为 ⌊i/2⌋,否则结点 i无双亲结点
(2)如果 2i≤n,则结点 i的左孩子的序号为 2i,否则结点 i无左孩子
(3)如果 2i+1≤n,则结点 i的右孩子的序号为2i+1,否则结点 i无右孩子
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
性质9:对一棵具有 n个结点的完全二叉树中从 0开始按层序编号,对于
任意的序号为 i(0≤i≤n-1)的结点(简称结点 i),有:
(1)如果 i>0,则结点 i的双亲结点的序号为 ⌊i-1/2⌋,否则结点 i无双亲结点
(2)如果 2i+1<=n,则结点 i的左孩子的序号为 2i+1,否则结点 i无左孩子
(3)如果 2i+2<=n,则结点 i的右孩子的序号为2i+2,否则结点 i无右孩子
0
A
2
1
B C
3 4 5 6
D E F G
7 8 9 10
H I J K考点三: 二叉树
性质10:对于一个棵完全二叉树,度为1的节点个数是1或0.
1
A
3 满的
2
B C
4 5 6 7
D E F G
8 9 10 11
H I J K考点三: 二叉树
ADT BiTree
DataModel
二叉树由一个根结点和两棵互不相交的左右子树构成,结点具有层次关系
Operation
InitBiTree:初始化一棵空的二叉树
CreatBiTree:建立一棵二叉树
DestroyBiTree:销毁一棵二叉树
PreOrder:前序遍历二叉树
InOrder:中序遍历二叉树
简单起见,只讨论二叉树的遍历
PostOrder:后序遍历二叉树
LeverOrder:层序遍历二叉树
endADT【二叉树的存储】考点三: 二叉树
顺序存储结构
用一组连续的存储单元依次存储数据元素,由存储位置表示元素之间的逻辑关系
二叉树的顺序存储结构是用一维数组存储二叉树的结点,结点的存
储位置(下标)应能体现结点之间的逻辑关系——父子关系
如何利用数组下标来反映结点之间的逻辑关系?
完全二叉树中结点的编号可以唯一地反映结点之间的逻辑关系考点三: 二叉树
二叉树的性质9,完全二叉树结点按层序编号:
i/2
i
2i 2i+1考点三: 二叉树
1
A
完 3
2
全 B C
二
叉 5 6 7
4
树 D E F G
的
顺
8 9 10 11
序
H I J K
存
储
结
构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J K # # # #
顺序存储结构(不用下标为0的元素)考点三: 二叉树
1
A
3
2
D
非 B
完 一般的二叉树先用空结
全 5 6 7 点补全成为完全二叉树,
4
二 # C # E 然后对结点编号
叉
树
10 11
12 13 14
的 8 9
# # # # # # F
顺
序
存
储 1 2 3 4 5 6 7 8 9 10 11 12 13 14
结
A B D # C # E # # # # # # F
构
typedef ElemType SqBTree[MaxSize];
用一个数组存储
SqBTree bt="#ABD#C#E######F";考点三: 二叉树
二叉树顺序存储结构的特点:
对于完全二叉树来说,其顺序存储是十分合适的。
对于一般的二叉树,特别是对于那些单分支结点较多的二叉树来说
是很不合适的,因为可能只有少数存储单元被利用,特别是对退化
的二叉树(即每个分支结点都是单分支的),空间浪费更是惊人。
在顺序存储结构中,找一个结点的双亲和孩子都很容易。
A
二叉树的顺序存储结构
一般仅存储完全二叉树 C
G
O考点三: 二叉树
用链接存储方式存储二叉树
head
a a a
∧
1 2 n
二叉链表:二叉树的每个结点对应一个链表结点,链表结点
存放结点的数据信息和指示左右孩子的指针 A
B C
lchild data rchild
D E F
G考点三: 二叉树
A
A
B C
B ∧ C
D E F
∧ D ∧ E ∧ ∧ F ∧
G
∧ G ∧考点三: 二叉树
A
A
B C
B ∧ C
D E F
∧ D ∧ E ∧ ∧ F ∧
G
∧ G ∧
二叉链存储结构的特点:
除了指针外,二叉链比较节省存储空间。占用的存储空间与树形没有关系,
只与树中结点个数有关。
在二叉链中,找一个结点的孩子很容易,但找其双亲不方便。考点三: 二叉树
typedef char ElemType;
typedef struct BTNode {
A
ElemType data;
B ∧ C
struct BTNode *lchild, *rchild;
} BTNode, *BiTree;
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
叶子结点的标志? 左右孩子指针均为空考点三: 二叉树
typedef char ElemType;
typedef struct BTNode {
A
ElemType data;
B ∧ C struct BTNode *lchild, *rchild;
} BTNode, *BiTree;
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
n 个结点的二叉链表有多少个空指针?
2n-(n-1) = n+1 个空指针考点三: 二叉树
在二叉链表中增加一个指向双亲的指针域
A
lchild data parent rchild
B ∧ C
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
如何查找双亲?时间性能? O(n)考点三: 二叉树
A
A ∧
B C
B ∧ C
D E F
∧ D ∧ E ∧ ∧ F ∧
G
typedef char ElemType;
∧ G ∧
typedef struct BTNode {
ElemType data;
struct BTNode *Lchild, *Rchild, *parent ;
}BTNode;【政哥题型总结】考点三: 二叉树
1.一棵完全二叉树上有1000个结点,其中叶子结点的个数是( )。
A.489 B.500 C.254 D.512考点三: 二叉树
1.一棵完全二叉树上有1000个结点,其中叶子结点的个数是( )。
A.489 B.500 C.254 D.512
①根据结点个数,n1+n2+n0=1000,
根据性质10,对于一个棵完全二叉树,度为1的节点个数是1或0. :
n1={1,0},
根据性质3:n0=n2+1,
可以得到2×n2+n1+1=1000,等号右边是偶数,等号左边也是偶数,
因此得到n1=1,n2=499,n0=500。考点三: 二叉树
1.一棵完全二叉树上有1000个结点,其中叶子结点的个数是( )。
A.489 B.500 C.254 D.512
①根据性质,
n1+n2+n0=1000,
n1={1,0},
n0=n2+1,可以得到2×n2+n1+1=1000,等号右边是偶数,等号左
边也是偶数,因此得到n1=1,n2=499,n0=500。考点三: 二叉树
1.一棵完全二叉树上有1000个结点,其中叶子结点的个数是( )。
A.489 B.500 C.254 D.512
②根据性质9,
i/2
i/2
500
i
1000
2i 2i+1
一棵完全二叉树上有1000个结点,那么最后一个结点的编号是1000,
它的双亲结点的编号是500,因此编号为500后的结点都是叶子结点,
故有500个叶子结点。考点三: 二叉树
2.具有126个结点的完全二叉树其深度为( )(根的层次值为1)。
A.8 B.7 C.6 D.5考点三: 二叉树
2.具有126个结点的完全二叉树其深度为( )(根的层次值为1)。
A.8 B.7 C.6 D.5
B【解析】根据性质6,n个结点的完全二叉树深度为:㏒ n +1或者
2
log (n+1) 。将126代入公式,可以得到深度是7。
2考点三: 二叉树
3.将一棵有100个结点的完全二叉树从根结点开始,每层从左到右依次
对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号
为( )。
A.98 B.99 C.50 D.48考点三: 二叉树
3.将一棵有100个结点的完全二叉树从根结点开始,每层从左到右依次
对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号
为( )。
A.98 B.99 C.50 D.48
性质9:对一棵具有 n个结点的完全二叉树中从 1 开始按层序编号,对于
任意的序号为 i(1≤i≤n)的结点(简称结点 i),有:
(1)如果 i>1,则结点 i的双亲结点的序号为 ⌊i/2⌋,否则结点 i无双亲结点
(2)如果 2i≤n,则结点 i的左孩子的序号为 2i,否则结点 i无左孩子
(3)如果 2i+1≤n,则结点 i的右孩子的序号为2i+1,否则结点 i无右孩子考点三: 二叉树
3.将一棵有100个结点的完全二叉树从根结点开始,每层从左到右依次
对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号
为( )。
A.98 B.99 C.50 D.48
A【解析】根据性质9,若2i>n,则结点i为叶子结点,无左孩子;否则,
其左孩子结点编号是2i。若2i+1>n,则结点i无右孩子;否则,其右孩
子结点编号是2i+1。编号为49的结点的左孩子的编号是49×2=98。考点三: 二叉树
4.若一棵完全二叉树的第6层有3个叶子结点,则该完全二叉树一共最
多有( )个叶子结点,最少有( )个叶子结点。
A.60,17 B.60,18 C.61,17 D.61,18考点三: 二叉树
4.若一棵完全二叉树的第6层有3个叶子结点,则该完全二叉树一共最
多有( )个叶子结点,最少有( )个叶子结点。
A.60,17 B.60,18 C.61,17 D.61,18
C【解析】根据性质7,若完全二叉树的深度为k,则所有的叶子结点都
出现在第k层或第k-1层。
若一棵完全二叉树的第6层有3个叶子结点,则说明这棵树可能有6层,
也可能有7层。
所以,对应于有6层时,叶子结点最少;对应于有7层时,叶子结点最多。考点三: 二叉树
4.若一棵完全二叉树的第6层有3个叶子结点,则该完全二叉树一共最
多有( )个叶子结点,最少有( )个叶子结点。
A.60,17 B.60,18 C.61,17 D.61,18
假设树有6层,根据树的性质,第5层有25-1=16个结点,且第6层有3个叶
子结点,那么第5层将会有两个结点被用掉,因此一共有16-2+3=17(个)
叶子结点。 A
B C
D E F G
H I J K J K J K
J K J考点三: 二叉树
4.若一棵完全二叉树的第6层有3个叶子结点,则该完全二叉树一共最
多有( )个叶子结点,最少有( )个叶子结点。
A.60,17 B.60,18 C.61,17 D.61,18
假设树有7层,根据树的性质,第6层有26-1=32个结点,且第6层有3个叶
子结点,于是第7层最多有29×2=58(个)叶子结点,总的叶子结点是
58+3=61(个)孩子。 A
B C
D E F G
H I J K J K J K
J K JTHANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集【二叉树遍历的概念】考点框架考点框架
二叉树遍历的概念
先序遍历
中序遍历
后序遍历
层次遍历
二叉树的生成【二叉树遍历的概念】考点四: 二叉树的遍历
二叉树的遍历:从根结点出发,按照某种次序访问树中所有结点,
并且每个结点仅被访问一次
限定先左后右:前序、中序、后序
抽象操作,可以是对结点进行的各种处理,这里简化为输出结点的数据
按照什么次序对二叉树进行遍历呢?
根结点D
二叉树的遍历方式:
二叉树 左子树L
DLR、LDR、LRD、DRL、RDL、RLD
右子树R
层序遍历:按二叉树的层序编号的次序访问各结点考点四: 二叉树的遍历
二叉树是一种非线性结构,每个结点都可能有左、右两棵子树,因此,
需要寻找一种规律,使二叉树上的结点能排列在一个线性序列上,从而
实现遍历。
a
b a b c d e f
先序遍历
c d
e f
二叉树考点四: 二叉树的遍历
N
L R
NLR
6 LNR 只考虑L→ R的情况
种
LRN
遍
历
NRL
方
式 RNL
RLN考点四: 二叉树的遍历
先序遍历 根左右
中序遍历
左根右
二叉树遍历
后序遍历 左右根
层次遍历
逐层遍历考点四: 二叉树的遍历
先序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)访问根结点
(2)前序遍历根结点的左子树
(3)前序遍历根结点的右子树
D E F
前序遍历序列:A B D G C E F
G考点四: 二叉树的遍历
// 递归先序遍历 typedef char ElemType;
void PreOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
visit(t); struct BTNode *lchild, *rchild;
PreOrderVisit(t->lchild, visit); } BTNode, *BiTree;
PreOrderVisit(t->rchild, visit);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
中序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)中序遍历根结点的左子树
(2)访问根结点
(3)中序遍历根结点的右子树 D E F
中序遍历序列:D G B A E C F
G考点四: 二叉树的遍历
// 递归中序遍历 typedef char ElemType;
void InOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
InOrderVisit(t->lchild, visit); struct BTNode *lchild, *rchild;
visit(t); } BTNode, *BiTree;
InOrderVisit(t->rchild, visit);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
后序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)后序遍历根结点的左子树
(2)后序遍历根结点的右子树
(3)访问根结点
D E F
后序遍历序列:GDBEFCA
G考点四: 二叉树的遍历
// 递归后序遍历 typedef char ElemType;
void PostOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
PostOrderVisit(t->lchild, visit); struct BTNode *lchild, *rchild;
PostOrderVisit(t->rchild, visit); } BTNode, *BiTree;
visit(t);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
层次遍历方法
A
从二叉树的根结点开始,从上至下逐
B C
层遍历,在同一层中,则按从左到右
的顺序对结点逐个访问
D E F
层序遍历序列:A B C D E F G
G【先序遍历】考点四: 二叉树的遍历
先序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)访问根结点
(2)前序遍历根结点的左子树
(3)前序遍历根结点的右子树
D E F
前序遍历序列:A B D G C E F
G考点四: 二叉树的遍历
先序遍历方法考点四: 二叉树的遍历
// 递归先序遍历 typedef char ElemType;
void PreOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
visit(t); struct BTNode *lchild, *rchild;
PreOrderVisit(t->lchild, visit); } BTNode, *BiTree;
PreOrderVisit(t->rchild, visit);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
Pre(∧)
Pre(*B)
(2)B
Pre(*D)
Pre(*A)
Pre(B->lchild);
(3)D Pre(∧)
(1)A Pre(B->rchild);
Pre(D->lchild);
Pre(∧)
Pre(D->rchild);
Pre(A->lchild);
A
B C
D考点四: 二叉树的遍历
Pre(∧)
Pre(*B)
(2)B
Pre(*D)
Pre(*A)
Pre(B->lchild);
(3)D Pre(∧)
(1)A Pre(B->rchild);
Pre(D->lchild);
Pre(∧)
Pre(D->rchild);
Pre(A->lchild);
Pre(*C)
Pre(A->rchild); (4)C Pre(∧)
Pre(C->lchild); A
Pre(∧)
Pre(C->rchild);
B C
D考点四: 二叉树的遍历
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(1)首先我们要用一个指针(T)来指向当前访问的结点。
如图(a)所示,算法开始执行时,对应算法第1行,当前节点是A,这个节点不为空,
执行第3行,将它的数据输出,得到A,将这个节点A(图上的栈中写了节点的值是为了便
于理解,实际上栈中保存的是节点地址)压栈
执行第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是B,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(2)如图(b)所示,对应算法第1行,当前节点是B,这个节点不为空,
执行第3行,将它的数据输出,得到B,将这个节点B压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是D,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(3)如图(c)所示,对应算法第1行,当前节点是D,这个节点不为空,
执行第3行,将它的数据输出,得到D,将这个节点D压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是NULL,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(4)如图(d)所示,对应算法第1行,当前节点是NULL,执行第2行,返回。请注意
此时将会到D调用左子树的第4行(该语句返回),那么将执行第5行,此时为了执行第
五行,需要讲D弹出,以便于获得D->Rchlid。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(5)如图(e)所示,D->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,
执行第2行,返回。请注意此时将会到B调用左子树的第4行(该语句返回),那么将执行
第5行,此时为了执行第5行,需要将B弹出,以便于获得B->Rchlid。而B->Rchlid是F。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(6)如图(f)所示,对应算法第1行,当前节点是F,这个节点不为空,
执行第3行,将它的数据输出,得到F,将这个节点F压栈。
第4行,T= T->Lchlid, 将T的左子树赋给T,此时T是E,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(7)如图(g)所示,对应算法第1行,当前节点是E,这个节点不为空,
执行第3行,将它的数据输出,得到E,将这个节点E压栈。
第4行,T= T->Lchlid, 将T的左子树赋给T,此时T是NULL,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(8) 如图(h)所示对应算法第1行,当前节点是NULL,这个节点为空,
执行第2行,返回。请注意此时将会到E调用左子树的第4行(该语句返回),那么将执行
第5行,此时为了执行第5行,需要将E弹出,以便于获得E->Rchlid。而E->Rchlid是NULL。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(9) 如图(i)所示,E->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,执行
第2行,返回。请注意此时将会到F调用左子树的第4行(该语句返回),那么将执行第5
行,此时为了执行第五行,需要将F弹出,以便于获得F->Rchlid。而F->Rchlid是NULL。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(10) 如图(j)所示,F->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,执
行第2行,返回。请注意此时将会到A调用左子树的第4行(该语句返回),那么将执行第
5行,此时为了执行第五行,需要将A弹出,以便于获得A->Rchlid。而A->Rchlid是C。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(11) 如图(k)所示,对应算法第1行,当前节点是C,这个节点不为空,
执行第3行,将它的数据输出,得到C,将这个节点C压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是G,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(12) 如图(l)所示,对应算法第1行,当前节点是G,这个节点不为空,
执行第3行,将它的数据输出,得到G,将这个节点G压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是H,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(13) 如图(m)所示,对应算法第1行,当前节点是H,这个节点不为空,
执行第3行,将它的数据输出,得到H,将这个节点H压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是NULL,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(14) 如图(n)所示,对应算法第1行,当前节点是NULL,这个节点为空,
执行第2行,返回。请注意此时将会到H调用左子树的第4行(该语句返回),那么将执行第
5行,此时为了执行第五行,需要将H弹出,以便于获得H->Rchlid。而H->Rchlid是NULL。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(15)如图(o)所示,H->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,执行
第2行,返回。请注意此时将会到G调用左子树的第4行(该语句返回),那么将执行第5行,
此时为了执行第五行,需要将G弹出,以便于获得G->Rchlid。而G->Rchlid是NULL。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(16)如图(p)所示, G->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,执
行第2行,返回。请注意此时将会到C调用左子树的第4行(该语句返回),那么将执行
第5行,此时为了执行第五行,需要将C弹出,以便于获得C->Rchlid。而C->Rchlid是I。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(17) 如图(p)所示,,对应算法第1行,当前节点是I,这个节点不为空,
执行第3行,将它的数据输出,得到I,将这个节点I压栈。
第4行,T = T->Lchlid, 将T的左子树赋给T,此时T是NULL,转向递归调用的第1行。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(18) 如图(q)所示,对应算法第1行,当前节点是NULL,这个节点为空,
执行第2行,返回。请注意此时将会到I调用左子树的第4行(该语句返回),那么将执行
第5行,此时为了执行第5行,需要将I弹出,以便于获得I->Rchlid。而I->Rchlid是NULL。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
(19)如图(r)所示,I->Rchlid递归调用函数,对应算法第1行,当前节点是NULL,执行
第2行,返回。请注意此时将会到I调用左子树的第4行(该语句返回),那么将执行第5行,
此时为了执行第五行,需要将I弹出,以便于获得I->Rchlid。而I->Rchlid是NULL。
(20) 如图(r)所示,此时栈中没有结点,算法结束。
// 递归先序遍历
①void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
② if (!t) return;
③ visit(t);
④ PreOrderVisit(t->lchild, visit);
⑤ PreOrderVisit(t->rchild, visit);
⑥}考点四: 二叉树的遍历
// 非递归先序遍历 非递归算法的执行过程和递
void PreOrderVisit2(BiTree t, void (*visit)(BiTree)) {
归的执行示意图是一样的,唯
stack<BiTree> s;
一的区别是递归中系统栈换
while (t || !s.empty()) {
成用户栈(对应代码的第4行),
if (t) {
我们需要自己定义一个栈。
visit(t); // 先访问当前子树的根结点
s.push(t); // 将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
s.pop(); // 弹出最近访问子树的根结点
t = t->rchild; // 访问当前子树的右子树
}
}
}【中序遍历】考点四: 二叉树的遍历
中序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)中序遍历根结点的左子树
(2)访问根结点
(3)中序遍历根结点的右子树 D E F
中序遍历序列:D G B A E C F
G考点四: 二叉树的遍历
中序遍历方法考点四: 二叉树的遍历
// 递归中序遍历 typedef char ElemType;
void InOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
InOrderVisit(t->lchild, visit); struct BTNode *lchild, *rchild;
visit(t); } BTNode, *BiTree;
InOrderVisit(t->rchild, visit);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
// 非递归中序遍历
void InOrderVisit2(BiTree t, void (*visit)(BiTree)) {
stack<BiTree> s;
while (t || !s.empty()) {
if (t) {
s.push(t); // 先将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
s.pop(); // 弹出最近访问子树的根结点
visit(t); // 访问当前子树的根结点
t = t->rchild; // 访问当前子树的右子树
}
}
}【后序遍历】考点四: 二叉树的遍历
后序遍历方法
A
若二叉树为空,则空操作返回;否则:
B C
(1)后序遍历根结点的左子树
(2)后序遍历根结点的右子树
(3)访问根结点
D E F
后序遍历序列:GDBEFCA
G考点四: 二叉树的遍历
后序遍历方法考点四: 二叉树的遍历
// 递归后序遍历 typedef char ElemType;
void PostOrderVisit(BiTree t, void (*visit)(BiTree)) { typedef struct BTNode {
if (!t) return; ElemType data;
PostOrderVisit(t->lchild, visit); struct BTNode *lchild, *rchild;
PostOrderVisit(t->rchild, visit); } BTNode, *BiTree;
visit(t);
}
L R
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机考点四: 二叉树的遍历
// 非递归后序遍历
void PostOrderVisit2(BiTree t, void (*visit)(BiTree)) {
stack<BiTree> s;
BiTree last = NULL; // 记录最近访问过的结点
while (t || !s.empty()) {
if (t) {
s.push(t); // 先将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
if (t->rchild && t->rchild != last) {
t = t->rchild; // 当前子树的右子树存在且未被访问过,访问当前子树的右子树
} else {
s.pop(); // 弹出最近访问子树的根结点
visit(t); // 访问当前子树的根结点
last = t; // 记录最近访问过的结点
t = NULL; // 置空,继续弹出栈顶结点
}
}
}
}【层次遍历】考点四: 二叉树的遍历
层次遍历方法
A
从二叉树的根结点开始,从上至下逐
B C
层遍历,在同一层中,则按从左到右
的顺序对结点逐个访问
D E F
层序遍历序列:A B C D E F G
G考点四: 二叉树的遍历
// 层次遍历 typedef char ElemType;
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
if (!t) {
return; // 空树直接返回 ElemType data;
}
struct BTNode *lchild, *rchild;
queue<BiTree> q;
q.push(t); // 根结点入队 } BTNode, *BiTree;
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(1) 先将根结点A入队。此时队列有且仅有一个结点A,如图(a)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(2) 队列不为空。队头A出队,A的左、右子树B和C不为空,B和C依次人队,如 (b)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(3) 队列不为空。队头B出队,B的左、右子树D和F不为空,D和F依次人队,如图 (c)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(4) 队列不为空。队头C出队,C的左、右子树G和I不为空,G和I依次入队,如图 (d)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(5) 队列不为空。队头D出队,D无左、右子树,不执行人队操作,如图 (e)所示
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(6) 队列不为空。队头F出队,F的左子树E不为空,E人队,如图 (f)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(7) 队列不为空。队头G出队,G的左子树 H不为空,H人队,如图 (g)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(8) 队列不为空。队头1出队,1无左、右子树,不执行人队操作,如图 (h)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(9) 队列不为空。队头E出队,E无左、右子树,不执行入队操作,如图 (i)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
(10) 队列不为空。队头 H出队,H无左、右子树,不执行人队操作,如图 (j)所示。
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
if (!t) {
return; // 空树直接返回
}
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
}
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}考点四: 二叉树的遍历
二叉树遍历的性质
1)先序遍历,中序遍历,后续遍历使用栈 【系统栈或者用户栈】
2)层次遍历使用队列;
3)遍历过程中,叶子结点的相对顺序是不变的。
4)先序遍历是先访问元素,再入栈
5)中序遍历是先出栈,再访问元素【二叉树的生成】考点四: 二叉树的遍历
考试中,经常有一种考题,给定遍历序列,构建二叉树。根据遍历的
特点,会有三种不同的组合方式,可以唯一确定一棵二叉树。
A考点四: 二叉树的遍历
中序遍历 + 层次遍历:其中层次遍历确定根,中序遍历确定左右子树
中序遍历 + 后序遍历:其中后序遍历确定根,中序遍历确定左右子树
中序遍历 + 先序遍历:其中先序遍历确定根,中序遍历确定左右子树
大家记得一点,要想确定一棵二叉树,一定需要中序遍历,区分左右
子树,其他三种方式无法确定左右子树。考点四: 二叉树的遍历
已知先序序列为ABDGCEF,中序序列为DGBAECF,则构造二叉树的过程
如图所示,考点四: 二叉树的遍历
已知中序序列为DGBAECF,后序序列为GDBEFCA,则构造二叉树的过程
如图所示,考点四: 二叉树的遍历
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为
DBGEHJACIF,如图所示,考点四: 二叉树的遍历
若已知一棵二叉树的前序序列和中序序列,能否唯一确定这棵二叉树呢?
A
前序:B C 前序:A B C D E F G H I
中序:B C
中序:B C A E D G H F I
B C D E F
G H I
前序: D E F G H I
A
中序: E D G H F I
B D
C E
F G
H I考点四: 二叉树的遍历
若已知一棵二叉树的前序序列和中序序列,能否唯一确定这棵二叉树呢?
A
前序: F G H I
中序: G H F I
B D
C E F
G H I考点四: 二叉树的遍历
若已知一棵二叉树的前序序列和中序序列,能否唯一确定这棵二叉树呢?
A
前序: G H
中序: G H
B D
C E F
G I
H考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为
DCEGBFHKJIA。请画出该树。
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A
D C B H F I
G E J K考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A
A
B H F I
D C B H F I
J K
G E J K
D C G E考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A
A
B H F I
B H F I
J K
J K
C
G E
D C G E
D考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A A
B H F I B H F I
J K J K
C C
G E G
E
D
D考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A
A
B I
B H F I
J K
H F J K
C
G
C
G
D E
E
D考点四: 二叉树的遍历
若已知一棵二叉树的后序序列和中序序列,能否唯一确定这棵二叉树呢?
中序序列:D C B G E A H F I J K
后序序列:D C E G B F H K J I A
A
A
B I
B K
H
J
C
H F I J G
C
G
F K
E
E D
D考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A A
C
D B G C I F B
E H J考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
A
B C B C
D E
D G E
H J考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
B C
D E F考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
B C
D E F考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
A
B C
B C
D E F
D E F
G H考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
A
B C
B C
F
D E F D E
G H G H I考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
B C
D E F
G H I考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
A
C
B
B C
F
D E
D E F
H I
G
G H I
J考点四: 二叉树的遍历
若已知一棵二叉树的层序序列和中序序列,能否唯一确定这棵二叉树呢?
假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。
请画出该树。
层次序列:A B C D E F G H I J
中序序列:D B G E H J A C I F
A
A
B C
B C
F
D E
D E F
H I
G
G H I
J考点四: 二叉树的遍历
要想确定一个二叉树,只要提供区分左右子树、区分根的方法,就可以确定唯
一的二叉树,于是
• 中序遍历 + 层次遍历:其中层次遍历确定根,中序遍历确定左右子树
• 中序遍历 + 后序遍历:其中后序遍历确定根,中序遍历确定左右子树
• 中序遍历 + 先序遍历:其中先序遍历确定根,中序遍历确定左右子树
• 二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍历)考点四: 二叉树的遍历
要想确定一个二叉树,只要提供区分左右子树、区分根的方法,就可以确定
唯一的二叉树,于是
• 二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍历)考点四: 二叉树的遍历
二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍
历)
中序序列:D B G E H J A C I F
A
C
B
F
D E
I
G H
J考点四: 二叉树的遍历
二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍
历)
层次序列:A B C D E F G H I J
A
C
B
F
D E
I
G H
J考点四: 二叉树的遍历
二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍
历)
先序序列:A B D E G H J C F I
A
C
B
F
D E
I
G H
J考点四: 二叉树的遍历
二叉树树形结构 + 遍历序列(先序遍历、中序遍历、后序遍历、层次遍
历)
后序序列:D G J H E B I F C A
A
C
B
F
D E
I
G H
J考点四: 二叉树的遍历
若已知一棵二叉树的前序(或中序,或后序,或层序)序列,能
否唯一确定这棵二叉树呢?
若已知一棵二叉树的前序序列和后序序列,能否唯一确定
这棵二叉树呢?
A
A
B
前序遍历序列:A B C
B
后序遍历序列:C B A
C
C【政哥题型总结】考点四: 二叉树的遍历
1.若非空二叉树的先序序列与中序序列的次序正好相同,则该二叉树
一定是( )的二叉树。
A.左子树为空
B.其中任一结点无左孩子
C.右子树为空
D.其中任一结点无右孩子考点四: 二叉树的遍历
1.若非空二叉树的先序序列与中序序列的次序正好相同,则该二叉树
一定是( )的二叉树。
A.左子树为空
B.其中任一结点无左孩子
C.右子树为空
D.其中任一结点无右孩子
B【解析】在遍历中,先序序列,根左右;中序序列,左根右。则
①空树:先序序列与中序序列的次序正好相同;
②只有根结点:先序序列与中序序列的次序正好相同;
③只有左子树:先序序列为根左,中序序列为左根,先序序列与中序序列的
次序正好相反;考点四: 二叉树的遍历
1.若非空二叉树的先序序列与中序序列的次序正好相同,则该二叉树
一定是( )的二叉树。
A.左子树为空
B.其中任一结点无左孩子
C.右子树为空
D.其中任一结点无右孩子
B【解析】在遍历中,先序序列,根左右;中序序列,左根右。则
④只有右子树:先序序列为根右,中序序列为根右,先序序列与中序序列的
次序正好相同;
⑤左子树和右子树均有:先序序列为根左右,中序序列为左根右,先序序列
与中序序列的次序正好不同。
综上,任一结点无左孩子。考点四: 二叉树的遍历
2.在二叉树结点的先序、中序和后序序列中,所有叶子结点的先后顺
序( )。
A.都不相同
B.完全相同
C.先序和中序相同,而与后序不同
D.中序和后序相同,而与先序不同考点四: 二叉树的遍历
2.在二叉树结点的先序、中序和后序序列中,所有叶子结点的先后顺
序( )。
A.都不相同
B.完全相同
C.先序和中序相同,而与后序不同
D.中序和后序相同,而与先序不同
B【解析】这是一个性质,大家要记住,在二叉树结点的先序、中序和
后序序列中,所有叶子结点的先后顺序完全相同。考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
解析 通过先序序列和中序序列确定一棵二叉树,需要通过先序序列确
定根结点,中序序列确定左、右子树,逐级进行确定。考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
解析
E 先序: E B A D C F H G I K J
中序: A B C D E F G H I J K
A B F H G
C D I K J考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
解析
E 先序: E B A D C F H G I K J
中序: A B C D E F G H I J K
A B F H G
C D I K J
E
B
F H G
I K J
A
C D考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
解析
先序: E B A D C F H G I K J
E
中序: A B C D E F G H I J K
B
F H G
I K J
E
A
C D
B
F H G
I K J
A
D
C考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
E
先序: E B A D C F H G I K J
中序: A B C D E F G H I J K
B
F H G
I K J E
A
D
B F
C
A D H G I
K J
C考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
E 先序: E B A D C F H G I K J
中序: A B C D E F G H I J K
B F
E
A
D H G I
B F
K J
C
A H
D
G I K J
C考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
E 先序: E B A D C F H G I K J
中序: A B C D E F G H I J K
B F
E
A H
D
B F
G I K J
C
A H
D
G I
C
J K考点四: 二叉树的遍历
3.假设一棵二叉树先序序列为EBADCFHGIKJ,中序序列为
ABCDEFGHIJK,请画出该树。
E
先序: E B A D C F H G I K J
B F 中序: A B C D E F G H I J K
E
A H
D
G I B F
C
J K
A H
D
G I
C
K
J考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。
解析 通过层次遍历和中序遍历确定一棵二叉树,需要通过层次遍历确定根结
点,中序遍历确定左、右子树。但是层次遍历有其特殊性,是按照层进行遍历
的。考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。
解析 如图 (a)所示,因为层次遍历中第一个是A,所以A是根,在中序遍历中
得到左子树是DBGEHJ,右子树是CIF。那么说明紧挨着A的B和C就是A的左子
树和右子树。考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。
解析 如图 (b)所示,对于DBGEHJ,在层次遍历中B是根,D是左子树,GEHJ
是右子树。那么说明紧挨着C的D和E就是B的左子树和右子树。对于CIF,C没
有左子树,那么F就是右子树。考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。
解析 如图 (c)所示,D没有左、右子树,E有左、右子树,紧挨着F的G和H就是
E的左子树和右子树;F有左子树,那么I就是F的左子树。考点四: 二叉树的遍历
4.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,
请画出该树。
解析 如图 (d)所示,对于G,没有左、右子树;对于H,没有左子树,但是有
右子树J;对于I,没有左、右子树。THANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架
若结点有左孩子,则Lchild指向其左孩子,
定义 否则,指向其直接前驱;
若结点有右孩子,则Rchild指向其右孩子,
否则,指向其直接后继;
先序二叉线索树
线索二叉树
中序二叉线索树
后序二叉线索树
线索二叉树,可以加快前驱和后继
后序二叉线索树
的查找速度,但是无法很好解决的
问题是:后序遍历找直接后继考点框架
线索二叉树的概念
线索二叉树的构造
线索二叉树的遍历【线索二叉树的概念】考点五: 线索二叉树
回顾二叉树中序遍历
中序遍历就是从二叉树的根结点出发,当第二次到达结点时就输出结
点数据,按照先向左在向右的方向访问。
遍历本质上来讲是:把非线性结构线性化的操作考点五: 线索二叉树
typedef char ElemType;
二叉树的二叉链结构
typedef struct BTNode {
ElemType data;
A
struct BTNode *Lchild, *Rchild;
B ∧ C
}BTNode;
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
n 个结点的二叉链表有多少个空指针?
2n-(n-1) = n+1 个空指针考点五: 线索二叉树
线索二叉树
采用某种方法遍历二叉树的结果是一个结点的线性序列。
修改空链域改为存放指向结点的前驱和后继结点的地址。
这样的指向该线性序列中的“前驱”和“后继”的指针,称作线索。
创建线索的过程称为线索化。
线索化的二叉树称为线索二叉树。考点五: 线索二叉树
线索二叉树
在结点的存储结构上增加两个标志位来区分这两种情况:
0 表示lchild指向左孩子结点
左标志ltag
1 表示lchild指向前驱结点,即线索
0 表示rchild指向右孩子结点
右标志rtag
1 表示rchild指向后继结点,即线索
这样,每个结点的存储结构如下:
ltag lchild data rchild rtag
为了方便算法设计,在线索二叉树中再增加一个头结点。考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(1)首先看D结点,D是叶子,没有左右子树,左右指针均作为线索,
tag的值都是1,因为D没有直接前驱,D的左线索指向空,右线索指向B;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(2)接着看B结点,B有左子树,左指针指向左子树,Ltag是0,B没有
右子树,Rtag是1,指向直接后继A;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(3)接着看A结点,A有左、右子树,左指针指向左子树,Ltag是0,
右指针指向右子树,Rtag是0;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(4)接着看G结点,G是叶子,没有左右子树,左右指针均作为线索,
tag的值都是1,左线索指向直接前驱A,右线索指向直接后继E;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(5)接着看E结点,E有左子树,左指针指向左子树,Ltag是0,E没有
右子树,Rtag是1,指向直接后继C;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(6)接着看C结点,C有左、右子树,左指针指向左子树,Ltag是0,右
指针指向右子树,Rtag是0;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(7)接着看H结点,H是叶子,没有左右子树,左右指针均作为线索,
tag的值都是1,左线索指向直接前驱C,右线索指向直接后继F;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(8)接着看F结点,F有左、右子树,左指针指向左子树,Ltag是0,右
指针指向右子树,Rtag是0;考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
首先遍历二叉树得到中序遍历序列是:DBAGECHFI。然后开始检查每一
个指针,完成线索的填充,填充线索是按照遍历的顺序进行,具体过程:
(9)接着看I结点,I是叶子,没有左右子树,左右指针均作为线索,
tag的值都是1,左线索指向直接前驱C,右线索因为没有直接后继,指
向NULL。考点五: 线索二叉树
中序遍历:DBAGECHFI
A
线索二叉树
B C
D E F
G H I
0 A 0
0 B 1 0 C 0
⋀ 1 D 1 0 E 1 0 F 0
1 G 1 1 H 1 1 I 1 ⋀
中序线索树的链表结构【线索二叉树的构造】考点五: 线索二叉树
线索二叉树
采用某种方法遍历二叉树的结果是一个结点的线性序列。
修改空链域改为存放指向结点的前驱和后继结点的地址。
这样的指向该线性序列中的“前驱”和“后继”的指针,称作线索。
创建线索的过程称为线索化。
线索化的二叉树称为线索二叉树。考点五: 线索二叉树
线索二叉树的构建
建立某种次序的线索二叉树过程:
以该遍历方法遍历一棵二叉树。
在遍历的过程中,检查当前访问结点的左、右指针域是否为空:
如果左指针域为空,将它改为指向前驱结点的线索;
如果右指针域为空,将它改为指向后继结点的线索。考点五: 线索二叉树
线索二叉树的构建
线索化二叉树: 二叉树的线索化指的是依照某种遍历次序使二叉树成为
线索二叉树的过程。
线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后
继的过程。
A
A
B C
NIL
B C
NIL
D E F
D E F
G H I
G H I
中序线索树的逻辑形式
二叉树
结点序列:DBAGECHFI考点五: 线索二叉树
线索二叉树的构建
线索化二叉树: 二叉树的线索化指的是依照某种遍历次序使二叉树成为
线索二叉树的过程。
线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后
继的过程。
A
A
B C
B C
D E F
D E F NIL
G H I
G H I
二叉树 先序线索树的逻辑形式
结点序列:ABDCEGFHI考点五: 线索二叉树
线索二叉树的构建
线索化二叉树: 二叉树的线索化指的是依照某种遍历次序使二叉树成为
线索二叉树的过程。
线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后
继的过程。
A
A
B C
NIL B C
D E F
D E F
G H I
G H I
二叉树 后序线索树的逻辑形式
结点序列:DBGEHIFCA考点五: 线索二叉树
线索二叉树: 后序遍历找后继???
对于后序遍历的线索树中找结点的直接后继依然困难,分以下三种情况:
◆ 若结点是二叉树的根结点:其直接后继为空;
◆ 若结点是其父结点的左孩子或右孩子且其父结点没有右子树:直
接后继为其父结点;
◆ 若结点是其父结点的左孩子且其父结点有右子树:直接后继是对
其父结点的右子树按后序遍历的第一个结点。考点五: 线索二叉树
线索二叉树: 后序遍历找后继???
A
A
B C
NIL B C
D E F
D E F
G H I
G H I
后序线索树的逻辑形式
二叉树
结点序列:DBGEHIFCA【线索二叉树的遍历】考点五: 线索二叉树
遍历某种次序的线索二叉树就是从该次序下的开始结点出发,反复找到
该结点在该次序下的后继结点,直到头结点。考点五: 线索二叉树
在中序线索二叉树中,开始结点是根结点的最左下结点,该结点的左指针域
为线索(指向头结点的线索),即ltag=1,当找到开始结点(即结点)后访问它。
• 如果结点的右指针是右线索,说明右线索指向的是后继结点,就移到后
继结点并访问;
• 如果结点户的右指针不是右线索,它指向的是右子树,就转向右子树。
• 对右子树的遍历和对整个二又树的遍历是相似,所以中序遍历过程如下:考点五: 线索二叉树
void ThInOrder(BTNode * tb)
BTNode *p=tb->lchild; //p指向根结点
while(p!=tb) {
while(p->ltag==0)p=p-> lchild; //找开始结点
printf("%e",p-> data); //访问开始结点
while(p->rtag==l&&p-> rchild!=tb) {
p=p->rchild:
printf("%c",p->data);
}
p-p->rchild;
}
}【政哥题型总结】考点五: 线索二叉树
1.在线索化二叉树中,t所指结点没有左子树的充要条件是( )。
A.t->left==NULL B.t->ltag==1
C.t->ltag==1且t->left==NULL D.以上都不对考点五: 线索二叉树
1.在线索化二叉树中,t所指结点没有左子树的充要条件是( )。
A.t->left==NULL B.t->ltag==1
C.t->ltag==1且t->left==NULL D.以上都不对
【解析】在结点的存储结构上增加两个标志位来区分这两种情况:
0 表示lchild指向左孩子结点
左标志ltag
1 表示lchild指向前驱结点,即线索
0 表示rchild指向右孩子结点
右标志rtag
1 表示rchild指向后继结点,即线索考点五: 线索二叉树
1.在线索化二叉树中,t所指结点没有左子树的充要条件是( )。
A.t->left==NULL B.t->ltag==1
C.t->ltag==1且t->left==NULL D.以上都不对
B【解析】根据线索二叉树的定义,我们可以通过t->ltag==1判断是否有左
子树,此时t->left==NULL已经不能判断,因为有可能有前驱存在。
0 A 0
0 B 1 0 C 0
⋀ 1 D 1 0 E 1 0 F 0
1 G 1 1 H 1 1 I 1 ⋀
中序线索树的链表结构考点五: 线索二叉树
2.若对如图所示的二叉树进行中序线索化,则结点D的前驱和后继线索分别指向( )。
A.结点B和结点A B.结点C和结点B
C.结点C和结点E D.结点B和结点E考点五: 线索二叉树
2.若对如图所示的二叉树进行中序线索化,则结点D的前驱和后继线索分别指向( )。
A.结点B和结点A B.结点C和结点B
C.结点C和结点E D.结点B和结点E
【解析】在结点的存储结构上增加两个标志位来区分这两种情况:
0 表示lchild指向左孩子结点
左标志ltag
1 表示lchild指向前驱结点,即线索
0 表示rchild指向右孩子结点
右标志rtag
1 表示rchild指向后继结点,即线索考点五: 线索二叉树
2.若对如图所示的二叉树进行中序线索化,则结点D的前驱和后继线索分别指向( )。
A.结点B和结点A B.结点C和结点B
C.结点C和结点E D.结点B和结点E
A【解析】 根据中序线索化的定义,首先给出二叉树的中序遍历序列CBDAEF,
0 A 0
0 B 0 1 E 0
1 F 1 ⋀
⋀ 1 C 1 1 D 1考点五: 线索二叉树
2.若对如图所示的二叉树进行中序线索化,则结点D的前驱和后继线索分别指向( )。
A.结点B和结点A B.结点C和结点B
C.结点C和结点E D.结点B和结点E
A【解析】 根据中序线索化的定义,首先给出二叉树的中序遍历序列CBDAEF,
此时D是叶子结点,那么D的左指针指向D的直接前驱B,D的右指针指向D的直
接后继A。THANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架
加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚
线相连。
树转二叉树 去连线。除最左的第一个子结点外,父结点与所有其它子结点的
连线都去掉。 旋转。将树顺时针旋转450,原有的实线左斜。
整型。将旋转后树中的所有虚线改为实线,并向右斜。
二叉树转树
将F={T1, T2,⋯,Tn} 中的每棵树转换成二叉树。
树和二叉树
森林转二叉树 按给出的森林中树的次序,从最后一棵二叉树开始,每棵
二叉树作为前一棵二叉树的根结点的右子树,依次类推,
二叉树转森林
先序遍历:与将树转换成二叉树后对二叉树的先序遍历相同
树的遍历
后序遍历:与将树转换成二叉树后对二叉树的中序遍历相同考点框架
二叉树和树的对应关系
树转二叉树
二叉树转树
森林转二叉树
二叉树转森林
树和森林的遍历【二叉树和树的对应关系】考点六: 树、森林和二叉树的关系
树的孩子兄弟表示法(二叉链表)
链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针
A
某结点的第一个孩子是惟一的
某结点的右兄弟是惟一的
B C
D E F G H 设置两个分别指向该结点的
第一个孩子和右兄弟的指针
I考点六: 树、森林和二叉树的关系
树的孩子兄弟表示法(二叉链表)
链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针
A
A ∧
B C
B C ∧
∧ D E ∧ F ∧ ∧ G ∧ H ∧
D E F G H
∧ I ∧
I考点六: 树、森林和二叉树的关系
逻辑关系有什么变化?
A A
树:兄弟关系
B
B C D
二叉树:双亲和右孩子
E C
树:双亲和长子
E F G
二叉树:双亲和左孩子 F D
G考点六: 树、森林和二叉树的关系
从物理结构来看,树和二叉树的二叉链表是相同的,只是对指针的逻辑
解释不同而已。
对应关系 二叉树 R
树 R
A
A B C
R D B
D E
存储
存储 A E C
⋀ D ⋀
B 解释
解释
R ⋀
⋀ E ⋀
R ⋀ A
⋀ C ⋀
A B ⋀ C ⋀ ⋀ D ⋀ B
⋀ D ⋀ ⋀ E ⋀ ⋀ E ⋀ ⋀ C ⋀
树与二叉树的对应关系考点六: 树、森林和二叉树的关系
由于二叉树和树都可用二叉链表作为存储结构,对比各自的结点结构可
以看出,以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。
R
A
R
D B
A B C
E C
D E G F
G
F
一般的树
转换后的二叉树【树转二叉树】考点六: 树、森林和二叉树的关系
将一棵树转换为二叉树的方法是
(1)加线——树中所有相邻兄弟之间加一条连线
(2)去线——对树中的每个结点,只保留它与第一个孩子结点之间的
连线,删去它与其它孩子结点之间的连线。
(3)层次调整——以根结点为轴心,将树顺时针转动一定的角度,使
之层次分明。 A
B C D
E F G考点六: 树、森林和二叉树的关系
将一棵树转换为二叉树的方法是
A
(1)加线——树中所有相邻兄弟之间加一条连线
B
(2)去线——对树中的每个结点,只保留它与第
一个孩子结点之间的连线,删去它与其它孩子结点
之间的连线。 E C
(3)层次调整——以根结点为轴心,将树顺时针
F D
转动一定的角度,使之层次分明。 【左孩右兄】
G考点六: 树、森林和二叉树的关系
A
A
B
B C D
E C
E F G
F D
树的前序遍历等价于二叉树的前序遍历!
G
树的后序遍历等价于二叉树的中序遍历!考点六: 树、森林和二叉树的关系
A
A
B
B C D
E C
E F G
树的根结点没有兄弟 F D
G
二叉树根结点的右子树必为空【二叉树转树】考点六: 树、森林和二叉树的关系
A
将一棵二叉树还原为树,具体转换方法是
(1)加线——若某结点 x是其双亲 y的左 B
孩子,则把结点 x的右孩子、右孩子的右孩
子、……,与结点 y连线 E C
(2)去线——删去所有双亲结点与右孩子
F D
结点的连线
A
(3)层次调整——整理由(1)、(2)两
G
步所得到的树(森林),使之层次分明。
B C D
E F G【森林转二叉树】考点六: 树、森林和二叉树的关系
将一个森林转换为二叉树的方法是
(1)将森林中的每棵树转换为二叉树
(2)将每棵树的根结点视为兄弟,在所有根结点之间加上连线
(3)按照二叉树结点之间的关系进行层次调整
A C G
D E F H I
B
J考点六: 树、森林和二叉树的关系
A
A C G
B C
D E F H I
B
J D G
A C G
E H
B D H F I
E I
J
F J【二叉树转森林】考点六: 树、森林和二叉树的关系
具体的还原步骤。
① 去连线。将二叉树B的根结点与其右子结点以及沿右子结点链方
向的所有右子结点的连线全部去掉,得到若干棵孤立的二叉树,每
一棵就是原来森林F中的树依次对应的二叉树,如图(b)所示。
② 二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法
还原成一般的树,如图(c)所示。考点六: 树、森林和二叉树的关系
二叉树还原成森林的过程
A
A
B G
B G
C L M C L M
D H K D H K
(a) 二叉树
(b) 去连线后考点六: 树、森林和二叉树的关系
二叉树还原成森林的过程
A
A
B G
B G
C L M C L M
D H K D H K
(a) 二叉树
(b) 去连线后
A G M
B C L K
D H
(c) 还原成森林【树和森林的遍历】考点六: 树、森林和二叉树的关系
1、树的遍历
由树结构的定义可知,树的遍历有二种方法。
⑴ 先序遍历:先访问根结点,然后依次先序遍历完每棵子树。如图的
树,先序遍历的次序是:ABCDEFGIJHK
⑵ 后序遍历:先依次后序遍历完每棵子树,然后访问根结点。如图的
树,后序遍历的次序是:CDBFIJGHEKA考点六: 树、森林和二叉树的关系
1、树的遍历
说明:(这个需要记住,考试直接考)
◆ 树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。
◆ 树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。考点六: 树、森林和二叉树的关系
2、森林的遍历
 森林的先序遍历步骤:森林的先序遍历顺序即按照森林的每棵树的顺
序,对每一棵树进行先根遍历。
 森林的中序遍历步骤:森林的先序遍历顺序即按照森林的每棵树的顺
序,对每一棵树进行后根遍历。考点六: 树、森林和二叉树的关系
3、二叉树、树、森林之间的遍历关系如表所示THANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架
哈夫曼树的概念
哈夫曼树的构造
哈夫曼树的编码【哈夫曼树的概念】考点七: 哈夫曼树
编码:是将一个符号或一组符号通过某种规则转换成另一种符号或
符号组合的过程,是信息传递的基础。编码的作用是将信息从一个
形式转换为另一个形式,使其能够被传递、处理、存储与使用。考点七: 哈夫曼树
我们假设只发送A,B,C,D四个字母,那么直接发送A,B,C,D
是不可行的,为什么呢,我们知道字母在计算机中是8位来表示的,如
果直接发送A,B,C,D。
我们知道对信息进行表示的目的是区分信息,根据编码的原理,我
们可以A编码为00,B编码为01,C编码为10,D编码为11;
于是我们想发送的是10个A,5个B,3个C,2个D,那么一共要发
送的比特是10*2 + 5 * 2 + 3 * 2 + 20* 2 = 40bits(每个字母2个bits,
其二进制的表达是00 00 00 00 00 00 00 00 00 00 01 01 01 01 01 10
10 10 11 11)。考点七: 哈夫曼树
基本概念
① 结点路径:从树中一个结点到另一个结点的之间的分支构成这两个
结点之间的路径。
② 路径长度:结点路径上的分支数目称为路径长度。
③ 权(值):各种开销、代价、频度等的抽象称呼。考点七: 哈夫曼树
基本概念
④ 结点的带权路径长度:从该结点的到树的根结点之间的路径长度
与结点的权(值)的乘积
A
B G
C L M
D H K 2 3 6 7考点七: 哈夫曼树
基本概念
⑤ 二叉树的带权路径长度:从根结点到各个叶子结点的路径长度与相应
叶子结点权值的乘积之和
k

n
= 1
w
k
l
k 从根结点到第k个叶子的路径长度
第k个叶子的权值考点七: 哈夫曼树
基本概念
⑤ 二叉树的带权路径长度:从根结点到各个叶子结点的路径长度与相应
叶子结点权值的乘积之和考点七: 哈夫曼树
基本概念
⑤ 二叉树的带权路径长度:从根结点到各个叶子结点的路径长度与相应叶
子结点权值的乘积之和
1
2 3
WPL = (2+3)×2 + 1×1=11考点七: 哈夫曼树
基本概念
⑥ Huffman树:具有n个叶子结点(每个结点的权值为wi) 的二叉树不止
一棵,但在所有的这些二叉树中,必定存在一棵WPL值最小的树,称这
棵树为Huffman树(或称最优树) 。考点七: 哈夫曼树
基本概念
如图是权值分别为2、3、6、7,具有4个叶子结点的二叉树,它们的带
权路径长度分别为:
(a) WPL=22+32+62+72=36 ;
(b) WPL=21+32+63+73=47 ;
(c) WPL=71+62+23+33=34 。
其中(c)的 WPL值最小,可以证明是Huffman树。
7
2
6
2 3 6 7 3
2 3
6 7考点七: 哈夫曼树
基本概念
最优二叉树的特点
(1)权值越大的叶子结点越靠近根结点
(2)只有度为 0 和度为 2 的结点,不存在度为 1 的结点
7
2
6
2 3 6 7 3
2 3
6 7【哈夫曼树的构造】考点七: 哈夫曼树
树的带权路径长度:树中所有叶子结点的带权路径长度之和,记做:
WPL=w l+w l+⋯+w l =∑w l (i=1,2,⋯,n)
1 1 2 2 n n i i
n
 w l
k k 从根结点到第k个叶子的路径长度
k =1
第k个叶子的权值考点七: 哈夫曼树
构造哈夫曼树的原则:
权值越大的叶结点越靠近根结点。
权值越小的叶结点越远离根结点。
n
 w l
k k 从根结点到第k个叶子的路径长度
k =1
第k个叶子的权值 一般情况下,w >> l, w是带头大哥考点七: 哈夫曼树
• 根据树高度的定义,如果路径长度长一些,那么对应结点的高度就高
一些,在树中就靠下一些;反之就靠上一些;
• 对应的,出现次数少(权重小的)的结点高度高(在树中靠下),出
现次数多(权重大的)的结点高度低(在树中靠上)。
也就是说 w大的,l小;w小的,l大。考点七: 哈夫曼树
构造哈夫曼树的过程:
(1)给定的n0个权值{W1,W2,…,Wn0},构造n0棵只有一
个叶结点的二叉树,从而得到一个二叉树的集合F={T1,T2,…,
Tn0}。
(2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、
右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、
右子树根结点权值之和。
(3)在F中用新得到的二叉树代替这两棵树。
(4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵
二叉树便是所要建立的哈夫曼树。考点七: 哈夫曼树
图是权值集合W={8, 3, 4, 6, 5, 5}构造Huffman树的过程。所构造的
Huffman树的WPL是: WPL=62+33+43+82+53+53 =79
5 5 6 7 8
3 4 5 5 6 8
3 4
第一步
第二步
6 7 8 10 8 10 13
3 4 5 5 5 5 6 7
第三步
3 4
第四步
Huffman树的构造过程考点七: 哈夫曼树
图是权值集合W={8, 3, 4, 6, 5, 5}构造Huffman树的过程。所构
造的Huffman树的WPL是:
WPL=62+33+43+82+53+53 =79
31
13 18
13 18
6 7 8 10
6 7 8 10
3 4 5 5
3 4 5 5
第五步
第六步
Huffman树的构造过程考点七: 哈夫曼树
构造Huffman树时,为了规范,规定F={T ,T , ⋯,T }中权值小的二叉
1 2 n
树作为新构造的二叉树的左子树,权值大的二叉树作为新构造的二叉树
的右子树;
在取值相等时,深度小的二叉树作为新构造的二叉树的左子树,深度大
的二叉树作为新构造的二叉树的右子树。考点七: 哈夫曼树
因为每次两棵树合并, n个叶子结点
合并 n-1 次 n-1个分支结点
哈夫曼树共有 2n-1个结点【哈夫曼树的编码】考点七: 哈夫曼树
编码:给每一个对象标记一个二进制位串来表示一组对象
等长编码:用长度相等的二进制位串表示一组对象
酸 甜 酸 甜 苦 辣 酸 甜 苦 辣 咸 麻
0 1 00 01 10 11 000 001 010 011 100 101
省 市 区 出生日期 顺序 校验
身份证号码 22 01 04 19870126 444 7
编码的目的是什么? 数字化 编码效率取决于编码长度
如果每个对象的使用频率不等,如何获得较高的编码效率?考点七: 哈夫曼树
不等长编码:表示一组对象的二进制位串的长度不相等
设计不等长编码时,必须考虑解码的唯一性
一组对象 A B C D E
使用频率 35 25 15 15 10
AABACD
不等长编码 0 1 01 10 11
0 0 100110
00100110
0 01 00110考点七: 哈夫曼树
不等长编码:表示一组对象的二进制位串的长度不相等
设计不等长编码时,必须考虑解码的唯一性
层次路径的概念,从根结点开始,到达某结点p所经过的所有结点
称为结点p的层次路径。
请注意每个叶子节点的层次路径有且仅有一条,且相互之间不会
出现前缀。考点七: 哈夫曼树
哈夫曼编码
规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点
所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的
编码称为哈夫曼编码。
哈夫曼编码属0、1
二进制编码
权值越大的字符编码越短,反之越长。考点七: 哈夫曼树
哈夫曼编码
在一组字符的哈夫曼编码中,不可能出现一个字符的哈夫曼编码是另一
个字符哈夫曼编码的前缀。
例如,有4个字符的编码如下:
100,001,0,1 ×
这是哈夫曼编码吗?
每个叶子节点的层次路径有且仅有一
条,且相互之间不会出现前缀。
哈夫曼编码也称为前缀编码。考点七: 哈夫曼树
如何设计一个编码效率最高的前缀编码呢 ? 哈夫曼编码
例:一组字符{A, B, C, D, E, F, G}出现的频率分别是{9, 11, 5, 7, 8, 2, 3}
,设计最经济的编码方案
45
哈夫曼编码方案: 0 1
A:00
19 26
B:10
0 1 0 1
C:010
D:110 9 10 11 15
E:111 A 0 1 B 0 1
F:0110
5 5 7 8
G:0111
C 0 1 D E
2 3
F G考点七: 哈夫曼树
如何设计一个编码效率最高的前缀编码呢 ? 哈夫曼编码
例:一组字符{A, B, C, D, E, F, G}出现的频率分别是{9, 11, 5, 7, 8, 2, 3}
,设计最经济的编码方案
45
0 1
哈夫曼编码方案:
A:00 19 26
0 1 0 1
B:10
C:010 9 10 11 15
D:110 A 0 1 B 0 1
E:111 5 5 7 8
F:0110 C 0 1 D E
等长编码的长度:3
G:0111 2 3
F G
哈夫曼编码的平均长度:
(2×9+3×5+4×2+4×3+2×11+3×7+3×8)/45= 2.67考点七: 哈夫曼树
哈夫曼树的特点
➢ 哈夫曼树只有0度结点和2度结点
➢ 哈夫曼树的WPL值最小
➢ 哈夫曼树不唯一,因为哈夫曼树的左右子树可以交换,但是WPL值唯一
➢ 哈夫曼树本质上不属于二叉树,但是考试中我们认为哈夫曼树是二叉树
➢ 哈夫曼树的上层结点权值不小于下层结点的权值
➢ 哈夫曼编码只讨论叶子的编码【政哥题型总结】考点七: 哈夫曼树
1.设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有( )个结点。
A.13 B.12 C.26 D.25考点七: 哈夫曼树
1.设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有( )个结点。
A.13 B.12 C.26 D.25
D【解析】哈夫曼树只有度为0的结点和度为2的结点。所以给定n =13,那么
0
n =12,于是一共有25个结点。
2考点七: 哈夫曼树
2.有5个字符,根据其使用频率设计对应的哈夫曼编码,( )是不可能的哈夫
曼编码。
A.000,001,010,011,1 B.0000,0001,001,01,1
C.000,001,01,10,11 D.00,100,101,110,111考点七: 哈夫曼树
2.有5个字符,根据其使用频率设计对应的哈夫曼编码,( )是不可能的哈夫
曼编码。
A.000,001,010,011,1 B.0000,0001,001,01,1
C.000,001,01,10,11 D.00,100,101,110,111
D【解析】对于这种题目,有两种方法:第一种是查看是否符合前缀编码的定
义:在一组字符的哈夫曼编码中,不可能出现一个字符的哈夫曼编码是另一
个字符哈夫曼编码的前缀。考点七: 哈夫曼树
2.有5个字符,根据其使用频率设计对应的哈夫曼编码,( )是不可能的哈夫
曼编码。
A.000,001,010,011,1 B.0000,0001,001,01,1
C.000,001,01,10,11 D.00,100,101,110,111
D【解析】第二种是把哈夫曼树构造出来,查看违例,规则是哈夫曼树只有度
为0的结点和度为2的结点。通过观察,选项中的编码都符合前缀编码的条件,
需要通过构造哈夫曼树进行确定。根据哈夫曼树的定义,按照左0右1进行哈夫
曼树的构造,得到各个选项的哈夫曼树,
A.000,001,010,011,1考点七: 哈夫曼树
2.有5个字符,根据其使用频率设计对应的哈夫曼编码,( )是不可能的哈夫
曼编码。
A.000,001,010,011,1 B.0000,0001,001,01,1
C.000,001,01,10,11 D.00,100,101,110,111
D【解析】同理可以得到,从D选项对应的图中可以看到,存在度为1的结点,
所以不符合哈夫曼树的性质。考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后
计算它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
2 3 6 9 14 15 16 17 5 6 9 14 15 16 17
第一步 2 3
第二步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
9 11 14 15 16 17
5 6 9 14 15 16 17
5 6
2 3
第二步
2 3
第三步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
9 11 14 15 16 17 14 15 16 17 20
9 11
5 6
5 6
2 3
第三步
2 3
第四步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
16 17 20 29
14 15 16 17 20
9 11
9 11 14 15
5 6
5 6
2 3
2 3
第四步
第五步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
20 29 33
16 17 20 29
9 11
9 11 14 15 16 17
14 15
5 6
5 6
2 3
2 3
第五步 第六步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
49
20 29 33
20 29 33
9 11
14 15 16 17
9 11
14 15 16 17
5 6
5 6
2 3
2 3
第六步
第七步考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
82
49
33
49
20 29 33
16 17
20 29
9 11
14 15 16 17
9 11
14 15
5 6
5 6
第七步
2 3
第八步
2 3考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
82 根据构造的哈夫曼树,得到WPL的值为
33
49 16×2+17×2+9×3+14×3+15×3+6×4
16 17
20 29 +2×5+3×5=229
9 11
14 15
5 6
2 3考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
平均编码长度:编码一个字符需要几个比特。
82
本题中,一共有82个字符,共需要229个比特,
33
49
因此平均编码长度是229/82。
16 17
20 29
9 11
14 15
5 6
2
3考点七: 哈夫曼树
3.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这些权值集合构造一
棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
A.129 B.219 C.189 D.229
D 【解析】要求哈夫曼树的带权路径长度,需要先把这棵树构造出来,然后计算
它的WPL值。根据哈夫曼树的构造方法,其构造步骤如下:
2, 3 ,6, 9, 14, 15, 16, 17
82 平均编码长度:编码一个字符需要几个比特。
33
49 推广到一般:
16 17
20 29 (1)平均编码长度 = WPL/σ𝑤
(2)当σ𝑤 = 1时,WPL=平均编码长度
9 11
14 15
5 6
2
3THANKSCON T EN T S
目录
考点一 基本术语 ★
考点二 树的性质和存储 ★★★
考点三 二叉树 ★★★★★
考点四 二叉树的遍历 ★★★★★
考点五 线索二叉树 ★★
考点六 树、森林和二叉树的关系 ★★★★
考点七 哈夫曼树 ★★★★★
考点八 并查集考点框架
定义
并查集的操作
并查集的实现【并查集的定义】考点八: 并查集
 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,他主要用
于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小
生成树的Kruskal算法和求最近公共祖先(Least Common Ancestors,
LCA)等
 使用并查集时,首先会存在一组不相交的动态集合 S={S , S ,⋯,S },一般都
1 2 k
会使用一个整数表示集合中的一个元素。考点八: 并查集
 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为
代表。每个集合中具体包含了哪些元素是不关心的,具体选择哪个
元素作为代表一般也是不关心的。我们关心的是,对于给定的元素,
可以很快的找到这个元素所在的集合(的代表),以及合并两个元
素所在的集合,而且这些操作的时间复杂度都是常数级的。考点八: 并查集
◼ 并查集的数据结构记录了一组动态集合S={S , S ,⋯,S } 。
1 2 k
◼ 每个动态集合S (1≤i≤k)通过一个“代表”加以标识,该代表即
i
为所代表的集合中的某个元素。对于集合S ,选取其中哪个元素作
i
为代表是任意的。【并查集的操作】考点八: 并查集
并查集的基本操作有三个:
 InitUFS(s):建立一个新的并查集,其中包含s个单元素集合
 Union (x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在
的集合不相交,如果相交则不合并。
 Find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两
个元素是否位于同一个集合,只要将他们各自的代表比较一下就可以
了。考点八: 并查集
用有根树来表示一个集合。多个集合形成一个森林,以每棵树的树根作
为集合的代表,并且根结点的父结点指向其自身,树上的其他结点都用
一个父指针表示它的附属关系。
4
3 2
1
{1,2,3,4}集合考点八: 并查集
用数组存放:t[i]对应i结点
4
3 2
1
{1,2,3,4}集合考点八: 并查集
4
3
4
2
3 2
1
1
{1,2,3,4}集合
{1,2,3,4}集合
查找1所在的集合:3次比较 查找1所在的集合:4次比较
树高度越小越好考点八: 并查集
初始状态 {1},{2},{3},{4},{5},{6},{7},{8},{9},{10}
parent
1 2 3 4 5 6 7 8 9 10
(2,4) {1},{2,4},{3},{5},{6},{7},{8},{9},{10}
1 3 4
5 6 7 8 9 10
2考点八: 并查集
1 3 4
5 6 7 8 9 10
2
(5,7) {1},{2,4},{3},{5,7},{6},{8},{9},{10}
7
1 3 4
6 8 9 10
2 5考点八: 并查集
1 3 4
6 7 8 9 10
2
5
(1,3) {1,3},{2,4},{5,7},{6},{8},{9},{10}
6 7 8 9 10
3
4
5
1 2考点八: 并查集
6 7 8 9 10
3
4
5
1 2
(8,9) {1,3},{2,4},{5,7},{6},{8,9},{10}
9
6 7 10
3
4
5 8
1 2考点八: 并查集
3 9
4 6 7 10
1 2 5 8
(1,2) {1,2,3,4},{5,7},{6},{8,9},{10}
4
9
6 7 10
2 4
5 8
3 2 3
1 1考点八: 并查集
如何保证A(根为a)和B(根为b)合并的树高度较低呢?
⚫ A和B的高度相同时,a作为b的孩子或者b作为a的孩子均可  合并树高度
=hA+1=hB+1。
⚫ A和B的高度不相同时,将较低的根作为较高根的孩子  合并树高度
=max(hA,hB)。
4
3
4
2 3
1 2
1考点八: 并查集
A A
B x B
x
4
4
2 3 1
2 3
1【并查集的实现】考点八: 并查集
1、结构体定义
为了方便,采用顺序方法存储森林,结点的类型声明如下:
typedef string ElemType;
typedef struct {
ElemType data; // 数据域
int rank; // 秩,用于启发式合并
int parent; // 父节点的下标
} UFSNode;
typedef struct {
UFSNode* nodes;
int size;
} UFSTree;考点八: 并查集
2、初始化并查集
建立一个存放并查集树的数组t.nodes,初始化每个结点的数据域data
为数组a的对应元素,rank值设置为0,parent值设置为自己。算法如下:考点八: 并查集
// 初始化并查集
bool InitUFS(UFSTree& t, ElemType a[], int n) {
if (n <= 0) {
return false;
}
t.nodes = (UFSNode*)malloc(sizeof(UFSNode) * n);
if (!t.nodes) {
return false;
}
t.size = n;
for (int i = 0; i < n; ++i) {
t.nodes[i].data = a[i]; // 初始化数据域
t.nodes[i].rank = 0; // 秩初始为0
t.nodes[i].parent = i; // 父节点初始为自身
}
return true;
}考点八: 并查集
3、查找一个元素所属的集合
 元素所属的集合,就在分离集合森林中,每一棵分离集合树对应一个
集合。如果要查找某是要找这个元素对应的结点所在的分离集合树一
个结点所在的分离
 不妨以分离集合树的根结点的编号来标识这个分离集合树,这样查找
集合树也就是查找该结点所在分离集合树的根结点。查找树的根结点
的方法很简单,找的那个结点),沿双只需任取树中的一个结点(不妨取
要查双亲结点为基点,走亲结点方向一直往树根走。
 初始时,取一个结点,走到它的双亲结点,然后以一个没有双亲结点
的结点为止,这个给到双亲结点的双亲结点,,直至走到点就是树的
根结点考点八: 并查集
// 在并查集中查找下标为i的元素所在集合根节点的下标
int Find(UFSTree& t, int i) {
if (i < 0 || i >= t.size) {
return -1; // 下标越界
}
if (t.nodes[i].parent != i) {
return Find(t, t.nodes[i].parent);
}
return i;
}
对于n个元素,构成的分离集合树的高度最高为log n,
2
所以本算法的时间复杂度为O(log n)。
2考点八: 并查集
4、两个元素各自所属的集合的合并
在进行合并的时候,只需要让具有较小秩的根指向具有较大秩的根。如果
两根的秩相等,只需要使其中一个根指向另一个,同时秩增加1。考点八: 并查集
bool Union(UFSTree& t, int i, int j) {
i = Find(t, i); // 查找i所在集合的根节点下标
j = Find(t, j); // 查找j所在集合的根节点下标
if (i == -1 || j == -1) {
return false; // 下标越界
}
if (i == j) {
return true; // 两个元素已经在同一个集合中
}
// 将秩小的集合合并到秩大的集合中
if (t.nodes[i].rank < t.nodes[j].rank) {
t.nodes[i].parent = j;
} else if (t.nodes[i].rank > t.nodes[j].rank) {
t.nodes[j].parent = i;
} else { // 两个集合的秩相等
t.nodes[j].parent = i; // 将j所在集合合并到i所在集合中
++t.nodes[i].rank; // i的秩加1
}
return true;
对于n个元素,本算法的时间复杂度为O(log n)。
} 2THANKS