树与二叉树

# 树和二叉树

# 树

空树 —— 结点数为 0 的树

非空树的特性：

有且仅有一个根节点
没有后继的结点称为 “叶子结点”（或终端结点）
有后继的结点称为 “分支结点”（或非终端结点）
除了根节点外，任何一个结点都有且仅有一个前驱
每个结点可以有 0 个或多个后继。

# 树的基本概念

树是 n $（ n \geq 0 ）$ 个结点的有限集合， $n = 0$ 时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

空树中应满足：

有且仅有一个特定的称为根的结点。
当 $n > 1$ 时，其余结点可分为 m $（ m > 0 ）$ 个互不相交的有限集合 $T_{1}, T_{2}, \dots, T_{m}$ ，其中每个集合本身又是一棵树，并且称为根结点的子树。

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

# 树形逻辑结构的应用

# 结点之间的关系描述

祖先结点：从自身开始向上追溯直到根结点，途径的所有结点都称为祖先结点（图示 “你” 的祖先结点有：“父亲”、“爷爷”）。
子孙节点：由自身所产生的所有结点都称为子孙节点（图示除了 “爷爷” 以外所有的结点都称为 “爷爷” 的子孙结点）。
双亲结点（父结点）：自身的前驱称为双亲结点（图示 “你” 的双亲结点为 “父亲”）。
孩子结点：自身的所有后继都称为孩子结点（图示 “父亲” 的孩子结点为 “你” 和 “F”）。
兄弟结点：自身的前驱所产生的其他结点称为兄弟结点（图示 “F” 为 “你” 的兄弟结点）。
堂兄弟结点：除了 “兄弟结点”，处于同一层中的所有结点都称为堂兄弟结点（图示 “G”、“H”、“I”、“J” 都称为 “你” 的堂兄弟结点）。
两个结点之间的路径：两个结点之间的路径只能是从上往下的单向方向。
路径长度：两个结点的路径长度指它们两经过的边的个数。

# 结点、树的属性描述

结点的层次（深度）—— 从上往下数；默认从 1 开始
结点的高度 —— 从下往上数
树的高度（深度）—— 总共多少层
结点的度 —— 有几个孩子（分支）
树的度 —— 各结点的度的最大值

# 有序树 V.S 无序树

有序树 —— 逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树 —— 逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

# 树 V.S 森林

森林。森林是 m $（ m \geq 0 ）$ 棵互不相交的树的集合

# 总结

# 树的常考性质

常见考点 1：结点数 = 总度数 + 1

常见考点 2：度为 m 的树、m 叉树的区别

度为 m 的树	m 叉树
任意结点的度 ≤ m（最多 m 个孩子）	任意结点的度 ≤ m（最多 m 个孩子）
至少有一个结点度 = m（有 m 个孩子）	允许所有结点的度都＜ m
一定是非空树，至少有 m+1 个结点	可以是空树

常见考点 3：度为 m 的树第 i 层至多有 $m^{i - 1}$ 个结点 $（ i \geq 1 ）$ m 叉树第 i 层至多有 $m^{i - 1}$ 个结点 $（ i \geq 1 ）$
常见考点 4：高度为 h 的 m 叉树至多有 $\frac{m^{h} - 1}{m - 1}$ 个结点。
常见考点 5：高度为 h 的 m 叉树至少有 h 个结点。高度为 h、度为 m 的树至少有 $h + m - 1$ 个结点。
常见考点 6：具有 n 个结点的 m 叉树的最小高度为 $⌈ \log_{m} (n (m - 1) + 1) ⌉$ 高度最小的情况 —— 所有结点都有 m 个孩子

# 总结

# 树、森林和二叉树之间的转换

# 树转换成二叉树

树转换成二叉树的画法：

在兄弟结点之间加一条线；
对每个结点，只保留它与第一个孩子的连线，抹去与其他孩子的连线；
以树根为轴心，顺时针旋转 45°

# 森林转换成二叉树

森林转换成二叉树的画法

