数据结构概论 第6章 树和二叉树 董黎刚 浙江工商大学信电学院.

Presentation on theme: "数据结构概论 第6章 树和二叉树 董黎刚 浙江工商大学信电学院."— Presentation transcript:

1 数据结构概论 第6章 树和二叉树 董黎刚 浙江工商大学信电学院

2 1. 树的定义 和基本术语

3 6.1.1 背景 从本章开始讲非线性结构。 树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。
它非常类似（注意不是完全一样）于自然界中的树。 6.1 树的定义和基本术语

4 6.1.1 背景 树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用，例如
在编译程序中，用树来表示源程序的语法结构； 在数据库系统中，可用树来组织信息； 在分析算法的行为时，可用树来描述其执行过程。 6.1 树的定义和基本术语

5 6.1.2 树的定义 树（Tree）是n（n≥0）个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：
必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。 其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树(Subtree)。 6.1 树的定义和基本术语

6 6.1.2 树的四种表示法 倒置树结构 （树形表示法） 文氏图(维恩图)表示法 （嵌套集合形式） 6.1 树的定义和基本术语

7 6.1.2 树的四种表示法 广义表形式 (A(B(E,F(I,J)),C,D(G,H))) （嵌套括号表示法） 凹入表示法 A———————
6.1 树的定义和基本术语

8 6.1.3 树的相关术语 结点（Node）：包含一个数据元素及若干指向其它结点的分支信息。
结点的度（Degree）：一个结点的子树个数（也就是孩子的个数）。 叶子结点（Leaf，也称为终端结点,非分支结点）。度为0的结点，即无子树的结点。 分支结点（也称为非终端结点）：度不为0的结点。 6.1 树的定义和基本术语

9 6.1.3 树的相关术语 孩子结点（Child）：一个结点的直接后继。 双亲结点（Parent）：一个结点的直接前驱。
兄弟结点（Sibling）：同一双亲结点的孩子结点之间互称兄弟结点。 A的度是3，C的度是1 K、L、F、G、I、J和M是叶子结点，其他是分支结点 B、C和D都是A的孩子结点 A是B、C和D的双亲结点 B、C和D互为兄弟结点 6.1 树的定义和基本术语

10 6.1.3 树的相关术语 路径（Path）。若树中存在一个结点序列k1，k2，…，kj，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从k1到kj的一条路径或道路。 路径长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。从树的根结点到树中其余结点均存在一条惟一的路径。 祖先结点（Ancestor）：从根结点到该结点的路径上的所有结点 子孙结点：一个结点的直接后继和间接后继。 6.1 树的定义和基本术语

11 6.1.3 树的相关术语 树的度：树中所有结点的度的最大值
结点的层次（Level）。从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。注意，也有些文献把根结点的层次定为0。 树的高度（深度）（Height）：树中所有结点的层次的最大值。 有序树（Ordered Tree）。在树T中，如果各子树Ti之间是有先后次序的，则称为有序树，否则为无序树(Unordered Tree)。 6.1 树的定义和基本术语

12 6.1.3 树的相关术语 森林（Forest）。m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点（比如下面的结点A）删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。 A、B和E都是K的祖先结点 K是A、B和E的子孙结点 树的度是3 A的层次是1，M的层次是4 树的高度（深度）是4 6.1 树的定义和基本术语

13 6.1.4 操作 线性表 树 初始化 InitList(L) InitTree(T) CreateTree(T)－按照输入创建树 销毁
DestroyList(L) DestoryTree(T) 清空 ClearList(L) 判空 IsTreeEmpty() 求长度 ListLength(L) 求结点 GetNode(L，i) Root(T) , FirstChild(T，x), NextSibling(T，x) , Parent(T，x) 求位置 LocateNode(L，x) 插入 InsertList(L，x，i) InsertChild(T，p，Child) 删掉 DeleteList(L，i) DeleteChild(T，p，i) 遍历 TraverseTree(T，Visit()) 6.1 树的定义和基本术语

14 2. 二叉树的定义

15 6.2.1 背景 树比较复杂，无法直接使用。为此，我们先研究另一种比较简单的、特殊的树形结构——二叉树。
如果我们能操作二叉树，而且又能实现二叉树到树的转换，那么就能操作树了。 6.2 二叉树的定义

16 6.2.2 定义 满足以下两个条件的树形结构叫做二叉树（Binary Tree）： 每个结点的度都不大于2；
每个结点的孩子结点次序不能任意颠倒。 我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。 6.2 二叉树的定义

17 6.2.2 定义 二叉树的五种基本形态 6.2 二叉树的定义

18 6.2.2 定义 二叉树与度数为2的有序树相同吗？ 有序树中，虽然孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。
而在二叉树中，即使是一个孩子也有左右之分。 可见，二叉树并非是树的特殊情形，它们是两种不同的数据结构。 6.2 二叉树的定义

19 6.2.2 定义 满二叉树（Full Binary Tree）：每层结点都具有最大结点数。
6.2 二叉树的定义

20 6.2.2 定义 完全二叉树（Complete Binary Tree）：对于满二叉树，从最低一层开始，按照编号反序删除零个或多个结点。
满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。 6.2 二叉树的定义

21 6.2.3 操作 树 二叉树 初始化 InitTree(T), CreateTree(T) Initiate(bt)，Create(bt)
销毁 DestoryTree(T) Destory(bt) 清空 Clear(bt) 判空 TreeEmpty() IsEmpty(bt) 求结点 Root(T), Parent(T，x)， FirstChild(T，x), NextSibling(T，x) Root(bt)，Parent(bt，x)，LeftChild(bt，x)，RightChild(bt，x) 插入 InsertChild(T，p，Child) 删掉 DeleteChild(T，p，i) 遍历 TraverseTree(T，Visit()) Traverse(bt) 6.2 二叉树的定义

22 3. 二叉树的性质（1）

