自动搬运

查看原文

来自洛谷，原作者为

	冷却心 111

搬运于2025-08-24 22:40:36，当前版本为作者最后更新于2022-11-14 22:19:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给定一个数组，依次插入进排序二叉树（这玩意不是叫二叉搜索树吗）中，然后 横向 打印这棵树。

解法

二叉搜索树的部分不再多说，题目里说的很清楚了，主要是输出格式。为了方便，本人把它存进一个字符数组 mp[1010][1010]，最后再输出。

样例 $1$ 输出:

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

观察样例 $1$，可发现这就是一个中序遍历，所以我处理时是用递归中序遍历的。

void output(LL p, LL space);

(虽然叫 output 但它不是输出，是处理怎样输出的。)

其中 p 是当前结点的编号，space 是要输出几个空格。

为了方便，可以将结点的值转换为字符串。

string trans(LL x){
	string res;
	while (x > 0)
		res = ((char)(x % 10 + '0')) + res, x /= 10;
	return res;
}

（很简单不说了。）

再观察，可发现每一层增加的空格都是由 这个数 和 两边的 -| 与 |- 组成，要特判一下 根节点 ，因为根节点开头没有字符。

所以 增加的空格数就是：

string num = trans(val);
LL Add = (p == 1 ? 0 : 2) + (LL)num.size() + 1;

（三元运算符的意思就是如果这个是编号 $1$ 的根节点，就不加上开头的 $2$ 个字符，否则加上。）

由于是中序遍历，所以结构这样：

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
...
void output(LL p, LL space){
	...
	output(ls(p), space + Add);
	....
	....
	output(rs(p), space + Add);
	....
	return ;
}

（(线段树好习惯)ls(x) 是 $x$ 的左儿子，rs(x) 同理，Add 就是刚才求出的增加空格数。）

在处理完左子树后，就该处理自己结点了。

先在全局定义一个变量 nowL，代表现在处理到第几行了。

再是一个局部变量 ind，代表 index，现在处理到这一行的第几个了，初始化为 $0$。

开始我们应先输出全部的空格。

for (LL i = 1; i <= space; i ++){
	if (mp[nowL][++ ind] != '|')
		mp[nowL][ind] = '.';
}

关于这个 if 有什么用，暂不讨论，看下面。

再次观察样例 $1$。

可发现除了根节点和叶子结点外，输出的就为 |- 加上 这个数（可以用刚才的字符串） 加上 -| 。

根节点就除去开头的 |-。

叶子结点就除去结尾的 -|。

如下：

// 根节点特判
if (p != 1){
	mp[nowL][++ ind] = '|'; mp[nowL][++ ind] = '-';
}

// 输出这个数字
for (LL i = 0; i < (LL)num.size(); i ++)
	mp[nowL][++ ind] = num[i];

// 叶子结点特判
if (tree[ls(p)] != -1 || tree[rs(p)] != -1)
	mp[nowL][++ ind] = '-', mp[nowL][++ ind] = '|';

为了输出方便，可在结尾加上一个标识符，代表这一行结束。

mp[nowL][++ ind] = '@';

然后处理左子树（根据前面的结构代码）。

这样算完成了 $80\%$。

最后是重头戏。

继续观察样例，可发现如果自身与子节点隔了几行，那么要在那几行加上几个 |，列的位置和自己这一行的最后那一个 | 是一样的。

这样就还要开一个数组 line[110] 表示当前结点所在的行数。

// 如果有左子树
if (tree[ls(p)] != -1){
	// L 为 左子树的 行位置
	LL L = line[ls(p)], now = line[p];
	for (LL i = L; i >= now; i --)
		mp[i][ind - 1] = '|';
}
// 如果有右子树
if (tree[rs(p)] != -1){
	// R 为 右子树的 行位置
	LL R = line[rs(p)], now = line[p];
	for (LL i = now; i >= R; i --)
		mp[i][ind - 1] = '|';
}	

这样在看刚才输出空格时的 if，就明白了它是什么意思了吧，它就是 防止后面的空格把前面的 | 覆盖。

这样整个代码就差不多完成了。

其余部分不讲了。

Code

#include<bits/stdc++.h>
#define LL long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define Fcin\
	ios :: sync_with_stdio(0);\
	cin.tie(0); cout.tie(0)
using namespace std;
const LL N = 110;
LL n, tree[N * 4], nowL = 0, line[N * 4];
char mp[N * 10][N * 10]; 

void insert(LL x, LL p){
	if (tree[p] == -1){
		tree[p] = x;
		return ;
	}
	if (x < tree[p])
		insert(x, ls(p));
	else
		insert(x, rs(p));
	return ;
}

string trans(LL x){
	string res;
	while (x > 0)
		res = ((char)(x % 10 + '0')) + res, x /= 10;
	return res;
}

void output(LL p, LL space){
	if (tree[p] == -1)
		return ;
	LL val = tree[p];
	
	string num = trans(val);
	LL Add = (p == 1 ? 0 : 2) + (LL)num.size() + 1;
	
	output(rs(p), space + Add);
	
	++ nowL;
	line[p] = nowL;
	LL ind = 0;
	
	for (LL i = 1; i <= space; i ++){
		if (mp[nowL][++ ind] != '|')
			mp[nowL][ind] = '.';
	}
	
	if (p != 1){
		mp[nowL][++ ind] = '|'; mp[nowL][++ ind] = '-';
	}
	
	for (LL i = 0; i < (LL)num.size(); i ++)
		mp[nowL][++ ind] = num[i];
		
	if (tree[ls(p)] != -1 || tree[rs(p)] != -1)
		mp[nowL][++ ind] = '-', mp[nowL][++ ind] = '|';
		
	mp[nowL][++ ind] = '@';
	output(ls(p), space + Add);
	
	if (tree[ls(p)] != -1){
		LL L = line[ls(p)], now = line[p];
		for (LL i = L; i >= now; i --)
			mp[i][ind - 1] = '|';
	}
	if (tree[rs(p)] != -1){
		LL R = line[rs(p)], now = line[p];
		for (LL i = now; i >= R; i --)
			mp[i][ind - 1] = '|';
	}	
	
	return ;
}

int main(){
	memset(tree, -1, sizeof(tree));
    Fcin;
    LL x;
    while (cin >> x){
    	++ n;
    	insert(x, 1);
	}
	
	output(1, 0);
	for (LL i = 1; i <= nowL; i ++){
		LL j = 1;
		while (mp[i][j] != '@'){
			cout << mp[i][j];
			++ j;
		}
		cout << "\n";
	}

	return 0;
}