树
徐仓仓 Lv3
  2022-08-09 21:34:44 2022-08-09 21:34    

📅time:8.09 - 8.13

🍔题目：

1094 25 The Largest Generation 树 DFS or BFS(哪一层的结点数量最多)
1053 30 Path of Equal Weight 树 DFS 路径和，并且记录路径（路径权重求和，记录路径）
1079 25 Total Sales of Supply Chain 树 DFS 叶子节点求和（计算叶子节点深度）
1090 25 Highest Price in Supply Chain 树 DFS 深度最大（计算最大深度）
1106 25 Lowest Price in Supply Chain 树 DFS 深度最小
1004 30 Counting Leaves 树 BFS 每层有几个叶子节点（分别计算每层的叶子节点数量）
1086 25 Tree Traversals Again 二叉树 顺序转变 先序+中序=>后序（注意参数）
1102 25 Invert a Binary Tree 二叉树 输出层序、中序（基础题）
1020 25 Tree Traversals 二叉树 后序+中序=>层序 懒得重新做（注意参数）
1043 25 Is It a Binary Search Tree BST二叉搜索树 建树、各种顺序输出（已知前序，反转搜索树）
1064 30 Complete Binary Search Tree ☆ BST二叉搜索树+CBT完全二叉树 中序转CBT、层序输出（不会，只想到了中序）
1099 30 Build A Binary Search Tree BST二叉搜索树 已知树的结构和序列，层序输出（和上一题相似）
1066 25 Root of AVL Tree ☆ AVL树 插入操作 第一次写不是很熟
1107 30 Social Clusters 并查集 基础操作 第一次写不是很熟
1098 25 Insertion or Heap Sort 堆 基础操作 第一次写不是很熟

注意如果当前的变量是下标还是目标值