将森林中的每棵树转换成相应的二叉树；
每棵树的根也可视为兄弟结点，在每棵树之间加一根连线；
以第一棵树的根为轴心顺时针旋转 45°

# 二叉树转成森林

将根结点右子树的连接全部清除
以二叉树的根结点为轴心逆时针旋转 45°
将二叉树的左树的右子树全部清除
以二叉树的根结点为轴心逆时针旋转 45°

# 二叉树

# 二叉树的基本概念

二叉树是 n $（ n \geq 0 ）$ 个结点的有限集合：

或者为空二叉树，即 n = 0
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点：

每个结点至多只有两棵子树
左右子树不能颠倒（二叉树是有序树）

# 二叉树的五种状态

# 几个特殊的二叉树

# 满二叉树

满二叉树。一棵高度为 h，且含有 2 h - 1 个结点的二叉树

特点：

只有最后一层有叶子结点
不存在度为 1 的结点
按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 $2 i + 1$ ；结点 i 的父节点为 $⌊ i / 2 ⌋$ （如果有的话）

# 完全二叉树

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

特点：

只有最后两层可能有叶子结点
最多只有一个度为 1 的结点
按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 $2 i + 1$ ；结点 i 的父节点为 $⌊ i / 2 ⌋$ （如果有的话）
$i \leq ⌊ n / 2 ⌋$ 为分支结点， $i > ⌊ n / 2 ⌋$ 为叶子结点

# 二叉排序树

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

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

# 平衡二叉树

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过 1。

# 总结

# 二叉树的常考性质

常见考点 1：设非空二叉树中度为 0、1 和 2 的结点个数分别为 $n_{0} 、 n_{1} 和 n_{2}$ ，则 $n_{0} = n_{2} + 1$ （叶子结点比二分支结点多一个）
常见考点 2：二叉树第 i 层至多有 $2^{i - 1}$ 个结点 $（ i \geq 1 ）$ m 叉树第 i 层至多有 $m^{i - 1}$ 个结点 $（ i \geq 1 ）$
常见考点 3：高度为 h 的二叉树至多有 $2^{ℎ} - 1$ 个结点（满二叉树）

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

# 完全二叉树的常考性质

常见考点 1：具有 n 个（n > 0）结点的完全二叉树的高度 h 为 $⌈ \log_{2} (n + 1) ⌉ 或 ⌊ \log_{2} n ⌋ + 1$
常见考点 2：对于完全二叉树，可以由的结点数 n 推出度为 0、1 和 2 的结点个数为 $n_{0} 、 n_{1} 和 n_{2} ，完全二叉树最多只有一个度为 1 的结点，即$ $n_{1} = 0 或 1$ $n_{0} = n_{2} + 1 \to n_{0} + n - 2 一定是奇数$
- 若完全二叉树有 2k 个（偶数）个结点，则必有 $n_{1} = 1 ， n_{0} = k ， n_{2} = k - 1$
- 若完全二叉树有 $2 k - 1$ 个（奇数）个结点，则必有 $n_{1} = 0 ， n_{0} = k ， n_{2} = k - 1$

# 二叉树的存储结构

# 二叉树的顺序存储

#define MaxSize 100
struct TreeNode {
	ElemType value;
	bool IsEmpty; //结点是否为空
};
TreeNode t[MaxSize];

1
2
3
4
5
6

定义一个长度为 MaxSize 的数组 t ，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点

几个重要常考的基本操作：

i 的左孩子 ——2i
i 的右孩子 —— $2 i + 1$
i 的父节点 —— $⌊ i / 2 ⌋$
i 所在的层次 —— $⌈ \log_{2} (n + 1) ⌉ 或 ⌊ \log_{2} n ⌋ + 1$

若完全二叉树中共有 n 个结点，则

判断 i 是否有左孩子？ ——$2i ≤ n? $
判断 i 是否有右孩子？ —— $2 i + 1 \leq n ?$
判断 i 是否是叶子 / 分支结点？ —— $i > ⌊ n / 2 ⌋ ?$

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 $2^{h} - 1$ 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