23 6.3.1 背景 二叉树比较特殊，研究人员总结出了二叉树的5个性质。 每一层上的结点数 整个二叉树的结点数 度为2的结点数和叶子数的关系
n个结点的完全二叉树的深度 完全二叉树中结点编号规律 学习这些性质，不要记忆，而是要学会推导方法。 6.3 二叉树的性质（1）

24 6.3.2 性质1 性质1实例 在二叉树的第1层上至多有2i-1=20=1个结点； 在二叉树的第2层上至多有2i-1=21=2个结点；
6.3 二叉树的性质（1）

25 6.3.2 性质1 性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1)。 证明：用数学归纳法。
假设i=k时结论成立，即第k层上结点总数最多为2k-1个。 现证明当i=k+1时结论成立：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。 6.3 二叉树的性质（1）

26 6.3.3 性质2 性质2实例 深度为1的二叉树至多有2k-1=21-1=1个结点； 深度为2的二叉树至多有2k-1=22-1=3个结点；
6.3 二叉树的性质（1）

27 6.3.3 性质2 性质2: 深度为k的二叉树至多有2k-1个结点(k≥1)。
故结论成立。 6.3 二叉树的性质（1）

28 6.3.4 性质3 性质3实例 叶子结点数为n0=8，而其度数为2的结点数为n2=7，满足n0=n2+1。
可以这样理解：度为1的结点贡献了1个分支，同时消耗了1个分支。而度为2的结点贡献了2个分支，同时消耗了1个分支，叶子结点没有贡献分支，却消耗了1个分支，其消耗的分支是由度为2的结点贡献的，因此他们应该是1:1的关系。再加上根少消耗1个分支，因此叶子数比度为2的结点多1个。 6.3 二叉树的性质（1）

29 6.3.4 性质3 性质3: 对任意一棵二叉树T，若叶子结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。
证明：（1）二叉树中结点总数为n，n1为二叉树中度为1的结点数。n=n0+n1+n2。 （2）二叉树中分支数为B=n1+2n2。因为度为2的结点产生2个分支，度为1的结点产生1个分支。 （3）结点数和分支数的关系是n=B+1，因为除根结点外，每个结点均对应一个“拉住”它的分支。 （4）把（1）和（2）代入（3），得到 n0+n1+n2=n=B+1=n1+2n2+1。 整理后得n0=n2+1。 6.3 二叉树的性质（1）

30 4. 二叉树的性质（2）

31 6.4.1 背景 现在学习最后2个性质： n个结点的完全二叉树的深度 完全二叉树中结点编号规律 6.4 二叉树的性质（2）

32 6.4.2 性质4 性质4实例 具有13个结点的完全二叉树的深度为log2n+1=log213+1=4。
其中，  表示向下取整。 6.4 二叉树的性质（2）

33 6.4.2 性质4 性质4: 具有n个结点的完全二叉树的深度为log2n+1。( 表示向下取整)
证明：假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为n1=2k-1-1。k层满二叉树的结点总数为n2=2k-1 显然有n1<n≤n2，进一步可以推出n1+1≤n<n2+1。 将n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。 因为k是整数，所以k-1=log2n，k=log2n+1, 故结论成立。 6.4 二叉树的性质（2）

34 6.4.2 性质4 性质4的 另一种形式: 具有n个结点的完全二叉树的深度为 log2 (n+1)  。( 表示向上取整)
证明：假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为n1=2k-1-1。k层满二叉树的结点总数为n2=2k-1 显然有n1<n≤n2。 将n1=2k-1-1和n2=2k-1代入上式，可得2k-1<n+1 ≤ 2k，即k-1<log2(n+1)≤k。 因为k是整数，所以k=  log2 (n+1) , 故结论成立。 6.4 二叉树的性质（2）

35 6.4.3 性质5 性质5实例 比如结点5的双亲为i/2=5/2=2。结点5的左孩子结点是2×i=2×5=10，右孩子结点是2×i+1=2×5+1=11。 6.4 二叉树的性质（2）

36 6.4.3 性质5 性质5: 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有： （1）如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为i/2。 （2）如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。 （3）如2×i＋1>n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。 6.4 二叉树的性质（2）

37 6.4.3 性质5 证明：可以用数学归纳法证明其中的（2）和（3）：
当i=1时，如果2×i=2≤n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2；反之，如果2>n，说明二叉树中不存在序号为2的结点，其左孩子不存在。 同理，如果2×i+1=3≤n，说明其右孩子存在且序号为3；如果3>n，则二叉树中不存在序号为3的结点，其右孩子不存在。 6.4 二叉树的性质（2）

38 6.4.3 性质5 假设：对于结点j(1≤j≤i)， 当2×j≤n时，其左孩子存在且序号为2×j，当2×j>n 时，其左孩子不存在；
6.4 二叉树的性质（2）

39 6.4.3 性质5 当i=j+1时，n≥2×i=2(j+1)= 2×j+2，2×j是结点j的左孩子，由图可知2×j+2是结点i的左孩子。如果n<2×i=2×j+2，由图可知结点i没有左孩子。 n≥2×i＋1=2(j+1)＋1=(2×j+1)＋2，2×j+1是结点的右孩子，由图可知(2×j+1)＋2是结点i的右孩子。如果n<2×i＋1=(2×j＋1)+2，由图可知结点i没有右孩子。 故（2）和（3）得证。 6.4 二叉树的性质（2）

40 6.4.3 性质5 由（2）和（3）我们可以很容易证明（1）。 当i=1时，显然该结点为根结点，无双亲结点。
当i>1时，设结点i的双亲结点的序号为m 如果结点i是其双亲结点的左孩子，根据（2）有i=2×m，即m=i/2; 如果结点i是其双亲结点的右孩子，根据（3）有i=2×m+1，即m=（i-1）/2=i/2-1/2。 综合这两种情况可知，当i>1时，其双亲结点的序号等于i/2。证毕。 6.4 二叉树的性质（2）

41 5. 二叉树的存储结构

