数据结构-树与二叉树-思维导图+小结_数据结构树和二叉树思维导图

1 数据结构-第五章-树与二叉树-思维导图

  数据结构-第五章-树与二叉树-思维导图缩略图展示如下图1所示：

图1

2 思维导图-补充

  1、第五章中“并查集-基本操作”代码如下：

#define SIZE 13
int UFSets[SIZE];	//集合元素数组

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
		S[il=-1;
}

//Find"查"操作，找x所属集合(返回x所属根结点)
int Find(int S[],int x){
	while(S[x]>=0)	//循环寻找x的根
		X=S[x];
	return x;		//根的s[]小于0
}

//Union"并"操作，将两个集合合并为一个
void Union(int S[],int Rootl,int Root2){
	//要求Root1与Root2是不同的集合
	if(Root1==Root2)  return;
	//将根Root2连接到另一根Root1下面
	S[Root2]=Root1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  2、第五章中“并查集-Union优化”代码如下：

#define SIZE 13
int UFSets[SIZE];	//集合元素数组

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
		S[il=-1;
}

//Find"查"操作，找x所属集合(返回x所属根结点)
int Find(int S[],int x){
	while(S[x]>=0)	//循环寻找x的根
		X=S[x];
	return x;		//根的s[]小于0
}

//Union"并"操作，小树合并到大树
void Union(int S[],int Rootl,int Root2){
	if(Rootl==Root2) return;
	if(S[Root2]>S[Root1]){		//Root2结点数更少
		S[Root1] += S[Root2];   //累加结点总数
		S[Root2] = Root1;		//小树合并到大树
	} else {
		S[Root2] += S[Root1];	//累加结点总数
		S[Root1] = Root2;		//小树合并到大树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  3、第五章中“并查集-Find优化(压缩路径)”代码如下：

#define SIZE 13
int UFSets[SIZE];	//集合元素数组

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
		S[il=-1;
}

//Find"查"操作优化，先找到根节点，再进行"压缩路径"
int Find(int S[],int x){
	int root = x;
	while(S[root]>=0) root=S[root];	//循环找到根
	while(x!=root){		//压缩路径
		int t=S[x];		//t指向x的父节点
		S[x]=root;		//x直接挂到根节点下
		x=t;
	}
	return root;		//返回根节点编号
}

//Union"并"操作，小树合并到大树
void Union(int S[],int Rootl,int Root2){
	if(Rootl==Root2) return;
	if(S[Root2]>S[Root1]){		//Root2结点数更少
		S[Root1] += S[Root2];   //累加结点总数
		S[Root2] = Root1;		//小树合并到大树
	} else {
		S[Root2] += S[Root1];	//累加结点总数
		S[Root1] = Root2;		//小树合并到大树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3 小结

3.1 知识点小结

  1、树的性质：总结点数=总度数+1。

  2、度为m的树、m叉树区别：
    树的度------各结点的度的最大值；
    m叉树------每个结点最多只能有m个孩子的树；

  3、高度为h的m叉树至多有$\frac{m^h-1}{m-1}$个结点。

  4、满二叉树是高度为h且含有2^h-1个结点的二叉树。

  5、完全二叉树中度为1的结点要么为0要么为1。
    若完全二叉树有2k（偶数）个结点，则必有n₁ = 1，n₀ = k，n₂ = k-1；
    若完全二叉树有2k-1（奇数）个结点，则必有n₁ = 0，n₀ = k，n₂ = k-1。

  6、先序遍历、中序遍历、后序遍历利用栈进行实现，层次遍历利用队列进行实现。

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

  8、树和森林的遍历

  9、高度为h(h>0)的完全二叉树对应的森林所含的树的个数一般是h-1个，满二叉树对应的森林所含的树的个数是h个。

  10、构造哈夫曼树过程中，共建了n-1个结点（双分支结点），因此哈夫曼树结点总数为2n-1；构造哈夫曼树过程中每次都选择2棵树作为新结点的孩子，因此不存在度为1的结点。
  

3.2 习题小结

  以下题目均来自王道考研系列-《数据结构考研复习指导》。

  1、一棵有n₀个叶子结点的完全二叉树，最多有几个结点，最少有几个结点。

  1、【解析】在完全二叉树中，度为1的结点n₁有两种取值，即n₁ = 0或n₁ = 1。当n₁=1时，结点数最多，即n₀ + n₁ + n₂ = n₀ + 1 + n₀ - 1 = 2n₀个结点；当n₁ = 0时，结点数最少，即n₀ + n₁ + n₂ = n₀ + 0 + n₀ - 1 = 2n₀ - 1个结点；

  
  2、若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是几个。

  2、【解析】方法一：根据完全二叉树的性质：最后一个分支结点序号为$\lfloor n/2\rfloor$，那么$\lfloor 768/2\rfloor$=384，也就是说前384个结点是非叶结点，那么剩下768-384=384个结点就是叶子结点。
    方法二：在完全二叉树中，叶子结点个数比非叶子结点多一个或者二者相等，即n₁ = 0时，叶结点个数 = 非叶子结点个数 + 1；n₁ = 1时，叶结点个数 = 非叶子结点个数。总结点数 = n₀ + n₁ + n₂ = n₀ + n₁ + n₀ - 1 = 2n₀ + n₁ -1 = 768，即 2n₀ + n₁ = 769，又因为结点数必须是整数，所以n₁在可取值范围内取1，把n₁ = 1代入，即2n₀ = 768，n₀ = 384。
    方法三：根据3.1小结中第5点。因为768是偶数，所以必有n₁ = 1，n₀ = 384，n₂ = 383，故叶子结点为384个。
    补充：对于满二叉树，叶结点个数 = 非叶子结点个数 + 1

  
  3、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到多少个不同的码字。

  3、【解析】哈夫曼树有多少叶子结点，就有多少个不同的码字。哈夫曼树中只有度为0和度为2的两种结点，即n₀ + n₂ = n₀ + n₀ - 1 = 2n₀ - 1 = 215，n₀ = 108。

  
  4、若某二叉树有5个叶结点，其权值分别为10，12，16，21，30，则其最小的带权路径长度(WPL)是多少。

  4、【解析】方法一：画出对应哈夫曼树后计算，如下图2所示：

图2

    方法二：WPL=该树所有非叶子结点的权值之和，可以不画哈夫曼树，求出所有非叶结点的权值即可。即10 + 12 = 22，16 + 21 = 37，22 + 30 = 52，37 + 52 = 89，则WPL = 22 + 37 + 52 + 89 = 200。