品牌网站建设的意义,黑龙江省建设厅官网,网站空间流量查询,全国企业信息公示系统查询文章目录 题目链接题目描述输入格式输出格式样例自己的样例输入自己的样例输出 思路整体思路存储二叉搜索树中序遍历并存储计算目标数的行号dfs遍历并写入数组初始化和处理输入输出初始化处理输入处理输出 完整的代码如下 结束语更新初始化的修改存储二叉搜索树的修改中序遍历和… 文章目录 题目链接题目描述输入格式输出格式样例自己的样例输入自己的样例输出 思路整体思路存储二叉搜索树中序遍历并存储计算目标数的行号dfs遍历并写入数组初始化和处理输入输出初始化处理输入处理输出 完整的代码如下 结束语更新初始化的修改存储二叉搜索树的修改中序遍历和dfs的修改最终完整ac代码 题目链接
P8603 [蓝桥杯 2013 国 C] 横向打印二叉树
题目描述
其原理很简单对于一个排序二叉树添加新节点时先与根节点比较若小则交给左子树继续处理否则交给右子树。
当遇到空子树时则把该节点放入那个位置。
比如10 8 5 7 12 4 的输入顺序应该建成二叉树如图 1 1 1 所示。
本题目要求根据已知的数字建立排序二叉树并在标准输出中横向打印该二叉树。
输入格式
输入数据为一行空格分开的 N N N 个整数。 N 100 N100 N100每个数字不超过 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一个用于存二叉树、一个用于打印二叉树。
其实按照题目给的数据范围N100int数组长度不应该取1010应该取是 2 99 2^{99} 299次方显然也会超过内存限制。但是我亲测取1010也能过全部样例这里就怎么简单怎么来吧
我们用数组存储二叉搜索树下标 x x x为根 x ∗ 2 x*2 x∗2为左节点下标 x ∗ 2 1 x*21 x∗21为右节点下标按照输入顺序存储。
在中序遍历并存储因为二叉搜索树的中序是排序了的所以直接中序遍历输出的数字存储起来就行了排序后方便后面计算高度。
...|-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*21 x∗21。
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就行了
vectorint 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);
}计算目标数的行号
因为排好序我们直接找到目标数所在的下标。 行号 数字个数 − 下标 行号数字个数-下标 行号数字个数−下标
vectorint cn;
int compute_h(int w) {vectorint::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] |) {// 存入结束字符\0mymap[i][j] \0;break;}}// 正向遍历输出答案for (int j 1; mymap[i][j]; j) {cout mymap[i][j];}cout endl;
}完整的代码如下
#include bits/stdc.h
#define endl \nusing namespace std;const int N 1010;int max_w 0, stn, ns[N];
vectorint 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) {vectorint::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 \nusing namespace std;const int N 1010;int max_w 0, stn, ns[N * 2 10], l[N], r[N];
vectorint 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) {vectorint::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;
}