二叉搜索树：

  1. 对BST进行中序遍历，遍历的结果是有序的。
  2. 数组就是层序遍历
  3. 中序+树的结构可以获得整棵树

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int root, int sum) {
	temp.push_back(root);
	if (sum > S) return;
	if (sum == S) {
		if (tree[root].size() == 0) {
			path.push_back(temp);
		}
		//temp.pop_back();
		return;
	}
	for (int i = 0; i < tree[root].size(); i++) {
		dfs(tree[root][i], sum + weight[tree[root][i]]);
		temp.pop_back();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int root, int sum) {
	if (sum > S) return;
	if (sum == S) {
		if (tree[root].size() == 0) {
			path.push_back(temp);
		}
		//temp.pop_back();
		return;
	}
	for (int i = 0; i < tree[root].size(); i++) {
        temp.push_back(tree[root][i]);
		dfs(tree[root][i], sum + weight[tree[root][i]]);
		temp.pop_back();
	}
}
int main(){
    //……
	temp.push_back(root);
}

树

🍧满足连通、边数等于顶点数减1的结构一定是一棵树

静态写法构造树

  1. 结点没有数据，可能有多个孩子，利用vector数组记录，将结点的孩子push_back进父节点的数组中。

    🎈1094 The Largest Generation

    1
    2
    vector<int> Node[MAXN];
    Node[1].push_back(2);//2是1的孩子

  2. 结点有数据，并且树的结点按照下标构成，可以考虑开创一个数组来记录数据

🎈1079 Total Sales of Supply Chain

1
2
3
4
vector<int> chain[100010];
int project[100010];
project[1] = 10;//1号结点的数据是10
chain[1].push_back(2);//2是1的孩子

  1. 结点有数据，可能有多个孩子，构造结构体

    🎈1053 Path of Equal Weight

    1
    2
    3
    4
    5
    struct node {
    	int data;
    	vector<int> child;//储存孩子在tree中的索引
    };
    node tree[110];

树的宽度优先

利用队列

🎈1004 Counting Leaves

1
2
3
4
5
6
7
8
9
10
11
12
13
//BFS
queue<node>q;
void BFS() {
	while (!q.empty()) {
		node top = q.front();
		q.pop();
		……
		for (int i = 0; i < top.child.size(); i++) {
			……
			q.push(tree[top.child[i]]);
		}
	}
}

二叉树

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node {
	int data;
	node* lchild = NULL;
	node* rchild = NULL;
};
node* root = new node();
root -> data = 1;

//插入
void insert(node* &root,int x){//一定要注意这里有引用
	if(root == NULL){
        root = new node(x);
        return;
    }
    if(x < root->data){
        insert(root->lchild, x);
    }
    else insert(root->rchild, x);
}

遍历转换

中序序列可与先序序列、后序序列、层序序列中的任意一个来构造唯一的二叉树

先序+中序=>后序

🎈1086 Tree Traversals Again

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//1、得到先序pre[maxn]和中序in[maxn]数组；
int pre[maxn],in[maxn];
……
//2、构造后序
node* create(int preL, int preR, int inL, int inR) {
    //若函数参数表达范围是[preL,preR]、[inL,inR]，递归结束条件为if (preL > preR)
	if (preL + 1 > preR) {//函数参数表达范围是[preL,preR)、[inL,inR)
		return NULL;
	}
	node* root = new node();
    root->data = pre[preL];
	int i = inL;
	for (; i < inR; i++) {
		if (pre[preL] == in[i])
			break;
	}
    root->lchild = create(preL + 1, preL + i - inL + 1, inL, i);
	root->rchild = create(preL + i - inL + 1, preR, i + 1, inR);
	return root;
}

二叉查找树BST

  • 对BST进行中序遍历，遍历的结果是有序的。

完全二叉树CBT

  • 满二叉树：每一层都是满的

    完全二叉树：除最后一层都是满的

  • 使用数组存放，则对于任何一个结点（设编号为n，根节点编号为1），其左孩子的下标为2n，右孩子为2n+1。

  • CBT数组本身就是层序遍历

  1. 输入一串序列，可以得到唯一一颗完全二叉查找树

    🎈1064 Complete Binary Search Tree

    题解：

    1. 对输入序列排序，排序后的数组，就是二叉查找树的中序遍历结果。
    2. 根据中序和完全二叉树下标性质，得到CBT数组。
    3. CBT数组本身就是层序遍历，输出。

    已知中序遍历，求完全二叉树

    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
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int N, num[1010];
    bool cmp(int a, int b) {
    	return a < b;
    }
    int cbt[1010], index = 0;
    void inorder(int root) {
    	if (root > N) return;
    	inorder(root * 2);
    	cbt[root] = num[index++];
    	inorder(root * 2 + 1);
    }
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; i++) {
    		cin >> num[i];
    	}
    	sort(num, num + N, cmp);
    	//num是结果的中序遍历
    	inorder(1);
    	for (int i = 1; i < N; i++) {
    		cout << cbt[i] << " ";
    	}
    	cout << cbt[N] << endl;
    }

AVL平衡二叉树

结点定义

需记录高度

1
2
3
4
struct node{
	int v, height = 1;
	node* left = NULL, right = NULL;
}

插入操作

:heart:注意：左旋、右旋、插入的参数是node* &root，加引用是因为会对root进行修改，需要记录最新的根节点。

共六个函数：得到高度、更新高度、计算平衡因子、右旋、左旋、插入。

树形 平衡因子 操作
LL / root=2,root->left=1 root右旋
LR < root=2,root->left=-1 root->left左旋，root右旋
RR \ root=-2,root->right=-1 root左旋
RL > root=-2,root->right=1 root->right右旋，root左旋

高度

得到

1
2
3
4
int getHeight(node* root) {
	if (root == NULL) return 0;//注意root为空的情况
	return root->height;
}

更新

1
2
3
void update(node* root) {
	root->height = max(getgetHeight(root->left), getgetHeight(root->right)) + 1;
}

平衡因子

1
2
3
int balance(node* root) {
	return getHeight(root->left) - getHeight(root->right);
}

右旋

1
2
3
4
5
6
7
8
void R(node* &root) {//引用
	node* temp = root->left;
	root->left = temp->right;
	temp->right = root;
	update(root);//注意更新顺序
	update(temp);
	root = temp;
}

左旋

1
2
3
4
5
6
7
8
void L(node*& root) {//引用
	node* temp = root->right;
	root->right = temp->left;
	temp->left = root;
	update(root);
	update(temp);
	root = temp;
}

