数据结构考研第五章——树与二叉树（内含动图）

一、树的基本概念

1. 基本术语

1. 结点的度：一个结点的孩子个数称为结点的度
   树的度：树中结点的最大度数称为树的度
2. 分支结点：度大于0的结点
   叶子结点：度等于0的结点
3. 结点的深度：从根结点开始自上而下逐层累加的
   结点的高度：从叶子结点开始自底向上逐层累加的
4. 有序树：树中各结点从左到右是有次序的，不能互换，互换后会变成另一棵不同的树
   无序树：树中各结点从左到右是无次序的，可以互换，互换后会变成另一棵不同的树
5. 路径：两个结点之间的路径是由这两个结点之间所经过的结点序列构成的
   路径长度：路径上所经过的边的个数

2. 树的性质（结点数、高度）

1. 树中的结点数等于所有结点的度数加1；（除了根结点，每个结点头上都插着一个针）
2. 度为m的树中第i层上至多有$m^{i-1}$个结点
3. 高度为h的m叉树至多有$(m^h-1)$/$(m-1)$个结点
4. 具有n个结点的m叉树的最小高度为math.ceil[ $lo{g}_m$ (n(m-1) +1) ]

二、二叉树的基本概念

1. 特殊二叉树

满二叉树
完全二叉树
二叉排序树
平衡二叉树

2. 二叉树的性质（结点数、高度、编号、链域）

