树算法

algorithm

早起的虫儿被鸟吃

* 二叉树的存储：链式存储和数组。
* 二叉树的遍历：先序、中序、后序、层序。

二叉树的遍历

层序遍历

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
//算法思想：
//①将根节点root加入队列q。
//②取出队首结点，访问之。
//③如果该结点有左孩子，将左孩子入队。
//④如果该结点有有孩子，将有孩子入队。
//⑤返回②，直到队列为空。

void LayerOrder(node* root) { //带层次
	queue<node*> q;
	root->layer = 1;
	q.push(root);
	while(!q.empty()){
		node* p = q.front();
		q.pop();
		printf("%d ", p->data);
		if(p->left != NULL) {
			p->left->layer = p->layer + 1;
			q.push(p->left);
		}
		if(p->right != NULL) {
			p->right->layer = p->layer + 1;
			q.push(p->right);
		}
	}
}

建立二叉树

已知先序中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//算法思想：
//①先序数组的第零个结点为根结点。
//②遍历中序数组找出根结点位置并记录。
//③计算中序数组左子树个数
//④递归建立左右子树。

//其他情况算法类似，重点是确定根结点和数组区间范围。

node* create(int preL, int preR, int inL, int inR) {
	if(preL > preR) return NULL;
	node* root = new node;
	root->data = pre[preL];
	int k = inL;
	for(; k < inR; k++)
		if(in[k] == root->data) break;
	int numLeft = k - inL;
	root->left = create(preL + 1, preL + numLeft, inL, k - 1);
	root->right = create(preL + numLeft + 1, preR, k + 1, inR);
	return root;
}

二叉查找树(BST)

* 左边小右边大
* 对二叉查找树进行"中序"遍历，遍历结果是有序的
* 如果给定序列是有序的或者排序后有序，可以中序递归建立BST

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
void search(node* root, const int x) {
	if(root == NULL) {
		printf("search failed!\n");
		return;
	}
	if(x == root->data)
		printf("%d\n", root->data);
	else if(x < root->data)
		search(root->left, x);
	else
		search(root->right, x);
}

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert(node* &root, const int x) {
	if(root == NULL) { //插入位置
		root = new node;
		root->data = x;
		root->left = root->right = NULL;
		return;
	}
	if(x == root->data) return; //结点已存在 直接返回
	else if(x < root->data)
		insert(root->left, x);
	else
		insert(root->right, x);
}

二叉查找树的建立

1
2
3
4
5
node* create(int data[]) {
	node* root = NULL;
	for(const auto val : data) insert(root, val);
	return root;
}

二叉查找树的删除

1
2
3
4
5
6
7
8
9
10
11
12
//寻找以root为根结点的树中的最大权值结点
node* findMAX(node* root) {
	while(root->right != NULL)
		root = root->right;
	return root;
}
//寻找以root为根结点的树中的最小权值结点
node* findMin(node* root) {
	while(root->left != NULL)
		root = root->left;
	return root;
}
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
//算法思想：
//①如果当前结点root为空，说明不存在权值为给定权值 直接返回。
//②如果当前结点root的权值恰为给定权值x，进入删除处理
//a)如果当前结点root不存在左右孩子，说明叶子结点，直接删除。
//b)如果当前结点root存在左孩子，那么在左子树中寻找结点前驱pre，然//后让pre的数据覆盖root，接着在左子树中删除结点pre。
//c)如果当前结点root存在右孩子，那么在右子树中寻找结点后继next，//然后让next的数据覆盖root，接着在右子树中删除结点next。
//③如果给定的权值x小于当前结点的权值，则在左子树中递归删除权值为x//的结点。
//④如果给定的权值x大于当前结点的权值，则在右子树中递归删除权值为x//的结点。