插入

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
void insert(node*& root, int num) {//引用
	if (root == NULL) {
		root = new node();
		root->data = num;
		return;
	}
	if (num < root->data) {
		insert(root->left, num);
		update(root);
		if (balance(root) >= 2) {
			if (balance(root->left) > 0) {
				R(root);
			}
			else {
				L(root->left);
				R(root);
			}
		}
	}
	else {
		insert(root->right, num);
		update(root);
		if (balance(root) <= -2) {//注意有等号
			if (balance(root->right) < 0) {
				L(root);
			}
			else {
				R(root->right);
				L(root);
			}
		}
	}
}
1
2
3
4
5
node* root = NULL;//注意初始化为NULL
for (int i = 0; i < N; i++) {
    cin >> temp;
    insert(root, temp);
}

并查集

1
int father[N];

初始化

1
2
3
for (int i = 1; i <= N; i++) {
		f[i] = i;
	}

查找+压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
int findfather(int x){
	int z = x;
	while(x != f[x]){
		x = f[x];
	}
	//此时x是根节点
	while(f[z] != x){
		int t = f[z];
		f[z] = x;
		z = t;
	}
	return x;
}

合并

1
2
3
4
5
6
7
void merge(int a, int b){
	int fa = findfather(a);
	int fb = findfather(b);
	if(fa != fb){
		f[fa]=  fb;
	}
}

堆

  • 属于完全二叉树，**利用数组存放[1,N]**。

    非叶子结点：**[1,N/2]**💕

    对于结点N，孩子结点为2N、2N+1，父节点为N/2

    int num[maxn];

向下调整

用于建堆、堆排序、删除数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//在[low,heigh]范围内调整，low为欲调整结点
void downAdjust(int low, int heigh) {
	int child = low * 2;
	while (child <= heigh) { //有孩子
		if (child + 1 <= heigh && num[child] < num[child + 1]) {//有右孩子，且右孩子更大
			child++;//指向右孩子
		}
		if (iter[low] < iter[child]) {
			swap(iter[low], iter[child]);
			low = child;
			child = low * 2;
		}
		else {
			break;//该结点调整结束
		}
	}
}

建堆

下文以大顶堆为例，若最后想得到升（降）序序列，需先构造大（小）顶堆。

从最后非一个叶子结点N/2开始，向下调整，将更大的值往上放

1
2
3
4
5
6
7
void create(){
    //输入
    //……
    for(int i = N / 2; i >= 1; i--){//从最后非一个叶子结点倒着进行
        downAdjust(i, N);
    }
}

堆排序

在大顶堆的基础上

  1. 交换根节点和最后一个未确定的结点swap(N[1],N[heigh])
  2. 在[1,heigh-1]的范围内向下调整，1为欲调整结点
  3. 不断重复1、2
1
2
3
4
5
6
7
void sort(){
    create();
	for(int i = N; i > 1; i --){
        swap(num[1], num[i]);
        downAdjust(1, i);
    }
}

删除堆顶

num[1,N]是一个大顶堆

  1. 交换最后一个元素和堆顶
  2. 堆长度-1
  3. 对新堆顶进行向下调整
1
2
3
4
5
void delete(){
	swap(num[1],num[N]);
    N--;
    downAdjust(1, N);
}

向上调整

用于插入

1
2
3
4
5
6
7
8
9
10
11
12
13
void upAdjust(int low,int heigh){
	int father = heigh / 2;
	while(heigh >= low){
        if(num[heigh] > num[father]){
            swap(num[heigh], num[father]);
            heigh = father;
            father = heigh / 2;
        }
        else{
            break;
        }
    }
}

插入

插入于最后一个位置，再进行向上调整

1
2
3
4
void insert(int x){
	num[++N] = x;
	upAdjust(1, N);
}

哈夫曼树

recursively ：递归地

traversal ：遍历;穿越;追踪;周游;树的遍历

sequence ： 序列; 顺序; 按顺序排列;

附录

1094 The Largest Generation BFS or DFS

