当前位置： 首页 > article >正文

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

article 2024/11/14 3:55:58

文章目录

  • 题目链接
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例
      • 自己的样例输入
      • 自己的样例输出
    • 思路
      • 整体思路
        • 存储二叉搜索树
        • 中序遍历并存储
        • 计算目标数的行号
        • dfs遍历并写入数组
        • 初始化和处理输入输出
          • 初始化
          • 处理输入
          • 处理输出
      • 完整的代码如下
    • 结束语

题目链接

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() {
	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;
}

结束语

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


http://www.kler.cn/a/156064.html

相关文章：

  • C++初阶——list
  • AI时代的研发生产关系，是否有新的可能？
  • 蓝牙BLE开发——iOS 每次写入数据超过200字节报错？
  • 解决：WSL2可视化opencv和pyqt冲突：QObject::moveToThread
  • 【Qt】Macbook M1下载安装
  • Java基础-组件及事件处理（下）
  • 【Java 基础】15 注解
  • 汇编学习记录
  • 常用数据预处理方法 python
  • 前缀和列题AcWing795
  • 本地缓存和分布式缓存
  • 冗余链路和生成树协议
  • 【Java 基础】18 I/O流
  • Spring Boot 集成 spring security 01
  • 【网络安全】下载并安装 kali 的虚拟机 版本
  • 总结1073
  • 【LangChain实战】开源模型学习（1）-ChatGLM2-6B
  • 【扫雷】C语言实现扫雷小游戏
  • Java面试题（每天10题）-------连载（41）
  • 后端返回图片流前端展示图片
  • git stash save untracked not staged
  • TCP 基本认识
  • [WP] ISCTF2023 Web 部分题解
  • Amazon CodeWhisperer 使用体验
  • 6-55.汽车类的继承
  • Cmkae外部依赖管理