【算法】蓝桥杯2013国C 横向打印二叉树 题解

  • 开发
  • 53

文章目录

题目链接

P8603 [蓝桥杯 2013 国 C] 横向打印二叉树

题目描述

其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如图 1 1 1 所示。

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的 N N N 个整数。 N < 100 N<100 N<100，每个数字不超过 10000 10000 10000。

N N N 并没有在输入中给出。

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示,为了便于评卷程序比对空格的数目，请把空格用句点代替。

样例

自己的样例输入

5 2 3 4 45 35 11 20 15 30 25 121 1234 23 1 44 7 10 12 6

自己的样例输出

.............|-1234
.......|-121-|
..|-45-|
..|....|....|-44
..|....|-35-|
..|.........|.........|-30-|
..|.........|.........|....|-25-|
..|.........|.........|.........|-23
..|.........|....|-20-|
..|.........|....|....|-15-|
..|.........|....|.........|-12
..|.........|-11-|
..|..............|...|-10
..|..............|-7-|
..|..................|-6
5-|
..|.......|-4
..|...|-3-|
..|-2-|
......|-1

思路

整体思路

我们使用数组的方法存储二叉搜索树，定义一个长度为1010的int类型数组ns和宽度,高度都为1010的char数组mymap，一个用于存二叉树、一个用于打印二叉树。

（其实按照题目给的数据范围N<100，int数组长度不应该取1010，应该取是 2 99 2^{99} 299次方，显然也会超过内存限制。但是我亲测取1010也能过全部样例，这里就怎么简单怎么来吧）

我们用数组存储二叉搜索树，下标 x x x为根， x ∗ 2 x*2 x∗2为左节点下标， x ∗ 2 + 1 x*2+1 x∗2+1为右节点下标，按照输入顺序存储。

在中序遍历并存储，因为二叉搜索树的中序是排序了的，所以直接中序遍历输出的数字存储起来就行了，排序后方便后面计算高度。

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

上面为某个输出样例，我们观察可以不难看出，从下往上看每个数字是升序的，所以某个数字的高度h为所有大于这个数字的个数+1，这样就可以求出这个数在mymap数组的行号。列号也可以用dfs算法遍历求出。

最后做完上面的步骤，直接用dfs遍历一遍再处理一下输出就行。

存储二叉搜索树

二叉树的存储根节点的下标为1，左右节点下标为2和3，依此类推，节点下标为 x x x，那么左节点下标为 x ∗ 2 x*2 x∗2，右节点的下标为 x ∗ 2 + 1 x*2+1 x∗2+1。

int ns[1010], stn;
void insert(int x) {
   
	while (ns[stn] != -1) {
   
		if (ns[stn] > x)
			stn = stn * 2;
		else if (ns[stn] < x)
			stn = stn * 2 + 1;
	}
	ns[stn] = x;
}

这里的stn为全局变量每次插入的时候都初始为1（根节点下标）

中序遍历并存储

这里没什么好说的，直接中序排序后的数字压入vector就行了

vector<int> cn;
void in_dfs(int start) {
   
	if (ns[start] == -1)
		return;
	in_dfs(start * 2);
  	// 存储到vector，存储完后自然排好序
	cn.push_back(ns[start]);
	in_dfs(start * 2 + 1);
}
计算目标数的行号

因为排好序我们直接找到目标数所在的下标。

行号 = 数字个数 − 下标 行号=数字个数-下标 行号=数字个数−下标

vector<int> cn;
int compute_h(int w) {
   
	vector<int>::iterator it = find(cn.begin(), cn.end(), w);
	int c = it - cn.begin();
	return cn.size() - c;
}
dfs遍历并写入数组

h,w为该数字的行号和列号,max_w为整个输出的最大列号定义为全局遍历，每次迭代取最大值。start是当前迭代的数字，d_idx为当前数字在ns数组中的下标

把当前数字转换为string类型，并计算长度n。l_idx为当前数字的左节点，r_idx为当前数字的右节点，l_h为当前数字的左节点的高度，r_h为当前数字的右节点的高度。

write函数为写入，传入一些重要参数

后面按顺序进行dfs遍历，此处为前序遍历

int max_w = 0;
void dfs(int h, int w, int start, int d_idx) {
   
	if (ns[d_idx] == -1)
		return;
	max_w = max(max_w, w);
	string n = to_string(start);
	int l_idx = d_idx * 2, r_idx = d_idx * 2 + 1;
	int l_h = compute_h(ns[l_idx]), r_h = compute_h(ns[r_idx]);
	write(h, w, l_idx, r_idx, l_h, r_h, n);
	dfs(l_h, w + n.size() + 3, ns[l_idx], l_idx);
	dfs(r_h, w + n.size() + 3, ns[r_idx], r_idx);
}