BFS

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
44
45
46
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
	int data,layer;
};
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> family[110];
	int ID, K, child;
	for (int i = 0; i < M; i++ ) {
		cin >> ID >> K;
		for (int j = 0; j < K; j++) {
			cin >> child;
			family[ID].push_back(child);
		}
	}
	queue<node*>q;
	node* root = new node();
	root->layer = 1;
	root->data = 1;
	q.push(root);
	int num[110];
	fill(num, num + 110, 0);
	while (!q.empty()) {
		node* top = q.front();
		q.pop();
		num[top->layer]++;
		for (int i = 0; i < family[top->data].size(); i++) {
			node* temp = new node();
			temp->data = family[top->data][i];
			temp->layer = top->layer + 1;
			q.push(temp);
		}
	}
	int max = 1, maxlay = 1;
	for (int i = 2; i <= N; i++) {
		if (num[i] > num[maxlay]) {
			maxlay = i;
			max = num[i];
		}
	}
	cout << max << " " << maxlay << endl;
}

DFS

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
#include <iostream>
#include <vector>
using namespace std;
vector<int> family[110];
int layer[110];
void DFS(int root,int height) {
	layer[height]++;
	for (int i = 0; i < family[root].size(); i++) {
		DFS(family[root][i], height + 1);
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	int ID, n, child;
	for (int i = 0; i < M; i++) {
		cin >> ID >> n;
		for (int j = 0; j < n; j++) {
			cin >> child;
			family[ID].push_back(child);
		}
	}
	fill(layer, layer + 110, 0);
	DFS(1, 1);
	int max = 1, maxlayer = 1;
	for (int i = 2; i < N; i++) {
		if (layer[i] > maxlayer) {
			maxlayer = layer[i];
			max = i;
		}
	}
	cout << maxlayer << " " << max << endl;
}

1053 Path of Equal Weight

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node {
	int data;
	vector<int> child;
};
node tree[110];
vector<int>temp;
vector<vector<int> >ans;
int n, m, w;
void dfs(int index, int weight) {
	node root = tree[index];
	weight += root.data;
	if (tree[index].child.size() == 0 && weight == w) {
			ans.push_back(temp);
		return;
	}
	if (weight >= w) {
		return;
	}
	for (int i = 0; i < tree[index].child.size(); i++) {
		int id = tree[index].child[i];
		temp.push_back(tree[id].data);
		dfs(id, weight);
		temp.pop_back();
	}
}
bool cmp(vector<int> a,vector<int> b ) {
	int i = 0;
	for (; i < a.size() && i < b.size(); i++) {
		if (a[i] > b[i]) {
			return true;
		}
		if (a[i] < b[i])
			return false;
	}
	if (i < a.size()) return  true;
	else return false;
}
int main() {
	cin >> n >> m >> w;
	int a;
	for (int i = 0; i < n; i++) {
		cin >> a;
		tree[i].data = a;
	}
	int id1, num, id2;
	for (int i = 0; i < m; i++) {
		cin >> id1 >> num;
		for (int j = 0; j < num; j++) {
			cin >> id2;
			tree[id1].child.push_back(id2);
		}
	}
	temp.push_back(tree[0].data);
	dfs(0, 0);
	sort(ans.begin(), ans.end(), cmp);
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < ans[i].size()-1; j++) {
			cout << ans[i][j] << " ";
		}
		cout << ans[i][ans[i].size() - 1] << endl;
	}
}

1079 Total Sales of Supply Chain

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
#include<iostream>
#include<vector>
using namespace std;
int N;
double P, r;
vector<int> chain[100010];
int project[100010];
double ans = 0;
void DFS(int root,double price) {
	if (chain[root].size() == 0) {
		ans += price * project[root];
		return;
	}
	for (int i = 0; i < chain[root].size(); i++ ) {
		DFS(chain[root][i], (1 + r * 0.01) * price);
	}
}
int main() {
	cin >> N >> P >> r;
	fill(project, project + 100010, 0);
	int num, temp;
	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num == 0) {
			cin >> temp;
			project[i] = temp;
		}
		for (int j = 0; j < num; j++) {
			cin >> temp;
			chain[i].push_back(temp);
		}
	}
	DFS(0, P);
	printf("%.1f\n", ans);
}