42 6.5.1 背景 二叉树的存储结构有两种：顺序存储结构和链式存储结构。 6.5 二叉树的存储结构

43 6.5.2 二叉树的顺序存储 对于完全二叉树，存储比较简单。从根开始，层间从上到下，层内从左到右，逐层进行编号；将结点按编号存入顺序存储结构
6.5 二叉树的存储结构

44 6.5.2 二叉树的顺序存储 对于非完全二叉树，需要添上一些“虚结点”（这样才能保存每个结点的位置信息），成为“完全二叉树”，其中"虚结点"用"∧"表示。 6.5 二叉树的存储结构

45 6.5.2 二叉树的顺序存储 优点：对完全二叉树而言，顺序存储结构既简单又节省存储空间；
缺点：一般的二叉树采用顺序存储结构时，易造成存储空间的浪费。 6.5 二叉树的存储结构

46 6.5.3 二叉树的链式存储 结点结构：至少包括三个域：数据域、 左孩子域和右孩子域： 为了便于找到父结点，可以增加一个Parent域
LChild Data RChild LChild Data Parent RChild 6.5 二叉树的存储结构

47 6.5.3 二叉树的链式存储 C语言定义： typedef struct Node { DataType data;
struct Node *LChild; struct Node *RChild; }BiTNode,*BiTree; 6.5 二叉树的存储结构

48 可见，空的指针域比使用的指针域还要多2个。
6.5.3 二叉树的链式存储 性质：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的指针域。 证明：分支数目B=n-1，即非空的指针域有n-1个，故空指针域有2n-(n-1)=n+1个。 可见，空的指针域比使用的指针域还要多2个。 6.5 二叉树的存储结构

49 6. 二叉树的遍历

50 6.6.1 背景 二叉树中最重要的操作是遍历 因为遍历是其他操作的基础，如求叶子个数，求二叉树结点总数等操作都会使用“遍历”这个功能。
6.6 二叉树的遍历

51 6.6.2 遍历的概念 二叉树遍历（Traversal） 遍历是指按照一定规律对二叉树中的每个结点进行访问且仅访问一次。
遍历的本质是：通过遍历，把非线性的树结构变成了一个线性结构（数据的访问顺序是线性的）。 6.6 二叉树的遍历

52 6.6.2 遍历的概念 在任一给定结点上，可以按某种次序执行三个操作： 访问结点本身(N)， 遍历该结点的左子树(L)，
遍历该结点的右子树(R)。 以上三种操作有六种执行次序组合：NLR、LNR、LRN、NRL、RNL、RLN。 6.6 二叉树的遍历

53 6.6.2 遍历的概念 前三种次序与后三种次序对称，故只讨论先左后右的前三种次序：
先序/前序/先根遍历（Preorder Traversal） ：访问根，前序遍历左子树，前序遍历右子树 中序/中根遍历（Inorder Traversal）：中序遍历左子树，访问根，中序遍历右子树 后序/后根遍历（Postorder Traversal）：后序遍历左子树，后序遍历右子树，访问根 取名的依据是看根结点数据的访问顺序 6.6 二叉树的遍历

54 6.6.2 遍历的概念 以中序为例 中序访问以A为根的树的左子树，即以B为根的树 中序访问以B为根的树的左子树，该左子树为空 访问B
中序访问以B为根的树的右子树，即以D为根的树 中序访问以D为根的树的左子树，即以F为根的树 访问F 访问D 中序访问以D为根的树的右子树，即以G为根的树 访问G 访问A 中序访问以A为根的树的右子树，即以C为根的树 中序访问以C为根的树的左子树，该左子树为空 访问C 中序访问以C为根的树的右子树，即以E为根的树 中序访问以E为根的树的左子树，该左子树为空 访问E 中序访问以E为根的树的右子树， 即以H为根的树 访问H 6.6 二叉树的遍历

55 6.6.2 遍历的概念 前序遍历：A、B、D、F、G、C、E、H 中序遍历：B、F、D、G、A、C、E、H
后序遍历：F、G、D、B、H、E、C、A 6.6 二叉树的遍历

56 6.6.3 遍历算法 前序遍历算法 void PreOrder(BiTree root) /*前序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ { if(root! =NULL) Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*前序遍历左子树*/ PreOrder(root ->RChild); /*前序遍历右子树*/ } 6.6 二叉树的遍历