# 二叉树的链式存储

typedef struct BiTNode {
	ElemType data; //数据域
	struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;

1
2
3
4

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

struct ElemType {
	int value;
};

typedef struct BiTNode {
	ElemType data; //数据域
	struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;

void testBuild() {
	//定义一棵空树
	BiTree root = NULL;
	//插入根节点
	root = (BiTree) malloc(sizeof(BiTNode));
	root->data = {1};
	root->lchild = NULL;
	root->rchild = NULL;
	//插入新结点
	BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
	p->data = {2};
	p->lchild = NULL;
	p->rchild = NULL;
	root->lchild = 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

如何找到指定结点 p 的父结点？

只能从根开始遍历寻找

给结点添加一个 parent 指针记录它的父节点

typedef struct BiTNode {
	ElemType data; //数据域
	struct BiTNode *lchild, *rchild; //左、右孩子指针
    struct BiTNode *parent; //父节点指针 称为三叉链表
} BiTNode, *BiTree;

1
2
3
4
5

# 先 / 中 / 后序遍历

遍历：按照某种次序把所有结点都访问一遍

# 二叉树的遍历

二叉树的递归特性：

要么是个空二叉树
要么就是由 “根节点 + 左子树 + 右子树” 组成的二叉树

遍历顺序：

先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）

在前 / 中 / 后序表达式中应用

# 先序遍历

先序遍历（PreOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
访问根结点；
先序遍历左子树；
先序遍历右子树。

//先序遍历
void preOrder(BiTree T) {
	if (T != NULL) {
		visit(T); //访问根节点
		preOrder(T->lchild); //递归遍历左子树
		preOrder(T->rchild); //递归遍历右子树
	}
}

1
2
3
4
5
6
7
8

# 中序遍历

中序遍历（InOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
中序遍历左子树；
访问根结点；
中序遍历右子树

//中序遍历
void InOrder(BiTree T) {
	if (T != NULL) {
		preOrder(T->lchild); //递归遍历左子树
		visit(T); //访问根节点
		preOrder(T->rchild); //递归遍历右子树
	}
}

1
2
3
4
5
6
7
8

# 后序遍历

后序遍历（InOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
后序遍历左子树；
后序遍历右子树；
访问根结点。

//后序遍历
void PostOrder(BiTree T) {
	if (T != NULL) {
		preOrder(T->lchild); //递归遍历左子树
		preOrder(T->rchild); //递归遍历右子树
		visit(T); //访问根节点
	}
}

1
2
3
4
5
6
7
8

# 求遍历序列

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

先序遍历 —— 第一次路过时访问结点，每个结点都会被路过 3 次。
中序遍历 —— 第二次路过时访问结点
后序遍历 —— 第三次路过时访问结点

# 总结

# 二叉树层序遍历

算法思想：

初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
重复 3 直至队列为空

typedef struct BiTNode {
	ElemType data; //数据域
	struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode {
	BiTNode * data;
	struct LinkNode *next;
} LinkNode;

typedef struct {
	LinkNode *front, *rear; //队头队尾指针
} LinkQueue;

//层序遍历
void LevelOrder(BiTree T) {
	LinkQueue Q;
	InitQueue(Q); //初始化辅助队列
	BiTree p;
	EnQueue(Q, T); //将根结点入队
	while (!IsEmpty(Q)) { //队列不空则循环
		DeQueue(Q, p); //队头结点出队
		visit(p); //访问出队结点
		if (p->lchild != NULL) {
			EnQueue(Q, p->lchild); //左孩子入队
		}
		if (p->rchild != NULL) {
			EnQueue(Q, p->rchild); //右孩子入队
		}
	}
}

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

# 由遍历序列构造二叉树

中序遍历：中序遍历左子树、根结点、中序遍历右子树

前序遍历：根结点、前序遍历左子树、前序遍历右子树

后序遍历：前序遍历左子树、前序遍历右子树、根结点

层序遍历：

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

# 前序 + 中序遍历序列

# 后序 + 中序遍历序列

# 层序 + 中序遍历序列

# 若前序、后序、层序序列两两组合？

结论：前序、后序、层序序列的两两组合无法唯一确定一科二叉树

# 总结

# 线索二叉树

能否从一个指定结点开始中序遍历？

如何找到指定结点 p 在中序遍历序列中的前驱？
如何找到 p 的中序后继？

思路：从根节点出发，重新进行一次中序遍历，指针 q 记录当前访问的结点，指针 pre 记录上一个被访问的结点

当 q==p 时，pre 为前驱
当 pre==p 时，q 为后继

缺点：找前驱、后继很不方便；遍历操作必须从根开始

# 线索二叉树概念

# 中序线索二叉树

# 线索二叉树的存储结构

//线索二叉树结点
typedef struct ThreadNode {
	ElemType data;
	struct ThereadNode *lchild, *rchild;
	int ltag, rtag; //左、右线索标志
} ThereadNode, *ThereadTree;

1
2
3
4
5
6

# 先序线索二叉树

# 后序线索二叉树

# 三种线索二叉树的对比

# 总结

# 二叉树的线索化

# 中序线索化

//线索二叉树结点
typedef struct ThreadNode {
	ElemType data;
	struct ThereadNode *lchild, *rchild;
	int ltag, rtag; //左、右线索标志
} ThereadNode, *ThereadTree;

//全局变量 pre 指向当前访问结点的前驱
ThreadNode *pre = NULL;

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;
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThereadTree T) {
	if (T != NULL) {
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
}

//中序线索化的二叉树
void CreateInThread(ThereadTree T) {
	pre = NULL; //pre初始化为null
	if (T != NULL) { //非空二叉树才能线索化
		InThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1; //处理遍历的最后一个结点
		}
	}
}

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
33
34
35
36
37
38
39
40
41

# 先序线索化

//线索二叉树结点
typedef struct ThreadNode {
	ElemType data;
	struct ThereadNode *lchild, *rchild;
	int ltag, rtag; //左、右线索标志
} ThereadNode, *ThereadTree;

//全局变量 pre 指向当前访问结点的前驱
ThreadNode *pre = NULL;

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;
}

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThereadTree T) {
	if (T != NULL) {
        visit(T);
		if (T->ltag==0){ //lchild不是前驱线索
            PreThread(T->lchild);
        }
		PreThread(T->rchild);
	}
}

//先序线索化的二叉树
void CreateInThread(ThereadTree T) {
	pre = NULL; //pre初始化为null
	if (T != NULL) { //非空二叉树才能线索化
		PreThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1; //处理遍历的最后一个结点
		}
	}
}

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
33
34
35
36
37
38
39
40
41
42
43

