树结构练习题

https://www.mfstem.org/

P648单词查找树

由于题目强调了这一定是棵二叉树,所以我们不需要模拟二叉树,直接计算结点数量。具体方法:

  1. 将所给单词排序。

  2. 判断当前单词与前一单词关系,有几个字符不一样,就多开几个结点。

易错点:答案初始化,应该直接加上第一个单词的长度,然后再加上一个根节点。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<string>vec;
int main() {
	string s1;
	int n=0;
	while(cin >> s1) {
		vec.push_back(s1);
	}
	sort(vec.begin(),vec.end());
	int ans=vec[0].size();
/*	for(int i=0 ; i < vec.size() ; i++)
		cout << vec[i] << endl;*/
	for(int i=1; i < vec.size() ; i++)
		for(int j=0 ; j < vec[i].size() ; j++)
			if(vec[i][j]!=vec[i-1][j]){
				ans+=vec[i].size()-j;
				break;
			}
	cout << ans+1;
}

tip:快读、快出模板

inline int read()
{
	int x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch-='0');
		ch=getchar(); 
	}
	return x*f;
}
inline void write(int x) //快出
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9)
    {
    	write(x/10);
	}
    putchar(x%10+'0');
}

P652. 小球(drop)

水题,题目说了满二叉树,一下子开朗起来了,vis记录是否有数字,block模拟题目的布尔,tree记录数值。

(这题应该可以改成构造题)

#include<bits/stdc++.h>
using namespace std;
bool block[1<<21];
int tree[1<<21];
int main(){
	int d,ot;
	cin >> d >> ot;
	int maxn = 1<<d;
	for(int i=1; i <= ot ;i++){
		int ball = 1;
		while(ball*2 + 1 < maxn ){
/*如果这个节点是false,则这个球把它变成true,然后从左子树走*/
			block[ball] = !block[ball];
			if(block[ball]){
				if(tree[ball*2]) break;
				ball*=2;
			}
			else{
				if(tree[ball*2+1]) break;
				ball = ball*2+1;
			}
		}
		tree[ball] = i;
		if(i==ot){
			cout << ball << endl;
			return 0;
		}
	}
}

P654FBI树(fbi)

2^n个结点,明显完全二叉树,用数组做很友好

判断全零和全一挺麻烦的,用递归去查有O(n²)的时间复杂度,我不能接受。

我选择从叶结点开始,把他们都给加起来,查和,然后对应F、B、I。

全零,那加起来就是零。

全一有点麻烦,全一的和是和层数反向相关的,如果用递归写个函数,查上一层满一的值,然后乘2得到这一层满一的值,自然可以,我这里写的不好,写了个init函数从1开始算全一的值,太麻烦了,不好理解。

除去全一和全零就是01都有了。

#include<iostream>
#include<cstdio>
using namespace std;
int tree[1<<12],I[1<<12];
bool vis[1<<12];
int n,topLimit;
int init() {
	int front=n;
	for(int i=1; i <= 1<<(n+1) ; i++) {
		if(i>(1<<(n-front+1))-1) front--;
		I[i] = (1<<front);
	}
}
int find(int N) {
	if(N >= (topLimit<<1) ) {
		cout << "wrong" << endl;
		return 0;
	}
	if(vis[N]) return tree[N];
	vis[N] = true;
	tree[N]=find(N*2)+find(N*2+1);
	return tree[N];
}
void traversal(int N) {
	if(N >= (topLimit<<1)) return;
	traversal(N*2);
	traversal(N*2+1);
	if(tree[N]==0) {
		putchar('B');
		return;
	}
	if(tree[N]==I[N]) {
		putchar('I');
		return;
	}
	putchar('F');
	return;
}
int main() {
	cin >> n;
	init();
	topLimit = 1<<n;
	getchar();
	for(int i=0 ; i < topLimit ; i++) {
		char ch = getchar();
		tree[topLimit+i] = ch-'0';
		vis[topLimit+i]=true;
	}
	find(1);
	traversal(1);
}
上一篇:C++中高精度运算总结


下一篇:最短路/次短路/K短路