void write(int h, int w, int l_idx, int r_idx, int l_h, int r_h, string n) {
   
	int len = n.size();
	// 前面部分
	if (w - 2 >= 0)
		mymap[h][w - 2] = '|';
	mymap[h][w - 1] = '-';
	//中间数字部分
	for (int i = w; i < len + w; ++i) {
   
		mymap[h][i] = n[i - w];
	}
	// 后面部分
	if (ns[l_idx] != -1 || ns[r_idx] != -1) {
   
		mymap[h][len + w] = '-';
		mymap[h][w + len + 1] = '|';
	}
	// 补充'|'
	if (l_h - h > 1 && ns[l_idx] != -1) {
   
		for (int i = h; i < l_h; ++i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
	if (h - r_h > 1 && ns[r_idx] != -1) {
   
		for (int i = h; i > r_h; --i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
}
初始化和处理输入输出
初始化

结束dfs的方式判断当前数字为-1，先初始化ns数组全部为-1。

题目要求输出的空格打印为’.‘,那么就初始化mymap数组全部为’.'。

// 初始化
memset(ns, -1, sizeof ns);
memset(mymap, '.', sizeof mymap);
处理输入

这题没有指定读入多少个数字，所以在普通的编译器上面就不知道如何结束读入，好在OJ有一个特性我们正好可以利用。

我们简单的介绍这个OJ的特性：读入文本，读到文本末尾，程序会自动停止的。

这里就先存一下根节点，再把后面的节点读入进去

// 存储二叉树
int x;
cin >> x;
ns[1] = x;
while (cin >> x) {
   
	stn = 1;
	insert(x);
}
处理输出

显然cn的长度为输出的最大行号，max_w为最大宽度，我们遍历一下这个二维字符数组就行了

for (unsigned int i = 1; i <= cn.size(); ++i) {
   
	// 这里max_w 要加上大于1的数，因为要把结束字符存入max_w外面。
    	// 反向遍历，处理结束符
	for (int j = max_w + 2; j >= 1; j --) {
   
        	if ((mymap[i][j - 1] >= '0' && mymap[i][j - 1] <= '9') || mymap[i][j - 1] == '|') {
   
            		// 存入结束字符'\0'
			mymap[i][j] = '\0';
			break;
		}
	}
    // 正向遍历，输出答案
	for (int j = 1; mymap[i][j]; ++j) {
   
		cout << mymap[i][j];
	}
	cout << endl;
}

完整的代码如下

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1010;

int max_w = 0, stn, ns[N];
vector<int> cn;
char mymap[N][N];

void insert(int x) {
   
	while (ns[stn] != -1) {
   
		if (ns[stn] > x)
			stn = stn * 2;
		else if (ns[stn] < x)
			stn = stn * 2 + 1;
	}
	ns[stn] = x;
}

void in_dfs(int start) {
   
	if (ns[start] == -1)
		return;
	in_dfs(start * 2);
	cn.push_back(ns[start]);
	in_dfs(start * 2 + 1);
}

int compute_h(int w) {
   
	vector<int>::iterator it = find(cn.begin(), cn.end(), w);
	int c = it - cn.begin();
	return cn.size() - c;
}

void write(int h, int w, int l_idx, int r_idx, int l_h, int r_h, string n) {
   
	int len = n.size();
	// 前面部分
	if (w - 2 >= 0)
		mymap[h][w - 2] = '|';
	mymap[h][w - 1] = '-';
	//中间数字部分
	for (int i = w; i < len + w; ++i) {
   
		mymap[h][i] = n[i - w];
	}
	// 后面部分
	if (ns[l_idx] != -1 || ns[r_idx] != -1) {
   
		mymap[h][len + w] = '-';
		mymap[h][w + len + 1] = '|';
	}
	// 补充'|'
	if (l_h - h > 1 && ns[l_idx] != -1) {
   
		for (int i = h; i < l_h; ++i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
	if (h - r_h > 1 && ns[r_idx] != -1) {
   
		for (int i = h; i > r_h; --i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
}


void dfs(int h, int w, int start, int d_idx) {
   
	if (ns[d_idx] == -1)
		return;
	max_w = max(max_w, w);
	string n = to_string(start);
	int l_idx = d_idx * 2, r_idx = d_idx * 2 + 1;
	int l_h = compute_h(ns[l_idx]), r_h = compute_h(ns[r_idx]);
	write(h, w, l_idx, r_idx, l_h, r_h, n);
	dfs(l_h, w + n.size() + 3, ns[l_idx], l_idx);
	dfs(r_h, w + n.size() + 3, ns[r_idx], r_idx);
}

int main() {
   
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	// 初始化
	memset(ns, -1, sizeof ns);
	memset(mymap, '.', sizeof mymap);
	int x;
	// 存储二叉树
	cin >> x;
	ns[1] = x;
	while (cin >> x) {
   
		stn = 1;
		insert(x);
	}
	// 中序遍历并排序
	in_dfs(1);
	dfs(compute_h(ns[1]), 1, ns[1], 1);
	for (unsigned int i = 1; i <= cn.size(); ++i) {
   
		for (int j = max_w + 2; j >= 1; j --) {
   
			if ((mymap[i][j - 1] >= '0' && mymap[i][j - 1] <= '9') || mymap[i][j - 1] == '|') {
   
				mymap[i][j] = '\0';
				break;
			}
		}
		for (int j = 1; mymap[i][j]; ++j) {
   
			cout << mymap[i][j];
		}
		cout << endl;
	}
	return 0;
}

结束语

萌新，第一次在洛谷博客写一篇题解，有写得不好之处，请轻喷~~

更新

2023年12月4号

在上面说过了我这个方法不怎么对，用上面那种数组模拟二叉树存储在题目的限制范围会超出内存限制的，只适合像满二叉树那样，单枝树超过了8个节点就不行了，昨天因为是晚上知道这个问题后写完代码还能ac，就直接用这种简单的方法写完题解交了。今天马上就改进了，现在我们使用三个int类型数组来存储二叉树。

ns数组用来存储该下标节点的值，l数组用于存储下一个左节点的下标，r数组用于存储下一个右节点的下标。

修改如下:

初始化的修改

因为l[i]是存储i节点的左节点的下标，r[i]是存储的i节点的右节点的下标。所以我们可以递推实现预处理。

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

存储二叉搜索树的修改

stn 还是每次进行insert的时候初始化根节点为1，然后从根节点找x应该存储在哪个节点上并赋值。

void insert(int x) {
   
	while (ns[stn] != -1) {
   
		if (ns[stn] > x)
			stn = l[stn];
		else if (ns[stn] < x)
			stn = r[stn];
	}
	ns[stn] = x;
}

中序遍历和dfs的修改

设：start为一个节点的下标，那么这个点的左节点为l[start]，r[start]。

void in_dfs(int start) {
   
	if (ns[start] == -1)
		return;
	in_dfs(l[start]);
	cn.push_back(ns[start]);
	in_dfs(r[start]);
}

void dfs(int h, int w, int start, int d_idx) {
   
	if (ns[d_idx] == -1)
		return;
	max_w = max(max_w, w);
	string n = to_string(start);
	int l_idx = l[d_idx], r_idx = r[d_idx];
	int l_h = compute_h(ns[l_idx]), r_h = compute_h(ns[r_idx]);
	write(h, w, l_idx, r_idx, l_h, r_h, n);
	dfs(l_h, w + n.size() + 3, ns[l_idx], l_idx);
	dfs(r_h, w + n.size() + 3, ns[r_idx], r_idx);
}

最终完整ac代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1010;

int max_w = 0, stn, ns[N * 2 + 10], l[N], r[N];
vector<int> cn;
char mymap[N][N];

void insert(int x) {
   
	while (ns[stn] != -1) {
   
		if (ns[stn] > x)
			stn = l[stn];
		else if (ns[stn] < x)
			stn = r[stn];
	}
	ns[stn] = x;
}

void in_dfs(int start) {
   
	if (ns[start] == -1)
		return;
	in_dfs(l[start]);
	cn.push_back(ns[start]);
	in_dfs(r[start]);
}

int compute_h(int w) {
   
	vector<int>::iterator it = find(cn.begin(), cn.end(), w);
	int c = it - cn.begin();
	return cn.size() - c;
}

void write(int h, int w, int l_idx, int r_idx, int l_h, int r_h, string n) {
   
	int len = n.size();
	// 前面部分
	if (w - 2 >= 0)
		mymap[h][w - 2] = '|';
	mymap[h][w - 1] = '-';
	//中间数字部分
	for (int i = w; i < len + w; ++i) {
   
		mymap[h][i] = n[i - w];
	}
	// 后面部分
	if (ns[l_idx] != -1 || ns[r_idx] != -1) {
   
		mymap[h][len + w] = '-';
		mymap[h][w + len + 1] = '|';
	}
	// 补充'|'
	if (l_h - h > 1 && ns[l_idx] != -1) {
   
		for (int i = h; i < l_h; ++i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
	if (h - r_h > 1 && ns[r_idx] != -1) {
   
		for (int i = h; i > r_h; --i) {
   
			mymap[i][w + len + 1] = '|';
		}
	}
}


void dfs(int h, int w, int start, int d_idx) {
   
	if (ns[d_idx] == -1)
		return;
	max_w = max(max_w, w);
	string n = to_string(start);
	int l_idx = l[d_idx], r_idx = r[d_idx];
	int l_h = compute_h(ns[l_idx]), r_h = compute_h(ns[r_idx]);
	write(h, w, l_idx, r_idx, l_h, r_h, n);
	dfs(l_h, w + n.size() + 3, ns[l_idx], l_idx);
	dfs(r_h, w + n.size() + 3, ns[r_idx], r_idx);
}

void init() {
   
	// 初始化
	memset(ns, -1, sizeof ns);
	memset(mymap, '.', sizeof mymap);
	l[1] = 2;
	r[1] = 3;
	for (int i = 2; i < N; ++i)
	{
   
		l[i] = l[i - 1] + 2;
		r[i] = r[i - 1] + 2;
	}
}

int main() {
   
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	init();
	int x;
	// 存储二叉树
	cin >> x;
	ns[1] = x;
	while (cin >> x) {
   
		stn = 1;
		insert(x);
	}
	// 中序遍历并排序
	in_dfs(1);
	dfs(compute_h(ns[1]), 1, ns[1], 1);
	for (unsigned int i = 1; i <= cn.size(); ++i) {
   
		for (int j = max_w + 2; j >= 1; j --) {
   
			if ((mymap[i][j - 1] >= '0' && mymap[i][j - 1] <= '9') || mymap[i][j - 1] == '|') {
   
				mymap[i][j] = '\0';
				break;
			}
		}
		for (int j = 1; mymap[i][j]; ++j) {
   
			cout << mymap[i][j];
		}
		cout << endl;
	}
	return 0;
}
阅读全部

相关推荐

  1. 【算法】蓝桥杯2013国C 横向打印二叉树 题解

    2023-12-09 12:18:02       54 阅读

  3. 【洛谷 P8739】[蓝桥杯 2020 国 C] 重复字符串 题解（字符串+贪心算法）

    2023-12-09 12:18:02       37 阅读

  4. 【洛谷 P9421】[蓝桥杯 2023 国 B] 班级活动 题解（计数排序+贪心算法+数学）

    2023-12-09 12:18:02       40 阅读

  5. [蓝桥杯 2016 国 C] 赢球票

    2023-12-09 12:18:02       43 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-09 12:18:02       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-09 12:18:02       106 阅读

  9. 在Django里面运行非项目文件

    2023-12-09 12:18:02       87 阅读

  19. Python语言-面向对象

    2023-12-09 12:18:02       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2023-12-09 12:18:02       91 阅读

热门阅读

  1. 什么是HTTPS加密协议？HTTPS安全传输原理，SSL和TLS介绍，NGINX如何配置SSL证书

    2023-12-09 12:18:02       64 阅读

  4. Android 10-13,默认屏幕亮度80%或100%

    2023-12-09 12:18:02       50 阅读

  8. Jupyter Notebook不小心删除/剪切了单元格ctrl+z无法撤回怎么办

    2023-12-09 12:18:02       96 阅读

  10. 代客泊车手势召车功能设计规范

    2023-12-09 12:18:02       43 阅读

  14. postgresql12配置主从

    2023-12-09 12:18:02       45 阅读

  15. 【flutter压缩Uint8List图片大小】

    2023-12-09 12:18:02       63 阅读

  18. AIGC: 关于ChatGPT中实现一个聊天机器人

    2023-12-09 12:18:02       58 阅读

  19. 云贝教育 |【技术文章】PostgreSQL中误删除数据怎么办（一）

    2023-12-09 12:18:02       54 阅读

  23. .ros空间的清理

    2023-12-09 12:18:02       53 阅读

  24. centos7.9安装k8s v1.28.4

    2023-12-09 12:18:02       42 阅读

  25. ubuntu20.04设置开机自启动jar（依赖其他服务）

    2023-12-09 12:18:02       70 阅读

  26. SQL Server事务（Transaction）

    2023-12-09 12:18:02       55 阅读

  27. 【Docker】进阶之路：（十）Docker日志管理

    2023-12-09 12:18:02       42 阅读