1090 Highest Price in Supply Chain

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
#include<iostream>
#include<vector>
using namespace std;
int N;
double P, r;
vector<int> chain[100010];
double maxprice = 0;
int maxnum = 0;
void DFS(int root, double price) {
	if (chain[root].size() == 0) {
		cout << "price" << price << endl;
		if (price > maxprice) {
			maxprice = price;
			maxnum = 1;
		}
		else if (price == maxprice) {
			maxnum++;
		}
		return;
	}
	for (int i = 0; i < chain[root].size(); i++) {
		DFS(chain[root][i], (1 + r * 0.01) * price);
	}
}
int main() {
	cin >> N >> P >> r;
	int temp, root = -1;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		if (temp == -1) {
			root = i;
			continue;
		}
		chain[temp].push_back(i);
	}
	DFS(root, P);
	printf("%.2f %d\n", maxprice, maxnum);
}

1106 Lowest Price in Supply Chain

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
#include<iostream>
#include<vector>
using namespace std;
int N;
double P, r;
vector<int> chain[500010];
int minnum = 0, minlayer = 500010;
void DFS(int root,int layer) {
	if (chain[root].size() == 0) {
		if (layer < minlayer) {
			minlayer = layer;
			minnum = 1;
		}
		else if (layer == minlayer) {
			minnum++;
		}
		return;
	}
	for (int i = 0; i < chain[root].size(); i++) {
		DFS(chain[root][i], layer + 1);
	}
}
int main() {
	cin >> N >> P >> r;
	int num, temp;
	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num == 0) {
			continue;
		}
		for (int j = 0; j < num; j++) {
			cin >> temp;
			chain[i].push_back(temp);
		}
	}
	DFS(0, 0);
	double price = pow((1 + r * 0.01), minlayer)  * P;
	printf("%.4f %d\n", price, minnum);
}

1004 Counting Leaves

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
44
45
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, M;
struct node {
	int layer = 0;
	vector<int> child;
};
node chain[110];
queue<node>q;
int number[110], level = 0;
void BFS() {
	while (!q.empty()) {
		node top = q.front();
		q.pop();
		if (level < top.layer)
			level = top.layer;
		if (top.child.size() == 0) {
			number[top.layer]++;
		}
		for (int i = 0; i < top.child.size(); i++) {
			chain[top.child[i]].layer = top.layer + 1;
			q.push(chain[top.child[i]]);
		}
	}
}
int main() {
	cin >> N >> M;
	int id, num, temp;
	for (int i = 0; i < M; i++) {
		cin >> id >> num;
		for (int j = 0; j < num; j++) {
			cin >> temp;
			chain[id].child.push_back(temp);
		}
	}
	q.push(chain[1]);
	BFS();

	for (int i = 0; i <= level - 1; i++) {
		cout << number[i] << " ";
	}
	cout << number[level] << endl;
}