57 6.6.3 遍历算法 中序遍历算法 void InOrder(BiTree root) /*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ { if(root! =NULL) InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } 6.6 二叉树的遍历

58 6.6.3 遍历算法 后序遍历算法 void PostOrder(BiTree root) /*后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ { if(root! =NULL) PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ } 6.6 二叉树的遍历

59 6.6.4 根据遍历序列确定二叉树 已知前序遍历序列： ，中序遍历序列： ，求二叉树： 解： 步骤一：由前序遍历序列的第一个结点可知本树的根结点为18。中序遍历序列中，被18分为两个部分【 】，【 】，得到右图。 6.6 二叉树的遍历

60 6.6.4 根据遍历序列确定二叉树 已知前序遍历序列： ，中序遍历序列： ，求二叉树： 步骤二：先考虑18的左子树，即按前序遍历是【 】，按中序遍历是【 】 。从前序遍历序列可知18的左子树的根是14，从中序遍历序列可知， 18的左子树的左子树是【 】，右子树为空。 18的右子树可以类似考虑，得到右图。 6.6 二叉树的遍历

61 6.6.4 根据遍历序列确定二叉树 已知前序遍历序列： ，中序遍历序列： ，求二叉树： 步骤三：考虑14的左子树，即按前序遍历是【 】，按中序遍历是【3 7 11】 。从前序遍历序列可知14的左子树的根是7，从中序遍历序列可知， 14的左子树的左子树是【3 】，右子树为【11】 。22的右子树可以类似考虑，得到右图。 6.6 二叉树的遍历

62 6.6.4 根据遍历序列确定二叉树 规律1：由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树
规律2：由前序和后序序列不能唯一确定一棵二叉树。 6.6 二叉树的遍历

63 6.6.5 用二叉树表示表达式 用中序遍历方式读取3*x*x+x-1/x+5，可得到下图 前序遍历左图，可得前序/前缀表达式（波兰式）:
后序遍历左图，可得后序/后缀表达式（逆波兰式）: 3xx**x+1x/-5+ 6.6 二叉树的遍历

64 7. 二叉树遍历的应用（1）

65 6.7.1 背景 基于二叉树的存储结构，我们尝试通过遍历建立二叉链表表达的树。
另外，在函数参数传递中，偶尔也会出现指针的指针，为什么要用这个？我们通过分析创建二叉链表树的指针图，彻底理解指针的指针的使用目的。 6.7 二叉树遍历的应用（1）

66 6.7.2 应用1:基于遍历序列建立二叉链表 建立二叉链表的动画 6.8 二叉树遍历的应用（2）

67 6.7.2 应用1:基于遍历序列建立二叉链表 实例： 前序遍历序列：AB.DF..G..C.E.H.. （序列中的小圆点表示空指针）
6.8 二叉树遍历的应用（2）

68 6.7.2 应用1:基于遍历序列建立二叉链表 算法 void CreateBiTree(BiTree *bt) { char ch;
ch=getchar(); if(ch==′.′) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)->data=ch; CreateBiTree(&((*bt)->LChild)); CreateBiTree(&((*bt)->RChild)); } 算法 6.8 二叉树遍历的应用（2）

69 6.7.2 程序例 #include<stdio.h> void CreateBiTree(BiTree *bt);
#include<malloc.h> typedef struct Node { char data; struct Node *LChild; struct Node *RChild; }BiTNode,*BiTree; 运行时输入AB.DF..G..C.E.H.. void CreateBiTree(BiTree *bt); main() { BiTree bt0; CreateBiTree(&bt0); } 6.7 二叉树遍历的应用（1）

70 6.7.3 程序的分析 main() { BiTree bt0; CreateBiTree(&bt0);
void CreateBiTree(BiTree *bt)   char ch; ch=getchar();  6.7 二叉树遍历的应用（1）

71 6.7.3 程序的分析 if(ch=='.') *bt=NULL; else {
*bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)->data=ch; 6.7 二叉树遍历的应用（1）

72 CreateBiTree(&((*bt)->LChild));
6.7.3 程序的分析 CreateBiTree(&((*bt)->LChild)); 6.7 二叉树遍历的应用（1）

73 CreateBiTree(&((*bt)->RChild));
6.7.3 程序的分析 CreateBiTree(&((*bt)->RChild)); } 6.7 二叉树遍历的应用（1）

74 8. 二叉树遍历的应用（2）

75 6.8.1 背景 遍历中对根的“访问”指什么？ 与结点相关的所有操作，比如打印输出，计算结点的深度，计算本结点到根的路径等。
遍历的应用，比如 输出二叉树中的结点 输出二叉树中的叶子结点 统计叶子结点数目 6.8 二叉树遍历的应用（2）

76 6.8.2 应用1：输出二叉树中的结点 实例： 输出序列（前序遍历）：ABDHIEJCFG 6.8 二叉树遍历的应用（2）

77 6.8.2 应用1：输出二叉树中的结点 算法思路：可用三种遍历中的任何一种算法完成。 采用前序遍历的实现算法
void PreOrder(BiTree root) /* 前序遍历输出结点*/ { if(root! =NULL) printf(root ->data); /* 输出根结点 */ PreOrder(root ->LChild); /* 前序遍历左子树 */ PreOrder(root ->RChild); /* 前序遍历右子树 */ } 6.8 二叉树遍历的应用（2）

78 6.8.3 应用2：输出二叉树中的叶子 实例： 输出序列（前序遍历）：HIJFG 6.7 二叉树遍历的应用（1）

79 6.8.3 应用2：输出二叉树中的叶子 算法思路：可用三种遍历中的任何一种算法完成。 采用前序遍历的实现算法
void PreOrder(BiTree root) /* 前序遍历输出叶子*/ { if(root! =NULL) if(root ->LChild==NULL && root ->RChild==NULL) printf(root ->data); /* 输出叶子结点 */ PreOrder(root ->LChild); /* 前序遍历左子树 */ PreOrder(root ->RChild); /* 前序遍历右子树 */ } 6.8 二叉树遍历的应用（2）

80 6.8.4 应用3：统计叶子的数量 实例： 输出：5 6.8 二叉树遍历的应用（2）

81 6.8.4 应用3：统计叶子的数量 算法1：用全局变量LeafCount保存叶子结点数目void PreOrder(BiTree root) /* 前序遍历统计叶子数目*/ { if(root! =NULL) if(root ->LChild==NULL && root ->RChild==NULL) LeafCount++; PreOrder(root ->LChild); /* 前序遍历左子树 */ PreOrder(root ->RChild); /* 前序遍历右子树 */ } 6.8 二叉树遍历的应用（2）

82 6.8.4 应用3：统计叶子的数量 算法2：不用全局变量 int Leaf(BiTree root) /*前序遍历统计叶子数目*/ {
int LeafCount; if(root==NULL) LeafCount =0; else if((root->lchild==NULL)&&(root->rchild==NULL)) LeafCount =1; else /* 叶子数为左右子树的叶子数目之和 */ LeafCount =Leaf(root->lchild)+Leaf(root->rchild); return LeafCount; } 6.8 二叉树遍历的应用（2）

83 9. 二叉树遍历的应用（3）

84 6.9.1 背景 遍历的2个应用例子： 求二叉树高度 按树状打印二叉树 6.9 二叉树遍历的应用（3）

