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

题目链接

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

题目描述

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

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

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

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

输入格式

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

$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}$次方，显然也会超过内存限制。但是我亲测取1010也能过全部样例，这里就怎么简单怎么来吧）

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

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

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

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

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

存储二叉搜索树

二叉树的存储根节点的下标为1，左右节点下标为2和3，依此类推，结点下标为$x$，那么左节点下标为$x\ast 2$，右节点的下标为$x\ast 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;
}

结束语

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