1086 Tree Traversals Again 中序=>后序

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
int N;
vector<int> postorder;
struct node {
	int data;
	node* rchild = NULL, * lchild = NULL;
};
stack<node*> q;
void post(node* root) {
	if (root == NULL)
		return;
	post(root->lchild);
	post(root->rchild);
	postorder.push_back(root->data);
}
int main() {
	cin >> N;
	string s;
	int temp;
	cin >> s >> temp;
	node* root = new node();
	root->data = temp;
	node* top = root;
	q.push(root);
	bool flag = true;//true:往左插入孩子，false：右
	for (int i = 0; i < 2 * N - 1; i++) {
		cin >> s;
		if (s == "Pop") {
			top = q.top();
			q.pop();
			flag = false;
		}
		if (s == "Push") {
			cin >> temp;
			if (flag) {
				top->lchild = new node();
				top = top->lchild;
				top->data = temp;
				q.push(top);
			}
			else {
				top->rchild = new node();
				top = top->rchild;
				top->data = temp;
				q.push(top);
			}
			flag = true;
		}
	}
	post(root);
	for (int i = 0; i < postorder.size() - 1; i++) {
		cout << postorder[i] << " ";
	}
	cout << postorder[postorder.size() - 1] << endl;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//先序+中序=>后序
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int N, pre[31], in[31], post[31];
struct node {
	int data;
	node* lchild = NULL;
	node* rchild = NULL;
};
node* create(int preL, int preR, int inL, int inR) {
	if (preL + 1 > preR) {
		return NULL;
	}
	node* root = new node();
	root->data = pre[preL];
	int i = inL;
	for (; i < inR; i++) {
		if (pre[preL] == in[i])
			break;
	}
	root->lchild = create(preL + 1, preL + i - inL + 1, inL, i);
	root->rchild = create(preL + i - inL + 1, preR, i + 1, inR);
	return root;
}
int n = 0;
void postorder(node* root) {
	if (root == NULL) {
		return;
	}
	postorder(root->lchild);
	postorder(root->rchild);
	post[n++] = root->data;
}
int main() {
	cin >> N;
	string s;
	int temp, innum = 0, prenum = 0;
	stack<int>q;
	for (int i = 0; i < 2 * N; i++) {
		cin >> s;
		if (s=="Push") {
			cin >> temp;
			q.push(temp);
			pre[prenum++] = temp;
		}
		if (s == "Pop") {
			in[innum++] = q.top();
			q.pop();
		}
	}
	node* root = create(0, N, 0, N);
	postorder(root);
	for (int i = 0; i < N - 1; i++) {
		cout << post[i] << " ";
	}
	cout << post[N - 1] << endl;
}

1102 Invert a Binary Tree 输出层序、中序

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
struct node {
	int rchild = -1;
	int lchild = -1;
};
bool flag[10];
node tree[10];
int root;
vector<int>layer;
vector<int>in;
queue<int> q;
void layerorder() {
	q.push(root);
	while (!q.empty()) {
		int top = q.front();
		layer.push_back(top);
		q.pop();
		if (tree[top].lchild!=-1) {
			q.push(tree[top].lchild);
		}
		if (tree[top].rchild!=-1) {
			q.push(tree[top].rchild);
		}
	}
}
void inorder(int root) {
	if (tree[root].lchild != -1) {
		inorder(tree[root].lchild);
	}
	in.push_back(root);
	if (tree[root].rchild != -1) {
		inorder(tree[root].rchild);
	}
	return;
}
int main(){
	fill(flag, flag + 10, false);
	cin >> N;
	char l, r;
	for (int i = 0; i < N; i++) {
		cin >> r >> l;
		if (r <= '9' && r >= '0') {
			tree[i].rchild = r - '0';
			flag[r - '0'] = true;
		}
		if (l <= '9' && l >= '0') {
			tree[i].lchild = l - '0';
			flag[l - '0'] = true;
		}
	}
	for (int i = 0; i < N; i++) {
		if (!flag[i]) {
			root = i;
			break;
		}
	}
	layerorder();
	for (int i = 0; i < N - 1; i++) {
		cout << layer[i] << " ";
	}
	cout << layer[N - 1] << endl;
	inorder(root);
	for (int i = 0; i < N - 1; i++) {
		cout << in[i] << " ";
	}
	cout << in[N - 1] << endl;
}

1043 Is It a Binary Search Tree

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N,num[1010];
struct node {
	int data;
	node* left = NULL, * right = NULL;
};
void insert(node* &root, int n) {
	if (root == NULL) {
		root = new node();
		root->data = n;
		return;
	}
	if (n < root->data) {
		insert(root->left, n);
	}
	else {
		insert(root->right, n);
	}
}
vector<int>preorder;
void pre(node* root) {
	if (root == NULL)
		return;
	preorder.push_back(root->data);
	pre(root->left);
	pre(root->right);
}
vector<int>repreorder;
void repre(node* root) {
	if (root == NULL)
		return;
	repreorder.push_back(root->data);
	repre(root->right);
	repre(root->left);
}
vector<int>postorder;
void post(node* root) {
	if (root == NULL)
		return;
	post(root->left);
	post(root->right);
	postorder.push_back(root->data);
}
vector<int>repostorder;
void repost(node* root) {
	if (root == NULL)
		return;
	repost(root->right);
	repost(root->left);
	repostorder.push_back(root->data);
}
bool judge(vector<int>& n) {
	for (int i = 0; i < N; i++) {
		if (num[i] != n[i]) {
			return false;
		}
	}
	return true;
}
int main() {
	cin >> N;
	node* root = NULL;
	for (int i = 0; i < N ; i++) {
		cin >> num[i];
		insert(root, num[i]);
	}

	pre(root);
	repre(root);
	if (judge(preorder)) {
		cout << "YES" << endl;
		post(root);
		for (int i = 0; i < postorder.size()-1; i++) {
			cout << postorder[i] << " ";
		}
		cout<< postorder[postorder.size() - 1] << endl;
	}
	else if (judge(repreorder)) {
		cout << "YES" << endl;
		repost(root);
		for (int i = 0; i < repostorder.size()-1; i++) {
			cout << repostorder[i] << " ";
		}
		cout << repostorder[repostorder.size() - 1] << endl;
	}
	else cout << "NO" << endl;
}

1064 Complete Binary Search Tree

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int N,num[1010];
struct node {
	int data;
	node* right = NULL;
	node* left = NULL;
};
queue<node*>q;
node* CBT(int left,int right) {
	if (left >= right)
		return NULL;
	if (left + 1 == right) {
		node* root = new node();
		root->data = num[left];
		//cout << num[left] << endl;
		return root;
	}
	int n = right - left;//该树共n个结点
	int k = log(n) / log(2) ;//前k层是满的
	int k_num = pow(2, k) - 1;// 前k层有k_num个结点
	int last_num = n - k_num;//最后一层结点个数
	int last_left = (last_num - (int)(pow(2, k - 1)))>=0?(int)(pow(2, k - 1)): last_num;
	int root_index = (k_num - 1) / 2 + last_left + left;
	node* root = new node();
	//cout << num[root_index] << endl;
	root->data = num[root_index];
	root->left = CBT(left, root_index);
	root->right = CBT(root_index + 1, right);
	return root;
}
vector<int>layerorder;
void layer() {
	while (!q.empty()) {
		node* top = q.front();
		q.pop();
		layerorder.push_back(top->data);
		if (top->left != NULL) {
			q.push(top->left);
		}
		if (top->right != NULL) {
			q.push(top->right);
		}
	}
}
bool cmp(int a, int b) {
	return a < b;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sort(num, num + N,cmp);
	node* root = NULL;
	root = CBT(0, N);
	q.push(root);
	layer();
	for (int i = 0; i < N - 1; i++) {
		cout << layerorder[i] << " ";
	}
	cout << layerorder[N - 1] << endl;
}
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
#include<iostream>
#include<algorithm>
using namespace std;
int N, num[1010];
bool cmp(int a, int b) {
	return a < b;
}
int cbt[1010], index = 0;
void inorder(int root) {
	if (root > N) return;
	inorder(root * 2);
	cbt[root] = num[index++];
	inorder(root * 2 + 1);
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sort(num, num + N, cmp);
	//num是结果的中序遍历
	inorder(1);
	for (int i = 1; i < N; i++) {
		cout << cbt[i] << " ";
	}
	cout << cbt[N] << endl;
}

1099 Build A Binary Search Tree

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
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
bool cmp(int a, int b) {
	return a < b;
}
const int maxn = 110;
int N,num[maxn];
struct node {
	int left = -1;
	int right = -1;
};
node tree[maxn];
int number = 0;
int BST[maxn];
void inorder(int root) {
	if (number > N) return;
	if (tree[root].left != -1) {
		inorder(tree[root].left);
	}
	BST[root] = num[number++];
	if (tree[root].right != -1) {
		inorder(tree[root].right);
	}
}
queue<int>q;
vector<int> layerorder;
void layer() {
	q.push(0);
	while (!q.empty()) {
		int top = q.front();
		layerorder.push_back(BST[top]);
		q.pop();
		if (tree[top].left != -1)
			q.push(tree[top].left);
		if (tree[top].right != -1)
			q.push(tree[top].right);
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tree[i].left >> tree[i].right;
	}
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sort(num, num + N, cmp);
	inorder(0);
	layer();
	for (int i = 0; i < N - 1; i++)
		cout << layerorder[i] << " ";
	cout << layerorder[N - 1] << endl;
}

1066 Root of AVL Tree

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
using namespace std;
const int maxn = 21;
int N;
struct node {
	int data;
	int height = 1;
	node* left = NULL, * right = NULL;
};
int get(node* root) {
	if (root == NULL) return 0;
	return root->height;
}
int balance(node* root) {
	return get(root->left) - get(root->right);
}
void update(node* root) {
	root->height = max(get(root->left), get(root->right)) + 1;
}
void R(node* &root) {
	node* temp = root->left;
	root->left = temp->right;
	temp->right = root;
	update(root);
	update(temp);
	root = temp;
}
void L(node*& root) {
	node* temp = root->right;
	root->right = temp->left;
	temp->left = root;
	update(root);
	update(temp);
	root = temp;
}
void insert(node*& root, int num) {
	if (root == NULL) {
		root = new node();
		root->data = num;
		return;
	}
	if (num < root->data) {
		insert(root->left, num);
		update(root);
		if (balance(root) >= 2) {
			if (balance(root->left) > 0) {
				R(root);
			}
			else {
				L(root->left);
				R(root);
			}
		}
	}
	else {
		insert(root->right, num);
		update(root);
		if (balance(root) <= -2) {
			if (balance(root->right) < 0) {
				L(root);
			}
			else {
				R(root->right);
				L(root);
			}
		}
	}
}
int main() {
	cin >> N;
	int temp;
	node* root = NULL;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		insert(root, temp);
		//cout << root->data << endl;
	}
	cout << root->data << endl;
}