85 6.9.2 应用1:求二叉树高度 算法1：后序遍历求二叉树高（不用全局变量） int PostTreeDepth(BiTree bt) {
int hl, hr, max; if(bt! =NULL) hl=PostTreeDepth(bt->LChild); /* 求左子树的深度 */ hr=PostTreeDepth(bt->RChild); /* 求右子树的深度 */ max=hl>hr?hl: hr; /* 得到左、 右子树深度较大者*/ return(max+1); /* 返回树的深度 */ } else return(0); /* 如果是空树，则返回0 */ 6.9 二叉树遍历的应用（3）

86 6.9.2 应用1:求二叉树高度 算法2：前序遍历求二叉树高（用全局变量depth）
void PreTreeDepth(BiTree bt, int h) /* 前序遍历求二叉树bt高度的递归算法，h为bt指向结点所在层次，初值为1*/ { if(bt!=NULL) if(h>depth) depth = h; PreTreeDepth(bt->Lchild, h+1);/* 遍历左子树 */ PreTreeDepth(bt->Rchild, h+1);/* 遍历右子树 */ } 6.9 二叉树遍历的应用（3）

87 6.9.3 应用2:按树状打印二叉树 树状打印的二叉树示意 每行打印一个字母（上例中序列为：CFEADB） 结点层次越深缩进越大
6.9 二叉树遍历的应用（3）

88 6.9.3 应用2:按树状打印二叉树 算法：按竖向树状（逆中序）打印二叉树
void PrintTree(BiTree Boot, int nLayer) { if(Boot= =NULL) return; PrintTree(Boot->pRight, nLayer+1); for(int i=0; i<nLayer; i++) printf(″ ″); printf(″%c\n″, Boot->ch); PrintTree(Boot->pLeft, nLayer+1); } 6.9 二叉树遍历的应用（3）

89 10. 二叉树的 线索化——创建

90 背景 之前我们已经知道：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的指针域。空的比不空的还多。 为此，有人想把这些空间用起来（用于保存遍历过程中结点的前驱、后继信息），从而提出了线索二叉树的概念。 6.10 二叉树的线索化（1）

91 线索二叉树的定义 思路：利用二叉链表中的空指针域，将遍历过程中结点的前驱、后继信息保存下来。为了区别原来的左右孩子指针是指向孩子的指针还是指向前驱/后继的指针（称为线索），需要增设两个线索标志域，如下图所示： Ltag=0: LChild域指示结点的左孩子 Ltag=1: LChild域指示结点的遍历前驱 Rtag=0: RChild域指示结点的右孩子 Rtag=1: RChild域指示结点的遍历后继 6.10 二叉树的线索化（1）

92 6.10.2 线索二叉树的定义 用上述结点结构的二叉链表，称为线索链表。 对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。
线索化了的二叉树称为线索二叉树（Threaded Binary Tree）。 6.10 二叉树的线索化（1）

93 线索二叉树的定义 前序线索二叉树 6.10 二叉树的线索化（1）

94 线索二叉树的定义 中序线索二叉树 6.10 二叉树的线索化（1）

95 线索二叉树的定义 后序线索二叉树 6.10 二叉树的线索化（1）

96 对线索二叉树的评价 线索化是建立结点在相应序列（前、中或后序）中的前驱和后继之间的直接联系。线索的好处是在二叉树遍历时就可以不再用递归（递归运行比较费时）。 设计线索二叉树的动机貌似为了节省空间，实际上并非如此。原因是Ltag/ Rtag也和LChild/RChild一样，被分配4个字节（32位）。 虽然不节省空间，但是如果Ltag和Rtag改成线索（即指向前驱和后继的指针），指针的操作数量就增加了一倍。 6.10 二叉树的线索化（1）

97 6.10.4 线索化算法 算法思路：按某种次序遍历二叉树，在遍历过程中用线索取代空指针。 算法：采用中序遍历进行线索化
void Inthread(BiTree root)/* 对root所指的二叉树进行中序线索化，其中全局变量pre始终指向刚访问过的结点，其初值为NULL* / { if(root! =NULL) Inthread(root->LChild); /* 线索化左子树 */ 6.10 二叉树的线索化（1）

98 6.10.4 线索化算法 if(root->LChild==NULL) { root->Ltag=1;
root->LChild=pre;/ *置前驱线索 */ } if(pre! =NULL&& pre->RChild==NULL) pre->Rtag=1; pre->RChild=root ;/ *置后继线索 */ pre=root; Inthread(root->RChild); /*线索化右子树*/ 6.10 二叉树的线索化（1）

99 线索化算法 采用中序遍历进行线索化的动画 6.10 二叉树的线索化（1）

100 11. 二叉树的 线索化——应用

101 6.11.1 背景 有了线索二叉树，就能不通过递归算法而找到中序遍历的前驱和后继结点。这样的话，操作二叉树时就可以不用递归算法。
6.11 二叉树的线索化（2）

102 在线索二叉树中找中序前驱结点 找中序前驱的动画 6.11 二叉树的线索化（2）

103 在线索二叉树中找中序前驱结点 void InPre(BiTNode *p,BiTNode *pre)/* 在中序线索二叉树中查找p的中序前驱,并用pre指针返回结果 */ { if(p->Ltag==1) pre= p->LChild; /*直接利用线索*/ else/*在p的左子树中查找“最右下端”结点 */ for(q= p->LChild; q->Rtag==0; q=q->RChild) ; pre=q; } 6.11 二叉树的线索化（2）

104 在线索二叉树中找中序后继结点 找中序后继的动画

105 在线索二叉树中找中序后继结点 void InSucc(BiTNode *p,BiTNode *succ) /*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/ { if(p->Rtag==1) succ= p-> RChild; /*直接利用线索*/ else/*在p的右子树中查找“最左下端”结点*/ for(q=p->RChild;q->Ltag==0; q=q->LChild) ; succ=q; } 6.11 二叉树的线索化（2）

