題目鏈接

P8603 [藍(lán)橋杯 2013 國 C] 橫向打印二叉樹

題目描述

其原理很簡單：對于一個排序二叉樹添加新節(jié)點(diǎn)時，先與根節(jié)點(diǎn)比較，若小則交給左子樹繼續(xù)處理，否則交給右子樹。

當(dāng)遇到空子樹時，則把該節(jié)點(diǎn)放入那個位置。

比如，10 8 5 7 12 4 的輸入順序，應(yīng)該建成二叉樹如圖 $1$ 所示。

本題目要求：根據(jù)已知的數(shù)字，建立排序二叉樹，并在標(biāo)準(zhǔn)輸出中橫向打印該二叉樹。

輸入格式

輸入數(shù)據(jù)為一行空格分開的 $N$ 個整數(shù)。$N<100$，每個數(shù)字不超過 $10000$。

$N$ 并沒有在輸入中給出。

輸入數(shù)據(jù)中沒有重復(fù)的數(shù)字。

輸出格式

輸出該排序二叉樹的橫向表示,為了便于評卷程序比對空格的數(shù)目，請把空格用句點(diǎ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

思路

整體思路

我們使用數(shù)組的方法存儲二叉搜索樹，定義一個長度為1010的int類型數(shù)組ns和寬度,高度都為1010的char數(shù)組mymap，一個用于存二叉樹、一個用于打印二叉樹。

（其實(shí)按照題目給的數(shù)據(jù)范圍N<100，int數(shù)組長度不應(yīng)該取1010，應(yīng)該取是$2^{99}$次方，顯然也會超過內(nèi)存限制。但是我親測取1010也能過全部樣例，這里就怎么簡單怎么來吧）

我們用數(shù)組存儲二叉搜索樹，下標(biāo)$x$為根，$x?2$為左節(jié)點(diǎn)下標(biāo)，$x?2+1$為右節(jié)點(diǎn)下標(biāo)，按照輸入順序存儲。

在中序遍歷并存儲，因?yàn)槎嫠阉鳂涞闹行蚴桥判蛄说?#xff0c;所以直接中序遍歷輸出的數(shù)字存儲起來就行了，排序后方便后面計(jì)算高度。

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

上面為某個輸出樣例，我們觀察可以不難看出，從下往上看每個數(shù)字是升序的，所以某個數(shù)字的高度h為所有大于這個數(shù)字的個數(shù)+1，這樣就可以求出這個數(shù)在mymap數(shù)組的行號。列號也可以用dfs算法遍歷求出。

最后做完上面的步驟，直接用dfs遍歷一遍再處理一下輸出就行。

存儲二叉搜索樹

二叉樹的存儲根節(jié)點(diǎn)的下標(biāo)為1，左右節(jié)點(diǎn)下標(biāo)為2和3，依此類推，節(jié)點(diǎn)下標(biāo)為$x$，那么左節(jié)點(diǎn)下標(biāo)為$x?2$，右節(jié)點(diǎn)的下標(biāo)為$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（根節(jié)點(diǎn)下標(biāo)）

中序遍歷并存儲

這里沒什么好說的，直接中序排序后的數(shù)字壓入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);
}

計(jì)算目標(biāo)數(shù)的行號

因?yàn)榕藕眯蛭覀冎苯诱业侥繕?biāo)數(shù)所在的下標(biāo)。

$行號=數(shù)字個數(shù)?下標(biāo)$

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遍歷并寫入數(shù)組

h,w為該數(shù)字的行號和列號,max_w為整個輸出的最大列號定義為全局遍歷，每次迭代取最大值。start是當(dāng)前迭代的數(shù)字，d_idx為當(dāng)前數(shù)字在ns數(shù)組中的下標(biāo)

把當(dāng)前數(shù)字轉(zhuǎn)換為string類型，并計(jì)算長度n。l_idx為當(dāng)前數(shù)字的左節(jié)點(diǎn)，r_idx為當(dāng)前數(shù)字的右節(jié)點(diǎn)，l_h為當(dāng)前數(shù)字的左節(jié)點(diǎn)的高度，r_h為當(dāng)前數(shù)字的右節(jié)點(diǎn)的高度。

write函數(shù)為寫入，傳入一些重要參數(shù)

后面按順序進(jìn)行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] = '-';//中間數(shù)字部分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] = '|';}// 補(bǔ)充'|'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] = '|';}}
}

初始化和處理輸入輸出

初始化

結(jié)束dfs的方式判斷當(dāng)前數(shù)字為-1，先初始化ns數(shù)組全部為-1。

題目要求輸出的空格打印為’.‘,那么就初始化mymap數(shù)組全部為’.'。

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

處理輸入

這題沒有指定讀入多少個數(shù)字，所以在普通的編譯器上面就不知道如何結(jié)束讀入，好在OJ有一個特性我們正好可以利用。

我們簡單的介紹這個OJ的特性：讀入文本，讀到文本末尾，程序會自動停止的。

這里就先存一下根節(jié)點(diǎn)，再把后面的節(jié)點(diǎn)讀入進(jìn)去

// 存儲二叉樹
int x;
cin >> x;
ns[1] = x;
while (cin >> x) {stn = 1;insert(x);
}

處理輸出

顯然cn的長度為輸出的最大行號，max_w為最大寬度，我們遍歷一下這個二維字符數(shù)組就行了

for (unsigned int i = 1; i <= cn.size(); ++i) {// 這里max_w 要加上大于1的數(shù)，因?yàn)橐呀Y(jié)束字符存入max_w外面。// 反向遍歷，處理結(jié)束符for (int j = max_w + 2; j >= 1; j --) {if ((mymap[i][j - 1] >= '0' && mymap[i][j - 1] <= '9') || mymap[i][j - 1] == '|') {// 存入結(jié)束字符'\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] = '-';//中間數(shù)字部分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] = '|';}// 補(bǔ)充'|'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;
}

結(jié)束語

萌新，第一次在洛谷博客寫一篇題解，有寫得不好之處，請輕噴~~

更新

2023年12月4號

在上面說過了我這個方法不怎么對，用上面那種數(shù)組模擬二叉樹存儲在題目的限制范圍會超出內(nèi)存限制的，只適合像滿二叉樹那樣，單枝樹超過了8個節(jié)點(diǎn)就不行了，昨天因?yàn)槭峭砩现肋@個問題后寫完代碼還能ac，就直接用這種簡單的方法寫完題解交了。今天馬上就改進(jìn)了，現(xiàn)在我們使用三個int類型數(shù)組來存儲二叉樹。

ns數(shù)組用來存儲該下標(biāo)節(jié)點(diǎn)的值，l數(shù)組用于存儲下一個左節(jié)點(diǎn)的下標(biāo)，r數(shù)組用于存儲下一個右節(jié)點(diǎn)的下標(biāo)。

修改如下:

初始化的修改

因?yàn)閘[i]是存儲i節(jié)點(diǎn)的左節(jié)點(diǎn)的下標(biāo)，r[i]是存儲的i節(jié)點(diǎn)的右節(jié)點(diǎn)的下標(biāo)。所以我們可以遞推實(shí)現(xiàn)預(yù)處理。

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 還是每次進(jìn)行insert的時候初始化根節(jié)點(diǎn)為1，然后從根節(jié)點(diǎn)找x應(yīng)該存儲在哪個節(jié)點(diǎ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;
}

中序遍歷和dfs的修改

設(shè)：start為一個節(jié)點(diǎn)的下標(biāo)，那么這個點(diǎn)的左節(jié)點(diǎn)為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] = '-';//中間數(shù)字部分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] = '|';}// 補(bǔ)充'|'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;
}