1107 Social Clusters

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
#include<map>
#include <algorithm>
using namespace std;
int cmp(int a, int b) {
	return a > b;
}
const int maxn = 1010;
int N;
int f[maxn];
vector<int>hobby;
int findfather(int x) {
	int a = x;
	while (x != f[x]) {
		x = f[x];
	}
	return x;
}
void Union(int a, int b) {
	int faA = findfather(a);
	int faB = findfather(b);
	if (faA != faB) {
		f[faA] = f[faB];
	}
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		f[i] = i;
	}
	int temp, course[maxn] = { 0 }, root[maxn] = { 0 };
	string num;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		for (int j = 0; j < atoi((num.substr(0, num.size() - 1)).c_str()); j++) {
			cin >> temp;
			if (course[temp] == 0)
				course[temp] = i;
			Union(i, findfather(course[temp]));
		}
	}
	if (N == 1) {
		cout << 1 << endl << 1;
		return 0;
	}
	for (int i = 1; i <= N; i++) {
		root[findfather(i)]++;
	}
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (root[i] != 0)
			cnt++;
	}
	printf("%d\n", cnt);
	sort(root, root + maxn, cmp);
	for (int i = 0; i < cnt; i++) {
		printf("%d", root[i]);
		if (i != cnt-1) printf(" ");
	}
}

