Whimsical journey: my original blog is completely knocked by hand, absolutely not carried, and there can be no repetition in the whole network; I don't have a team, I only share it for technology lovers, and all the content doesn't involve advertising. All my articles are only published in CSDN and personal blog (must be the domain name of fantasy journey). In addition, they are all stolen articles!
Luogu P1185 drawing binary tree
Title Description
Binary tree is a basic data structure. It is either empty or composed of root node, left subtree and right subtree. At the same time, the left subtree and right subtree are also binary trees respectively.
When the height of a binary tree is m − 1 m-1 When m − 1, there are m m m floor. except m m Outside layer m, the number of nodes in other layers reaches the maximum, and the nodes are in the second layer m m m layer, this is a full binary tree.
Now, you need to use the program to draw a binary tree, which is formed by removing several nodes from a full binary tree. For a full binary tree, we need to draw it according to the following requirements:
1. The node is represented by the lowercase letter "o". For a parent node, use "/" to connect the left subtree and "\" to connect the right subtree.
2. Definition [ i , j ] [i,j] [i,j] is located at i i Line i j j A character in column j. if [ i , j ] [i,j] If [i,j] is "/", then [ i − 1 , j + 1 ] [i-1,j+1] [i − 1,j+1] and [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j − 1] is either "o" or "/. if [ i , j ] [i,j] [i,j] is "\", then [ i − 1 , j − 1 ] [i-1,j-1] [i − 1,j − 1] and [ i + 1 , j + 1 ] [i+1,j+1] [i+1,j+1] is either "o" or "\". Similarly, if [ i , j ] [i,j] [i,j] is the second 1 − m 1-m A node of 1 − m layer (i.e. "o"), then [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j − 1] is "/, [ i + 1 , j + 1 ] [i+1,j+1] [i+1,j+1] is "\".
3. For section m m The m-layer node is the leaf node. If two belong to the same father, there is no difference between them from 3 By 3 It is separated by three spaces. If two nodes are adjacent but do not belong to the same father, they are separated by 1 1 1 space apart. The first m m The left number of floor m 1 1 There is no space before 1 node.
Finally, it needs to be deleted from a drawn full binary tree n n n nodes (including its left and right subtrees and the connection with the father), and the original characters are replaced with spaces (ASCII 32, please pay attention to the difference between spaces and ASCII 0 (if you open it with Notepad, it looks the same, but it will be counted as a wrong answer during evaluation!).
Input format
The first 1 1 Line 1 contains 2 2 2 positive integers m m m and n n n. The number of binary tree layers to be drawn has been changed from m m The number of nodes deleted in the m-level full binary tree.
next n n n lines, two positive integers per line, representing the second line i i Layer i j j j nodes need to be deleted( 1 < i ≤ M , j ≤ 2 i − 1 1<i≤M,j≤2^{i-1} 1<i≤M,j≤2i−1).
Output format
Binary tree drawn according to the requirements of the topic.
Sample input and output
In 1:
2 0
Out 1:
o / \ o o
In 2:
4 0
Out 2:
o
/ \
/ \
/ \
/ \
/ \
o o
/ \ / \
/ \ / \
o o o o
/ \ / \ / \ / \
o o o o o o o o
In 3:
4 3 3 2 4 1 3 4
Out 3:
o
/ \
/ \
/ \
/ \
/ \
o o
/ /
/ /
o o
\ / \
o o o
Data range
30 % 30\% 30% of the data meet: n = 0 n=0 n=0；
50 % 50\% 50% of the data meet: 2 ≤ m ≤ 5 2≤m≤5 2≤m≤5；
100 % 100\% 100% of data meets: 2 ≤ m ≤ 10 , 0 ≤ n ≤ 10 2≤m≤10,0≤n≤10 2≤m≤10,0≤n≤10.
Problem solution
I like this question. Why—— You don't need so many algebraic proofs!
I use complex recursive control to complete.
In order to facilitate the writing of the problem solution, we define the branch layer as a horizontal line composed of three characters' / '' \ \ ', and the leaf layer as a horizontal line composed of two characters' o'
From the general perspective, the analysis can be divided into the following steps:
- Find the position of the root node and extend two subtrees to the left and right (two recursions), with marks extending to the left and right respectively
- For the recursive function, judge whether the current recursive layer is a branch layer or a leaf layer. If it is a branch layer, add branch characters and continue to extend in the same direction, and repeat the second step for the leaf layer 1 1 Step 1
- During recursion, another parameter is added to mark the current node. Whenever reaching the leaf layer, check whether the current node needs to be deleted. If it needs to be deleted, mark the current position as a space, then "climb back" along the extension direction of the branch, and successively change the just made branch character mark to a space until it encounters the 'o' character, The branch representing the node to be deleted is deleted (if not deleted, recursion will be executed normally)
- Boundary judgment
However, there are still several data that we need to deduce: when the number of layers is m m m, the effective part of the whole two-dimensional array, that is, the width of the visible part after output x x x and height y y y. And the number of branch layers between each two leaf layers l t i m e s [ i ] ltimes[i] ltimes[i] (indicates the penultimate i i Layer i and penultimate i + 1 i+1 i+1 layer (number of branch layers between two leaf layers).
For width x x x and height y y y. Let's look for rules from the list:
| Number of layers m m m | width x x x | height y y y |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 5 | 3 |
| 3 | 11 | 6 |
| 4 | 23 | 12 |
| 5 | 47 | 24 |
At a glance, it seems to be regular, but it can't be expressed. It doesn't matter. Let's simplify it: the number of layers is 1 1 1 is deleted (special judgment in the code is enough). Please observe again. Is it not difficult to find the law~
The summary is as follows:
- When m = 1 m = 1 When m=1, x = y = 1 x=y=1 x=y=1
- When m > 1 m > 1 m> At 1:00, x = 6 × 2 m − 2 − 1 , y = 3 × 2 m − 2 x = 6 \times2^{m-2} - 1, y = 3 \times 2^{m-2} x=6×2m−2−1,y=3×2m−2
Look again l t i m e s [ i ] ltimes[i] Value of ltimes[i]:
| position | Branch layer width |
|---|---|
| Penultimate 1 1 1 and penultimate 2 2 Between two floors | 1 |
| Penultimate 2 2 2 and penultimate 3 3 Between 3 floors | 2 |
| Penultimate 3 3 3 and penultimate 4 4 Between 4 floors | 5 |
| Penultimate 4 4 4 and penultimate 5 5 Between the 5th floor | 11 |
Can't find the law again? I won't tell you that the first set of data needs to be specially judged here
therefore l t i m e s [ i ] ltimes[i] The law of ltimes[i] is: when i = 1 i=1 When i=1, l t i m e s [ i ] = 1 ltimes[i]=1 ltimes[i]=1 ； When i > 1 i>1 i> At 1:00, l t i m e s [ i ] = 3 × 2 i − 2 − 1 ltimes[i]=3\times2^{i-2}-1 ltimes[i]=3×2i−2−1
OK, code! This is mainly the simulation of the code, so I wrote detailed comments for reference!
#include <bits/stdc++.h>
using namespace std;
int m, n, x, y; // Number of layers, number of nodes to be deleted, required map width and required map height
char mp[5000][10000]; // Store the final printed map
int ltimes[100] = {0, 0, 1, 2, 5};
bool locker[100][100]; // Mark the node to be deleted, and locker[i][j]=true indicates that the j-th node of layer I is to be deleted
void dfs(int p, int q, int level, int times, bool left, int num) {
/*
p, q: Coordinates of the current node
level: The number of leaf layers where the current node is located (if it is a branch layer, take the value of the leaf layer closest to the top) is used to determine the number of branch layers required
times: The number of recursive layers whose level value has not changed so far is used to mark whether the current required number of branch layers has been drawn
left: Mark the extension direction of the branch layer. A value of true represents the left
num: The number of the current node in the current layer (indicating the number of the first node, used to confirm whether to delete; meaningful only when in the leaf layer)
*/
// Judge whether to reach the leaf layer according to the times
if (times == 0) {
// Is the leaf layer, which is marked accordingly
mp[p][q] = 'o';
// Judge whether the current node needs to be deleted
if (locker[level][num]) {
// Delete node
mp[p][q] = ' ';
// Judge the extension direction of the branch in front of the node, and return to the original path to delete the branch until it reaches the previous leaf layer
if (left) {
for (int i = p - 1, j = q + 1; mp[i][j] != 'o'; i--, j++) {
mp[i][j] = ' ';
}
} else {
for (int i = p - 1, j = q - 1; mp[i][j] != 'o'; i--, j--) {
mp[i][j] = ' ';
}
}
// Stop the recursion of the subtree after deletion
return;
}
// If you have reached the lowest leaf layer, stop recursion
if (level == m) return;
// If the current node does not need to be deleted and is not the lowest leaf layer, continue recursion and divide it into left and right subtrees for processing respectively
// For the number of the current node in the current layer, multiply 2 minus 1 to get the number of its left child in the layer of the left child, and multiply 2 to get the number of its right child in the layer of the right child
dfs(p + 1, q - 1, level, times + 1, true, num * 2 - 1);
dfs(p + 1, q + 1, level, times + 1, false, num * 2);
} else {
// It is a branch layer and marked accordingly
mp[p][q] = left ? '/' : '\\';
// Judge whether it is the last layer of the current group of branch layers
if (times == ltimes[m + 1 - level]) {
// Yes, then the next level+1, times=0
if (left)
dfs(p + 1, q - 1, level + 1, 0, true, num);
else
dfs(p + 1, q + 1, level + 1, 0, false, num);
} else {
// No, normal recursion. Except for coordinates, only times needs to be processed
if (left)
dfs(p + 1, q - 1, level, times + 1, true, num);
else
dfs(p + 1, q + 1, level, times + 1, false, num);
}
}
}
int main() {
memset(mp, ' ', sizeof(mp)); // The initial value of the map is'
for (int i = 3; i < 100; i++) {
ltimes[i] = 3 * pow(2, i - 3) - 1; // Initializes the number of branch layers between leaf layers
}
// Input the data and determine the size of the map (find the law, and the specific formula is described above)
cin >> m >> n;
if (m == 1) {
x = 1;
y = 1;
} else {
x = 6 * pow(2, m - 2) - 1;
y = 3 * pow(2, m - 2);
}
// According to the input data, determine the node to be deleted and record it in the locker
int t1, t2;
for (int i = 0; i < n; i++) {
cin >> t1 >> t2;
locker[t1][t2] = true;
}
// Determine the location of the root node according to the map size, and call the dfs function to draw the map
// It is easy to know that the root node is in row 1 and the number of columns is x/2+1 (because it is on the symmetry axis in the middle of the first row, X is always odd)
dfs(1, x / 2 + 1, 1, 0, 0, 1);
// When printing a map, because x represents the width, that is, the number of columns, the outer layer is y and the inner layer is x
for (int i = 1; i <= y; i++) {
for (int j = 1; j <= x; j++) {
cout << mp[i][j];
}
cout << endl;
}
return 0;
}