# 11048: 【原1048】二叉树遍历

### 题目描述

author: xjia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1048

## Sample Input

``````7
3 2 1
1 7 6
2 4 5
``````

## Sample Output

``````3
2
1
4
5
7
6
``````

## FineArtz's solution

``````/* 二叉树遍历 */
#include <iostream>
using namespace std;

class Node{
public:
int l = 0, r = 0;
};

Node a[1025];
bool b[1025] = {0};

void hie(int root){
int q[1025] = {0}, front = 0, rear = 0;
q[rear++] = root;
while (front != rear){
int now = q[front++];
cout << now << endl;
if (a[now].l != 0){
q[rear++] = a[now].l;
}
if (a[now].r != 0){
q[rear++] = a[now].r;
}
}
}

int main(){
int n;
cin >> n;
n >>= 1;
for (int i = 1; i <= n; ++i){
int x, y, z;
cin >> x >> y >> z;
a[x].l = y;
a[x].r = z;
b[y] = true;
b[z] = true;
}
int root = 0;
for (int i = 1; i <= n * 2 + 1; ++i){
if (!b[i]){
root = i;
break;
}
}
hie(root);
return 0;
}
``````

## ligongzzz's solution

``````#include <iostream>
#include <queue>
#include <vector>
using namespace std;

using pii = pair<int, int>;

vector<pii> tdata;

void bfs(int root) {
queue<int> qdata;
qdata.push(root);

while (!qdata.empty()) {
auto temp = qdata.front();
qdata.pop();

cout << temp << "\n";

if (tdata[temp].first) {
qdata.push(tdata[temp].first);
qdata.push(tdata[temp].second);
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

tdata.resize(n + 1, pii(0, 0));
vector<bool> isroot(n + 1, true);

int a, b, c;
while (cin >> a) {
cin >> b >> c;

tdata[a].first = b;
tdata[a].second = c;

isroot[b] = isroot[c] = false;
}

int root = 0;

for (int i = 1; i <= n; ++i) {
if (isroot[i]) {
root = i;
break;
}
}

bfs(root);

return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
struct treedata{
int l, r, pre;
} tree[1024];
int n, i, node, lt, rt, father, maxlevel;
int le[1024][1000];
void cengci(int node,int level){
if (level > maxlevel) maxlevel = level;
le[level][++le[level][0]] = node;
if (tree[node].l) cengci(tree[node].l, level + 1);
if (tree[node].r) cengci(tree[node].r, level + 1);
}
int main(){
scanf("%d", &n);
while (scanf("%d%d%d", &node, &lt, &rt) != EOF){
tree[node].l = lt;
tree[node].r = rt;
tree[rt].pre = node;
tree[lt].pre = node;
}
for (i = 1; i <= n; i++)
if (!tree[i].pre){
father = i;
break;
}
cengci(father,1);
for (i = 1; i <= maxlevel; i++){
for (int j = 1; j <= 1000; j++)
if (le[i][j]) cout<<le[i][j]<<endl;
else break;
}
return 0;
}
``````