Tree

构建二叉树 / Tree

问题描述

树的表示方法很多,可以采用自然界的树形表示法,也可以采用括号表示法:先将根结点放入一对圆括号中,然后把它的子树按由左往右的顺序放入括号中,而对子树也采用同样的方法处理。同层子树与它的根结点用圆括号扩起来,同层子树之间用逗号格开,最后用闭括号括起来。如图所示的树可以表示成:(1(2(4,5),3))。由完全二叉树的定义我们可知,如果知道该完全二叉树的结点个数,则可以构建出一棵确定的完全二叉树,现在输入完全二叉树的结点数 N(N≤214),用括号表示法输出这棵树。(默认树的结点名称为树结点的编号。)

输入格式

N 完全二叉树的结点个数。

输出格式

N 个结点的完全二叉树的括号表示。

样例数据

tree.in tree.out
5 (1(2(4,5),3))

我的渣题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cmath>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n;

void dfs(int id) {
if (id > n) return;
printf("%d", id);
if (id * 2 <= n || id * 2 + 1 <= n) {
printf("(");
if (id * 2 <= n) dfs(id * 2);
if (id * 2 <= n && id * 2 + 1 <= n) printf(",");
if (id * 2 + 1 <= n) dfs(id * 2 + 1);
printf(")");
}
}

int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d", &n);
printf("(");
dfs(1);
printf(")");
return 0;
}