106 6.11.4 找结点的前序前驱和后继结点 找结点p的后继比较容易 找结点的前驱比较困难
若p存在左子树，则p的左孩子即为p的后继； 若p没有左子树，但有右子树，则p的右孩子即为p的后继； 若结点p既没有左子树，也没有右子树，则结点p的RChild指针域所指的结点即为p的后继。 找结点的前驱比较困难 除了特殊情况之外，可能要从根开始进行前序遍历才能找到结点P的前序前驱。 线索二叉树对查找指定结点的前序前驱并无帮助。 6.11 二叉树的线索化（2）

107 6.11.5 找结点的后序前驱和后继结点 在后序线索树中查找结点p的前驱很方便，仅从p出发就能找到其后序前驱结点，具体情况略。
但在后序线索树中找结点后继比较困难。线索二叉树对查找指定结点的后序后继并无帮助。 6.11 二叉树的线索化（2）

108 12. 树的存储结构

109 6.12.1 背景 树有三种存储方式 双亲表示法 孩子（链表）表示法 孩子兄弟（链表）表示法 其中最重要的是孩子兄弟（链表）表示法，为什么？
6.12 树的存储结构

110 6.12.2 双亲表示法 双亲表示法适合找到指定结点的双亲或祖先(包括根)，但是不方便查找孩子或其它后代：可能要遍历整个数组。
6.12 树的存储结构

111 6.12.2 双亲表示法 C语言 ＃define MaxTreeSize 100 //树中结点个数的最大数
typedef struct TNode { DataType data; int parent; }TNode;//结点的定义 typedef struct TNode tree[MaxTreeSize]; int nodenum;/*结点数*/ }ParentTree; //树的定义 6.12 树的存储结构

112 6.12.3 孩子（链表）表示法 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。
6.12 树的存储结构

113 孩子（链表）表示法 双亲孩子（链表）表示法 6.12 树的存储结构

114 6.12.3 孩子（链表）表示法 C语言 typedef struct ChildNode /* 孩子链表结点的定义 */ {
int Child; /* 该孩子结点在线性表中的位置 */ struct ChildNode *next; /* 指向下一个孩子结点的指针 */ }ChildNode; typedef struct /* 顺序表结点的结构定义 */ { DataType data; /* 结点的信息 */ ChildNode *FirstChild; /* 指向孩子链表的头指针 */ }DataNode; typedef struct /* 树的定义 */ DataNode nodes[MaxTreeSize]; /* 顺序表 */ int root, num; /* 该树的根结点在线性表中的位置和该树的结点个数 */ } ChildTree; 6.12 树的存储结构

115 6.12.4 孩子兄弟（链表）表示法 C语言 typedef struct CSNode {
DataType data; /*结点信息*/ Struct CSNode *FirstChild,*Nextsibling; /*第一个孩子, 下一个兄弟*/ }CSNode,*CSTree; 6.12 树的存储结构

116 6.12.4 孩子兄弟（链表）表示法 这种存储结构的最大优点是：它是树和二叉树之间转化的纽带，和对应的二叉树的二叉链表表示完全一样。
6.12 树的存储结构

117 13. 树、森林和 二叉树的相互转化

118 6.13.1 背景 通过孩子兄弟（链表）表示法，树或森林与二叉树之间有了一一对应关系。 任何一个森林或树可唯一地对应到一棵二叉树；
反之，任何一棵二叉树也能唯一地对应到一个森林或树。 通过这种对应关系，树或森林的操作能通过转化成二叉树进行。 6.13 树、森林和二叉树的相互转化

119 树转换为二叉树 树/森林与二叉树的转换动画 6.13 树、森林和二叉树的相互转化

120 6.13.2 树转换为二叉树 树中所有相邻兄弟之间加一条连线。
对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。 6.13 树、森林和二叉树的相互转化

121 6.13.2 树转换为二叉树 树的孩子兄弟链表就是对应二叉树的二叉链表 由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
6.13 树、森林和二叉树的相互转化

122 森林转换为二叉树 将森林中的每棵树转换成相应的二叉树。 6.13 树、森林和二叉树的相互转化

123 森林转换为二叉树 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。 6.13 树、森林和二叉树的相互转化

124 6.13.4 二叉树还原为树或森林 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连起来。
6.13 树、森林和二叉树的相互转化

125 二叉树还原为树或森林 删掉原二叉树中所有双亲结点与右孩子结点的连线。 6.13 树、森林和二叉树的相互转化

126 二叉树还原为树或森林 整理上面两步所得到的树或森林，使之结构层次分明。 6.13 树、森林和二叉树的相互转化

127 14. 树和森林的遍历

128 6.14.1 背景 树和森林的遍历就是对应二叉树的遍历。
因此，树和森林的遍历也类似于前序、中序和后序之分，但又有其特殊情况：树的遍历只有两种，而森林的遍历有三种。 6.14 树和森林的遍历

129 6.14.2 树的遍历——先根遍历 步骤 访问根结点。 从左到右，依次先根遍历根结点的每一棵子树。
树的先根遍历等价于前序遍历该树对应的二叉树 6.14 树和森林的遍历

130 6.14.3 树的遍历——后根遍历 步骤 从左到右，依次后根遍历根结点的每一棵子树。 访问根结点。
树的后根遍历等价于中序遍历该树对应的二叉树。为什么？ 因为树中的孩子在对应的二叉树中都在左孩子中。 6.14 树和森林的遍历

131 6.14.4 树的遍历实例 树的先根遍历序列（或对应二叉树的前序遍历序列）为ABECFHGD
树的后根遍历序列（或对应二叉树的中序遍历序列）为EBHFGCDA 6.14 树和森林的遍历

132 6.14.5 森林的遍历——前序遍历 步骤 访问森林中第一棵树的根结点。 前序遍历第一棵树的根结点的子树森林。
前序遍历除去第一棵树之后剩余的树构成的森林。 森林的遍历算法同样适用于树的遍历，因为树是一种特殊的森林。 森林的前序遍历与树的先根遍历实质上是一样的，也等价于前序遍历对应的二叉树。 6.14 树和森林的遍历