void deleteNode(node* root, int x) {
	if(root == NULL) return; //不存在权值为x的结点
	if(x == root->data) {//找到欲删除结点
		//delete(root);
		if(root->left == NULL && root->right == NULL)
			root = NULL;
		else if(root->left != NULL) {
			node* pre = findMAX(root->left, x);
			root->data = pre->data;
			deleteNode(root->left, pre->data);
		}
		else {
			node* next = findMin(root->right);
			root->data = next->data;
			deleteNode(root->right, next->data);
		}
	}
	else if(x < root->data)
		deleteNode(root->left, x);
	else
		deleteNode(root->right, x);
}

平衡二叉树(AVL树)

* AVL树是一棵二叉查找树
* 任意结点的左右子树高度之差(平衡因子)的绝对值不超过1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node {
	int v, height;
	node *left, *right;
};

int getHeight(node* root) {
	if(root == NULL) return 0;
	else return root->height;
}

int getBalanceFactor(node* root) {
	return getHeight(root->left) - getHeight(root->right);
}

void updateHeight(node* root) {
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
void search(node* root, const int x) {
	if(root == NULL) {
		printf("search failed!\n");
		return;
	}
	if(x == root->data)
		printf("%d\n", root->data);
	else if(x < root->data)
		search(root->left, x);
	else
		search(root->right, x);
}

插入操作

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
//旋转问题：
//左旋(Left Rotation)算法思想：
//①让B的左子树◆成为A的右子树
//②让A成为B的左子树
//③将根结点设定为结点B

void L(node* &root) {
	node* p = root->right;
	root->right = p->left;
	p->left = root;
	updateHeight(root);
	updateHeight(p);
	root = p;
}

//右旋(Right Rotation)算法思想：
//①让A的右子树◆成为B的左子树
//②让B成为A的右子树
//③将根结点设定为结点A

void R(node* &root) {
	node* p = root->left;
	root->left = p->right;
	p->right = root;
	updateHeight(root);
	updateHeight(p);
	root = 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
27
28
29
30
31
32
33
34
35
36
//只要把最靠近插入结点的失衡结点调整到正常，路径上的所有结点就都会正常(可证明)
//分LL型、LR型、RR型、RL型
//LR -> LL | RL -> RR
void insert(node* &root, const int v) {
	if(root == NULL) { //插入位置
		root = new node;
		root->v = v;
		root->height = 1;
		root->left = root->right = NULL;
		return;
	}
	if(v < root->v) {
		insert(root->left, v);
		updateHeight(root);
		if(getBalanceFactor(root) == 2) {
			if(getBalanceFactor(root->left) == 1) //LL型
				R(root);
			else if(getBalanceFactor(root->left) == -1) { //LR型
				L(root->left);
				R(root);
			}
		}
	}
	else {
		insert(root->right, v);
		updateHeight(root);
		if(getBalanceFactor(root) == -2) {
			if(getBalanceFactor(root->right) == -1) //RR型
				L(root);
			else if(getBalanceFactor(root->left) == 1) { //RL型
				R(root->right);
				L(root);
			}
		}
	}
}

AVL树的建立

1
2
3
4
5
node* create(int data[]) {
	node* root = NULL;
	for(const auto v : data) insert(root, v);
	return root;
}

并查集

* 合并：合并两个集合
* 查找：判断两个元素是否在一个集合
* 并查集产生的每一个集合都是一棵树
* int father[N]; //并查集数组

初始化

1
2
for(int i = 1; i <= N; i++)
	father[i] = i;

查找

1
2
3
4
5
6
7
8
9
10
//iterator
int findFather(int x){
	while(x != father[x]) x = father[x];
	return x;
}
//recursion
int findFather(int x) {
	if(x == father[x]) return x;
	else return findFather(father[x]);
}

合并

1
2
3
4
5
6
void Union(int a, int b) {
	int faA = findFather(a);
	int faB = findFather(b);
	if(faA != faB)
		father[faA] = faB;
}

路径压缩

1
2
3
4
5
6
7
8
9
10
11
12
//算法思想：
//①按原来的写法获得v的根结点root
//②重新从v开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲//全部改为根结点
int findFather(int v) { //T(n) = O(1)
	if(v == father[v]) return v; // 找到根结点
	else {
		//让当前结点v的父亲全部改为根结点
		int root = findFather(father[v]);
		father[v] = root;
		return root;
	}
}

堆与堆排序

* 堆是一个完全二叉树
* 大顶堆 和 小顶堆
* 堆可以用来实现优先队列
* int heap[maxn], n; // n为元素个数

向下调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//向下调整 T(n) = O(logn)
//其中low为欲调整的数组下表，high一般为堆的最后一个元素的数组下标
void downAdjust(int low, int high) {
	int i = low, j = i * 2;
	while(j <= high) {
		if(j + 1 <= high && heap[j+1] > heap[j])
			j = j + 1;
		if(heap[j] > heap[i]) {
			swap(heap[j], heap[i]);
			i = j;
			j = i * 2;
		}
		else break;
	}
}

建堆

1
2
3
4
5
6
7
8
//从最后一名同学位置开始，从下往上 从右往左
//左轮·D·普拉西多
// T(n) = O(n)
void createHeap() {
	for (int i = n / 2; i >= 1; i--) {
		downAdjust(i, n);
	}
}

删除堆顶

1
2
3
4
5
// T(n) = O(n)
void deleteTop(){
	heap[1] = heap[n--]; //用最后一个元素覆盖堆顶元素，并让元素个数减1
	downAdjust(1,n);
}

向上调整

1
2
3
4
5
6
7
8
9
10
11
12
// T(n) = O(logn)
void upAdjust(int low, int high) {
	int i = high, j = i / 2;
	while(j >= low){
		if(heap[i] > heap[j]){
			swap(heap[i], heap[j]);
			i = j;
			j = i / 2;
		}
		else break;
	}
}

堆的插入

1
2
3
4
void insert(node* root, int x) {
	heap[++n] = x; // 加入到堆最后一个元素后面，并让元素个数加1
	upAdjust(1, n);
}

堆排序(heap sort)

1
2
3
4
5
6
7
void heapSort() {
	createHeap();
	for (int i = n; i > 1; i--){
		swap(heap[1], heap[i]);
		downAdjust(1,i - 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
//算法思想：
//反复选择两个最小的元素，合并，直到只剩下一个元素
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

priority_queue<long long, vector<long long>, greater<long long> > q;

int main() {
	int n;
	long long temp, x, y, ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%lld", &temp);
		q.push(temp);
	}
	while(q.size() > 1) {
		x = q.top();
		q.pop();
		y = q.top();
		q.pop();
		q.push(x + y);
		ans += x + y;
	}
	printf("%lld\n", ans);
	return 0;
}

本文标题:树算法

文章作者:Kino

发布时间:2020年03月13日 - 07时46分

最后更新:2020年03月17日 - 23时05分

原始链接:https://cybaol.github.io/2020/03/13/Tree/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 二叉树的遍历
    1. 1.1. 层序遍历
  2. 2. 建立二叉树
    1. 2.1. 已知先序中序
  3. 3. 二叉查找树(BST)
    1. 3.1. 查找操作
    2. 3.2. 插入操作
    3. 3.3. 二叉查找树的建立
    4. 3.4. 二叉查找树的删除
  4. 4. 平衡二叉树(AVL树)
    1. 4.1. 查找操作
    2. 4.2. 插入操作
    3. 4.3. AVL树的建立
  5. 5. 并查集
    1. 5.1. 初始化
    2. 5.2. 查找
    3. 5.3. 合并
    4. 5.4. 路径压缩
  6. 6. 堆与堆排序
    1. 6.1. 向下调整
    2. 6.2. 建堆
    3. 6.3. 删除堆顶
    4. 6.4. 向上调整
    5. 6.5. 堆的插入
    6. 6.6. 堆排序(heap sort)
  7. 7. 哈夫曼树
,