# 后序线索化

//线索二叉树结点
typedef struct ThreadNode {
	ElemType data;
	struct ThereadNode *lchild, *rchild;
	int ltag, rtag; //左、右线索标志
} ThereadNode, *ThereadTree;

//全局变量 pre 指向当前访问结点的前驱
ThreadNode *pre = NULL;

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;
}

//后序遍历二叉树，一边遍历一边线索化
void PostThread(ThereadTree T) {
	if (T != NULL) {
		PostThread(T->lchild);
		PostThread(T->rchild);
        visit(T);
	}
}

//后序线索化的二叉树
void CreateInThread(ThereadTree T) {
	pre = NULL; //pre初始化为null
	if (T != NULL) { //非空二叉树才能线索化
		PostThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1; //处理遍历的最后一个结点
		}
	}
}

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
33
34
35
36
37
38
39
40
41

# 总结

# 找前驱 / 后继

# 中序线索二叉树找中序后继

在中序线索二叉树中找到指定结点 * p 的中序后继 next

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0

//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p) {
	//循环找到最左下结点（不一定是叶子结点）
	while (p->ltag == 0) {
		p = p->lchild;
	}
	return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
	//右子树最左下结点
	if (p->rtag == 0) {
		return Firstnode(p->rchild);
	} else {
		return p->rchild;
	}
}