133 6.14.5 森林的遍历——前序遍历 算法 void RootFirst(CSTree root) { if(root!=NULL)
Visit(root ->data); /*访问根结点*/ RootFirst(root->FirstChild); /*前序遍历首子树*/ RootFirst(root->Nextsibling);/*前序遍历兄弟树*/ } 6.14 树和森林的遍历

134 6.14.6 森林的遍历——中序遍历 步骤 中序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。 森林的中序遍历与树的后根遍历实质上是一样的，也等价于中序遍历对应的二叉树。 6.14 树和森林的遍历

135 6.14.7 森林的遍历——后序遍历 步骤 后序遍历森林中第一棵树的根结点的子树森林。 后序遍历除去第一棵树之后剩余的树构成的森林。
访问第一棵树的根结点。 森林的后序遍历等价于后序遍历对应的二叉树。 6.14 树和森林的遍历

136 6.14.8 森林的遍历实例 （1）森林的前序遍历序列（或对应二叉树的前序遍历序列）为ABCDEFGHIJ
（2）森林的中序遍历序列（或对应二叉树的中序遍历序列）为BCDAFEHJIG （3）森林的后序遍历序列为（对应二叉树的后序遍历序列）是DCBFJIHGEA 6.14 树和森林的遍历

137 6.14.9 比较 为什么树的遍历只有两种，而森林的遍历有三种？
因为树中没有左右子树之分，遍历时，根要么在所有子树之前，要么在所有子树之后，所以树只有两种遍历方式。 但是可以用森林的后序遍历方法对树进行遍历，会产生树的第三种遍历序列，这等价于对应二叉树的后序遍历序列。 6.14 树和森林的遍历

138 15. 哈夫曼树的相关概念

139 6.15.1 背景 提出哈夫曼树是为设计哈夫曼编码，而哈夫曼编码是为了提高编码效率。
编码（Coding）就是赋予信息元素以代码的过程。即用不同的代码与各种信息中的基本单位部分建立一一对应的关系。 编码是为了方便信息的存储、检索和使用，比如 文件编码后能压缩存储量 姓名编码后产生编号，方便检索/查找 6.15 哈夫曼树的相关概念

140 背景 1951年，David A. Huffman（哈夫曼，1925 – 1999）上MIT的信息论课程时可以选择完成学期报告还是期末考试。 6.15 哈夫曼树的相关概念

141 背景 哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了根据出现的概率来构造二叉树编码的想法，并证明了这个方法是最有效的（即平均长度最短）。这个方法就是哈夫曼编码。该编码方法发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 哈夫曼一生最知名的学术贡献是哈夫曼编码。 6.15 哈夫曼树的相关概念

142 6.15.2 路径和路径长度 路径是指从一个结点到另一个结点之间的结点序列 路径长度是指从一个结点到另一个结点所经过的分支数目。
树的路径长度是从树根到树中每一结点的路径长度之和。 在结点数目相同的二叉树中，完全二叉树的路径长度最短。 6.15 哈夫曼树的相关概念

143 6.15.2 路径和路径长度 结点A和E之间的路径是：ABE 结点A和E之间的路径长度是2
该树的路径长度=A到B的路径长度+ A到C的路径长度+ A到D的路径长度+ A到E的路径长度+ A到F的路径长度+ A到G的路径长度= =10 6.15 哈夫曼树的相关概念

144 6.15.2 路径和路径长度 (a) (b) (c) 上述三棵二叉树的路径长度分别为 PL(a)= 1+1+2+2+2+2=10
PL(b)= =12 PL(c)= =12 可见，在结点数目相同的二叉树中，完全二叉树的路径长度最短。 6.15 哈夫曼树的相关概念

145 路径和路径长度 但是，非完全二叉树也可能有最短路径长度，比如下面两个二叉树具有相同的路径长度。 6.15 哈夫曼树的相关概念

146 6.15.3 带权路径长度 在树形结构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。
树的带权路径长度（Weighted Path Length，WPL）:树中所有叶子结点的带权路径长度之和。注意：不考虑分支结点。 其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。树的带权路径长度亦称为树的代价。 6.15 哈夫曼树的相关概念

147 6.15.3 带权路径长度 (a) (b) (c) (a)中结点A的带权路径长度为2×7=14，其他叶子结点的带权路径长度可以类似计算。
上述三棵二叉树的带权路径长度分别为 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35 6.15 哈夫曼树的相关概念

148 6.15.3 带权路径长度 如何让WPL尽量小？ 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
权重越大的li越小越好。也就是说，权重越大的结点离根越近越好。（哈夫曼也这样想，呵呵） 最优二叉树的形态不唯一，但是WPL最小值是一致的。 6.15 哈夫曼树的相关概念

149 16. 哈夫曼树的构造

150 6.16.1 背景 哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。
6.16 哈夫曼树的构造

151 哈夫曼树的构造 哈夫曼树构造的动画 6.16 哈夫曼树的构造

152 哈夫曼树的构造 权重集合为：0.4,0.3,0.15,0.05,0.04,0.03,0.03 6.16 哈夫曼树的构造

153 哈夫曼树的构造 6.16 哈夫曼树的构造

154 哈夫曼树的构造 6.16 哈夫曼树的构造

155 哈夫曼树的构造 权重集合为：0.4,0.3,0.15,0.05,0.04,0.03,0.03 n个叶子的哈夫曼树构造过程中，要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 6.16 哈夫曼树的构造

156 哈夫曼树的存储 可以用一个大小为2×n－1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。 静态三叉链表中，每个结点的结构为 权值 双亲序号 左孩子序号 右孩子序号 data parent LChild RChild 1 A 2 3 B C 4 5 D E 6.16 哈夫曼树的构造

157 6.16.3 哈夫曼树的存储 weight parent LChild RChild 1 0.4 13 2 0.3 12 3 0.15 11
weight parent LChild RChild 1 0.4 13 2 0.3 12 3 0.15 11 4 0.05 9 5 0.04 6 0.03 8 7 0.06 10 0.09 0.6 6.16 哈夫曼树的构造