1. 树中的结点数等于所有结点的度数加1；（除了根结点，每个结点头上都插着一个针）；
2. 非空叉树的叶子结点数等于度为2的结点数加1；
3. 高度为h的m叉树至多有$(2^h-1)$个结点；
4. 度为m的树中第i层上至多有$2^{i-1}$个结点；
5. 具有n个结点的m叉树的最小高度为math.ceil[ $lo{g}_2$ (n+1)
6. 结点i的双亲编号：i/2;
   结点i的左孩子编号：2i；
   结点的右孩子编号：2i+1；
7. 链式存储结构：在含n个结点的二叉链表中，含有n+1个空链域

3. 二叉树的存储结构

【顺序存储结构】（从1开始存储）

1. 适用范围：完全二叉树和满二叉树
2. 数组下标：使用数组存储二叉树，建议从数组下标1开始存储树中的结点，若从数组下标0开始存储，则不满足性质4的描述。

【链式存储结构】 （在含n个结点的二叉链表中，含有n+1个空链域）

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
1
2
3
4

三、二叉树的遍历

注意：二叉树的先序中序后序遍历就是深度优先遍历。

1. 先序遍历

【递归先序遍历】

void PreOrder(BiTree T){
	visit(T);
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}
1
2
3
4
5

【非递归先序遍历】

//结点不为空就visit&push&lchild，结点为空就Pop&rchild，总结为vpl&pr
int PreOrder(BiTree T){
	if(T==NULL) return;
	
	SqStack S;
	InitStack(&S);
	BiTree p=T;
	while(p||!StackEmpty(S)){
		while(p){						
			visit(p);
			Push(&S,*p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			Pop(&S,p);
			p=p->rchild;
		}
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 中序遍历

【递归中序遍历】

void MidOrder(BiTree T){
	PreOrder(T->lchild);
	visit(T);
	PreOrder(T->rchild);
}
1
2
3
4
5

【非递归中序遍历】

//结点不为空就push&lchild，结点为空就Pop&visit&rchild，总结为pl&pvr
void MidOrder(BiTree T){
	if(T==NULL) return;

	InitStack(S);
	BiTree p=T;
	while(p||!StackEmpty(S)){
		while(p){
			Push(p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 后序遍历

【递归后序遍历】

void PreOrder(BiTree T){
	PreOrder(T->lchild);
	PreOrder(T->rchild);
	visit(T);
}
1
2
3
4
5

【非递归后序遍历】

//结点不为空就push&lchild，结点为空就Pop&visit&rchild，总结为pl&pprv
void PostOrder(BiTree T){
	if(T==NULL) return;    //重点呀大哥
	
	InitStack S;
	BiTree p;
	p.ptr=T;
	p.tag=0;
	Push(S,p);

	while(!p||StackEmpty(S)){
		while(p){
			Push(S,p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			Pop(S,p);
			if(!p->tag){
				p->tag++;
				Push(S,p);
			}
			if(p->rchild) p=p->rchild;
			else visit(p);
		}
	}
}
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

4. 层次遍历

【借助队列实现】

void LevelOrder(BiTree T){
	if(T==NULL) return;

	InitQueue(Q);
	BiTree p;
	EnQueue(Q,p);
	while(p||!QueueEmpty(Q)){
		DeQueue(Q,p);
		visit(p);
		if(p=p->lchild!=NULL) EnQueue(Q,p->lchild);
		if(p=p->rchild!=NULL) EnQueQue(Q,p->rchild);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

四、线索二叉树

1. 线索二叉树的定义

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点都有一个直接前驱和直接后继。

typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;	//指示左右孩子，或者指示前驱后继
	int ltag,rtag;						//tag为0时指示左右孩子，tag为1时指示前驱后继
}ThreadNode,*ThreadTree;
1
2
3
4
5

2. 二叉树的线索化

【共用模块】

void visit(ThreadNode *q){
	if(q->lchild==NULL){
		q->lchild=pre;	//左子树指向了前驱
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){
		pre->rchild=q;	
		pre->rtag=1;
	}
	pre=q;	//pre是前结点，供后继结点q=lchild使用
}
1
2
3
4
5
6
7
8
9
10
11

【先序遍历线索化】

void PreThread(ThreadTree T){
	if(T==NULL) return;
    visit(T);		//pre变化顺序为根、左、右
    if(T->ltag==0) PreThread(T->lchild);	 
    PreThread(T->rchild);
}

void CreatePreThread(ThreadTree T){
    pre=NULL;
    if(T==NULL) return;
    PreThread(T);
    if(pre->rchild==NULL) pre->rtag=1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

【中序遍历线索化】

void InThread(ThreadTree T){
    if(T==NULL) return;
    InThread(T->lchild);
    visit(T);
    InThread(T->rchild);
}
 
void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T==NULL) return;
    InThread(T);
    if(pre->rchild==NULL) pre->rtag=1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

【后序遍历线索化】

void PostThread(ThreadTree T){
    if(T!=NULL) return;
    PostThread(T->lchild);
    PostThread(T->rchild);
    visit(T);
}
 
void CreatePostThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL) return;
    PostThread(T);
    if(pre->rchild==NULL) pre->rtag=1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 中序线索二叉树的遍历

在中序线索二叉树中找结点后继的规律是：

1. 若其右标记为“1”，则右链为线索，指示其后继；
2. 否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继；

//若其右标记为“1”，则右链为线索，指示其后继；
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0) p=p->lchild;
	return p;
}

//否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==0) return Firstnode(p->rchild);	//右子树
	else return p->rchild;						//后继
}

//使用上述两个函数就可以完成中序遍历
void Inorder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(T);p!=NULL;p=nextnode(p))	visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五、树、森林

1. 树的存储结构

【双亲表示法】

typedef MAX_TREE_SIZE 100
typedef struct{
	ElemType data;
	int parent;
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int n;
}PTree;
1
2
3
4
5
6
7
8
9

【孩子表示法】

将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表。

【孩子兄弟法】

typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild,*nextsibling;
}
1
2
3
4

2. 树、森林与二叉树的转换

3. 树和森林的遍历
   

六、 哈夫曼树和哈夫曼编码

【基本概念】

1. 带权路径长度WPL：树中所有叶结点的带权路径长度之和称为该树的带权路径长度
2. 哈夫曼树：带权路径长度最小的二叉树称为哈夫曼树，也成为最优二叉树

【哈夫曼树的构造】

【哈夫曼编码】

七、并查集

1. 存储结构 （下标为0的数组）
   
2. 基本操作

【并查集的结构定义】

#define SIZE 100
int UFSets[SIZE];
1
2

【并查集初始化操作】

void Initial(int S[]){
	for(int i=0;i<size;i++) S[i]=-i;
}
1
2
3

【并查集查询操作】

int Find(int S[],int x){
	while(S[x]>=0) x=S[x];
	return x;
}
1
2
3
4

【并查集合并操作】

void Union(int S[],int Root1,int Root2){	//合并两个集合，必须先找到两个元素的根结点
	if(Root1==Root2) return;
	S[Root2]==S[Root1];
}
1
2
3
4