//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void InOrder(ThreadNode *T) {
	for (ThereadTree *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
17
18
19
20
21
22
23
24
25

空间复杂度 $O (1)$

# 中序线索二叉树找中序前驱

在中序线索二叉树中找到指定结点 * p 的中序前驱 pre

若 p->ltag==1，则 pre = p->lchild
若 p->ltag==0

//找到以p为根的子树中，最后被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p) {
	//循环找到最右下结点（不一定是叶子结点）
	while (p->rtag == 0) {
		p = p->rchild;
	}
	return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Prenode(ThreadNode *p) {
	//左子树最右下结点
	if (p->ltag == 0) {
		return Lastnode(p->lchild);
	} else {
		return p->lchild;
	}
}

//对中序线索二叉树进行逆向中序遍历
void InOrder(ThreadNode *T) {
	for (ThereadTree *p = Lastnode(T); p != NULL; p = Prenode(p)) {
		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

# 先序线索二叉树找先序后继

在先序线索二叉树中找到指定结点 * p 的先序后继 next

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0

# 先序线索二叉树找先序前驱

在先序线索二叉树中找到指定结点 * p 的先序前驱 pre

若 p->ltag==1，则 next = p->lchild
若 p->ltag==0

改用三叉链表可以找到父节点

# 后序线索二叉树找后序前驱

在后序线索二叉树中找到指定结点 * p 的后序前驱 pre

若 p->ltag==1，则 pre = p->lchild
若 p->ltag==0

# 后序线索二叉树找后序后继

在后序线索二叉树中找到指定结点 * p 的后序后继 next

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0

改用三叉链表可以找到父节点

# 总结

	中序线索二叉树	前序线索二叉树	后序线索二叉树
找前驱	√	×	√
找后驱	√	√	×

除非用三叉链表，或者用土办法从根开始遍历寻找

# 树的存储结构

树的基本概念

# 双亲表示法（顺序存储）

双亲表示法：每个结点中保存指向双亲的 “指针”

#define 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
10

双亲表示没有顺序要求，插入直接插入，删除用 - 1 标记法或者尾部迁移法都可以，并且插入 / 删除之后需要更新结点数

如果删除的是一个非叶子结点，则需要从头遍历孩子节点，进行逐个删除

# 孩子表示法（顺序 + 链式存储）

孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针

#define MAX_TREE_SIZE 100
struct CTNode {
	int child; //孩子结点在数组中的位置
	struct CTNode *next; //下一个孩子
};

typedef struct {
	ElemType data;
	struct CTNode *firstChild; //第一个孩子
} CTBox;

typedef struct {
	CTBox nodes[MAX_TREE_SIZE];
	int n, r; //结点数和根的位置
} CTree;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 孩子兄弟表示法（链式存储）

//孩子兄弟表示法
typedef struct CSNode {
	ElemType data;
	struct CSNode *firstChild, *nextsibling; //第一个孩子和右兄弟指
} CSNode, *CSTree;

1
2
3
4
5

# 森林和二叉树的转换

本质：用二叉链表存储森林

树、森林和二叉树之间的转换

# 总结

# 树、森林的遍历

# 树的先根遍历

先根遍历。若树非空，先访问根结点，再依次对每棵子树进行先根遍历。（深度优先遍历）

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

# 树的后根遍历

后根遍历。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。（深度优先遍历）

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

# 树的层次遍历

层次遍历（用队列实现即广度优先遍历）

若树非空，则根节点入队
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
重复 2 直到队列为空

# 森林的先序遍历

若森林为非空，则按如下规则进行遍历：

访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林。

也可以把森林转成二叉树再进行遍历

# 森林的中序遍历

若森林为非空，则按如下规则进行遍历：

中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

也可以把森林转成二叉树再进行遍历

# 总结

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

# 二叉排序树（BST）

二叉排序树，又称二叉查找树（BST，Binary Search Tree），一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

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

进行中序遍历，可以得到一个递增的有序序列

# 二叉排序树的查找

左子树结点值 < 根结点值 < 右子树结点值

若树非空，目标值与根结点的值比较
若相等，则查找成功
若小于根结点，则在左子树上查找，否则在右子树上查找
查找成功，返回结点指针；查找失败返回 NULL

//二叉排序树结点
typedef struct BSTNode {
	int key;
	struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

//在二叉排序树中查找值为 key 的结点  最坏空间复杂度O(1)
BSTNode *BST_Search(BSTree T, int key) {
	while (T != NULL && key != T->key) { //若树空或等于根结点值，则结束
		if (key < T->key) {
			T = T->lchild; //小于，则在左子树上查找
		} else {
			T = T->rchild; //大于，则在右子树上查找
		}
	}
	return T;
}

//在二叉排序树中查找值为 key 的结点（递归版）  最坏空间复杂度O(h)
BSTNode *BSTSearch(BSTree T, int key) {
	if (T == NULL) {
		return NULL; // 查找失败
	}
	if (key == T->key) {
		return T; // 查找成功
	} else if (key < T->key) {
		return BSTSearch(T->lchild, key); // 在左子树上查找
	} else {
		return BSTSearch(T->rchild, key); //在右子树上查找
	}
}

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

# 二叉排序树的插入

若原二叉排序树为空，则直接插入结点；
若关键字 k 小于根结点值，则插入到左子树，
若关键字 k 大于根结点值，则插入到右子树

//在二叉排序树插入关键字为k的新结点（递归实现） 最坏空间复杂度O(h)
int BST_Insert(BSTree &T, int k) {
	if (T == NULL) { //原树为空，新插入的结点为根结点
		T = (BSTree) malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1; //返回1，则插入成功
	} else if (k == T->key) { //树中查找相同关键字的结点，插入失败返回0
		return 0;
	} else if (k < T->key) {
		return BST_Insert(T->lchild, k); //插入到T的左子树上
	} else {
		return BST_Insert(T->rchild, k); //插入到T的右子树上
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二叉排序树的构造

//按照 str[] 中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n) {
	T = NULL; //初始时T为空树
	int i = 0;
	while (i < n) { //依次将每个关键字插入到二叉排序树中
		BST_Insert(T, str[i]);
		i++;
	}
}

1
2
3
4
5
6
7
8
9

# 二叉排序树的删除

先搜索找到目标结点：

若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
- z 的后继：z 的右子树中最左下结点（该节点一定没有左子树）；可以进行中序遍历，可以得到一个递增的有序序列，即该右子树进行中序遍历的第一个元素，会得到 p。
- z 的前驱：z 的左子树中最右下结点（该节点一定没有右子树）；可以进行中序遍历，可以得到一个递增的有序序列，即该左子树进行中序遍历的最后一个元素，会得到 p。

# 查找效率分析

查找长度 —— 在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。若树高 h，找到最下层的一个结点需要对比 h 次。

查找成功的平均查找长度 ASL （ Average Search Length ）

$A S L = (1 * 1 + 2 * 2 + 3 * 4 + 4 * 1) / 8 = 2.625$

$A S L = (1 * 1 + 2 * 2 + 3 * 1 + 4 * 1 + 5 * 1 + 6 * 1 + 7 * 1) / 8 = 3.75$

最好情况：n 个结点的二叉树最小高度为 $⌊ \log_{2} n ⌋ + 1 。$ 。平均查找长度 = $O (l o g_{2} n)$
最坏情况：每个结点只有一个分支，树高 h = 结点数 n。平均查找长度 = $O (n)$

查找失败的平均查找长度 ASL （ Average Search Length ）

$A S L = (3 * 7 + 4 * 2) / 9 = 3.22$

$A S L = (2 * 3 + 3 + 4 + 5 + 6 + 7 * 2) / 9 = 4.22$

# 总结

# 平衡二叉树（AVL）

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL 树 [G. M. Adelson-Velsky 和 E. M. Landis]）—— 树上任一结点的左子树和右子树的高度之差不超过 1。

结点的平衡因子 = 左子树高 - 右子树高。

//平衡二叉树结点
typedef struct AVLNode {
	int key;
	int balance; //平衡因子
	struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

1
2
3
4
5
6

# 平衡二叉树的插入

在二叉排序树中插入新结点后，如何保持平衡？

查找路径上的所有结点都有可能受到影响；从插入点往回找到第一个不平衡结点，调整以该结点为根的子树

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡

下面我们将说明四种情况的具体步骤

# 调整最小不平衡子树

# 调整最小不平衡子树（ LL ）

LL 即在 A 的左孩子的左子树中插入导致不平衡

二叉排序树的特性：左子树结点值 < 根结点值 < 右子树结点值

BL<B<BR<A<AR

LL 平衡旋转（右单旋转）。由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。

066f5430-db62-4c1f-a224-15c864f67c6b

# 调整最小不平衡子树（ RR ）

RR 即在 A 的右孩子的右子树中插入导致不平衡

二叉排序树的特性：左子树结点值 < 根结点值 < 右子树结点值

AL<A<BL<B<BR

RR 平衡旋转（左单旋转）。由于在结点 A 的右孩子（R）的右子树（R）上插入了新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。

74f55c09-a034-49eb-9f07-0bb7794b29cc

# 代码思路

# 调整最小不平衡子树（ LR ）

LR 平衡旋转（先左后右双旋转）。由于在 A 的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置

# 调整最小不平衡子树（ RL ）

RL 平衡旋转（先右后左双旋转）。由于在 A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置

# 总结

# 查找效率分析

若树高为 h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 $O (h)$

平衡二叉树 —— 树上任一结点的左子树和右子树的高度之差不超过 1。

假设以 $n_{h}$ 表示深度为 h 的平衡树中含有的最少结点数。

则有 $n_{0} = 0, n_{1} = 1, n_{2} = 2$ ，并且有 $n_{h} = n_{h - 1} + n_{h - 2} + 1$

可以证明含有 n 个结点的平衡二叉树的最大深度为 $O (l o g_{2} n)$ ，平衡二叉树的平均查找长度为 $O (l o g_{2} n)$

《An algorithm for the organizaSonof informaSon》——G.M. Adelson-Velsky 和 E.M. Landis ,1962

# 总结

# 哈夫曼树

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

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

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

$WPL = \sum_{i = 1}^{n} w_{i} l_{i}$

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

# 哈夫曼树的构造

给定 n 个权值分别为 $w_{1}, w_{2}, \dots, w_{n}$ 的结点，构造哈夫曼树的算法描述如下：

将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。
构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
重复步骤 2 和 3，直至 F 中只剩下一棵树为止。

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
哈夫曼树的结点总数为 $2 n - 1$
哈夫曼树中不存在度为 1 的结点。
哈夫曼树并不唯一，但 WPL 必然相同且为最优

# 哈夫曼编码

电报 —— 点、划两个信号（二进制 0/1）

固定长度编码 —— 每个字符用相等长度的二进制位表示
可变长度编码 —— 允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

有哈夫曼树得到哈夫曼编码 —— 字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树，一般以左边为 0，右边为 1，从根据节点到某个结点即为这个结点的哈夫曼编码。

# 英文字母频次

英文字母使用频率表：(%) A 8.19 B 1.47 C 3.83 D 3.91 E 12.25 F 2.26 G 1.71 H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 M 3.34 N 7.06 O 7.26 P 2.89 Q 0.09 R 6.85 S 6.36 T 9.41 U 2.58 V 1.09 W 1.59 X 0.21 Y 1.58 Z 0.08

可以尝试设计哈夫曼编码，并计算数据压缩率

# 总结

编辑

上次更新: 2023/12/06, 01:31:48

← 串图→