158 哈夫曼树的存储 哈夫曼树构造算法的动画 6.16 哈夫曼树的构造

159 17. 哈夫曼编码

160 背景 若一段程序有1000条指令，其中I1大约有400条，I2大约有300条，I3大约有150条，I4大约有50条，I5大约有40条，I6大约有30条，I7大约有30条。那么是否有一种编码方式能够实现程序长度最短？ 哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。 6.17 哈夫曼编码

161 6.17.2 定长编码 如果采用定长编码，需要的编码长度是log27=3。 该段程序的总位数大约为3×1000＝3000。 指令 I1
001 010 011 100 101 110 6.17 哈夫曼编码

162 6.17.3 变长编码 我们的思路是使用频率高的指令采用短的编码，这样才能缩短程序长度。比如：
但是事情没有这样简单。比如，00解释成两个I1,还是一个I3。因此，上述编码不能用。 指令 I1 I2 I3 I4 I5 I6 I7 编码 1 00 01 000 001 010 6.17 哈夫曼编码

163 6.17.4 前缀码 如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。
例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。 6.17 哈夫曼编码

164 哈夫曼编码 思路：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予1，右分支赋予0（相反也行），则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。（注意不是从叶子到根） 指令 I1 I2 I3 I4 I5 I6 I7 频率 0.4 0.3 0.15 0.05 0.04 0.03 编码 10 110 11100 11101 11110 11111 6.17 哈夫曼编码

165 哈夫曼编码 哈夫曼编码是前缀码 证明：哈夫曼编码是根到叶子路径上的边的编码的序列。而由树的特点知，若路径A是另一条路经B的最左部分，则B经过了A，因此，A的终点不是叶子。而哈夫曼编码都对应终点为叶子的路径，所以，任一哈夫曼码都不会与任意其他哈夫曼编码的前部分完全重叠，得证。 6.17 哈夫曼编码

166 哈夫曼编码 哈夫曼编码是最优前缀码。 比如，对于n个字符，分别以它们的使用频度为叶子权，构造哈夫曼树，则该树对应的哈夫曼编码，能使各种报文（由这n种字符构成的文本）对应的二进制串的平均长度最短。 6.17 哈夫曼编码

167 6.17.5 哈夫曼编码 计算哈夫曼编码的平均码长 pi为各个编码对应的概率，li为各个编码对应的长度。 指令 I1 I2 I3 I4 I5
频率 0.4 0.3 0.15 0.05 0.04 0.03 编码 10 110 11100 11101 11110 11111 采用哈夫曼编码后，该段程序的总位数大约为 1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200。平均码长为2200/1000=2.2。 6.17 哈夫曼编码

168 18. 并查集

169 6.18.1 背景 大侠的规则 碰到和自己不是一路人的，就免不了要打一架。 绝对不打自己的朋友。 信奉“朋友的朋友就是我的朋友”
两个原本互不相识的人，如何判断是否属于一个朋友圈呢？ 6.18 并查集

170 6.18.1 背景 寻找亲戚 如Marry和Tom是亲戚，Tom和Ben是亲戚，可以推出Marry和Ben是亲戚。
如果有完整的家谱，判断两个人是否亲戚是可行的。 但如果是远亲，那么检验亲戚关系就十分复杂。 在这种情况下，就需要应用并查集。 6.18 并查集

171 并查集概念 并查集（英文：Disjoint Set，即“不相交集合”）。将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。 常见两种操作： 合并两个集合 查找某元素是否属于哪个集合 所以，称为“并查集”。 6.18 并查集

172 并查集实现方法（1） 定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合；用编号最小的元素标记所在集合 比如：不相交集合： {1,3,7}, {4}, {2,5,9,10}, {6,8} i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

173 6.18.3 并查集实现方法（1） 查找某个元素（时间复杂度O(1)） i 1 2 3 4 5 6 7 8 9 10 set[i]
find1(x) { return set[x]; } i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

174 6.18.3 并查集实现方法（1） 合并两个集合（时间复杂度O(n)） 对于“合并操作”，必须搜索全部元素！如何改进？ i 1 2 3 4
merge1(a,b)// a,b是两个集合标号 { i = min(a,b); j = max(a,b); for (k=1; k<=n; k++) { if (set[k] == j) set[k] = i; } 对于“合并操作”，必须搜索全部元素！如何改进？ i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

175 6.18.4 并查集实现方法（2） 定义一个数组 set[1..n] ，每个集合用一棵“有根树”（即有向树，指定了根的树）表示
set[i] = i , 则i表示本集合，且是集合对应树的根。 set[i] = j, j<>i, 则 j 是 i 的双亲节点。 6.18 并查集

176 并查集实现方法（2） 比如： i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

177 6.18.4 并查集实现方法（2） 查找某个元素（时间复杂度O(1)） 不是查找set值，而是查找其祖先 i 1 2 3 4 5 6 7 8
find2(x) { r = x; while (set[r] != r) r = set[r]; return r; } 不是查找set值，而是查找其祖先 i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

178 6.18.4 并查集实现方法（2） 合并两个集合（时间复杂度O(1)） 合并之后树越深，查找越费时！如何改进？ i 1 2 3 4 5 6
merge2(a, b) { if (a<b) set[b] = a; else set[a] = b; } 合并之后树越深，查找越费时！如何改进？ i 1 2 3 4 5 6 7 8 9 10 set[i] 6.18 并查集

179 6.18.5 并查集性能优化 合并优化 方法：将深度小的树合并到深度大的树
实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是: max(h1,h2), if h1<>h2. h1+1, if h1=h2. 效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过logk 6.18 并查集

180 6.18.5 并查集性能优化 路径压缩 思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快 步骤:
第一步，找到根结点 第二步，修改查找路径上的所有节点，将它们都指向根结点 6.18 并查集

181 总结