1098 Insertion or Heap Sort

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 101;
int N, num[maxn], iter[maxn];
bool insert = false, heap = false;
void downAdjust(int low, int high) {
	int change = 2 * low;
	while (change <= high) {
		if (change + 1 < high && iter[change] < iter[change + 1]) {
			change++;
		}
		if (iter[low] < iter[change]) {
			swap(iter[low], iter[change]);
			low = change;
			change = low * 2;
		}
		else break;
	}
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> iter[i];
	}
	//判断
	int index = 2;
	while (index <= N && iter[index] >= iter[index - 1]) {
		index++;
	}
	int p = index;
	while (p <= N && num[p] == iter[p]) p++;
	if (p == N + 1) insert = true;
	else heap = true;
	if (insert) {
		cout << "Insertion Sort\n";
		sort(iter + 1, iter + index + 1);
		for (int i = 1; i <= N; i++) {
			cout << iter[i];
			if (i != N) cout << " ";
		}
	}
	if (heap) {
		cout << "Heap Sort\n";
		int high = N;
		for (; high > 1; high--) {
			if (iter[high] < iter[1]) {
				break;
			}
		}
		swap(iter[1], iter[high]);
		downAdjust(1, high - 1);
		for (int i = 1; i <= N; i++) {
			cout << iter[i];
			if (i != N) cout << " ";
		}
	}
}
 Comments