# 11042: 【原1042】左儿子右兄弟

### 题目描述

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

## Description

[左儿子右兄弟表示法是一种精神，务必领会]

2

/|\

1 3 4

/ \ \

5 6 7

``````   |

8
``````

## Sample Input

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

## Sample Output

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

## FineArtz's solution

``````/* 左儿子右兄弟 */
#include <iostream>
using namespace std;

class Node{
public:
int child = 0, brother = 0;
};

Node a[12350];
bool v[12350] = {0};

void dlr(int x){
cout << x << ' ';
int i = a[x].child;
while (i != 0){
dlr(i);
i = a[i].brother;
}
}

void lrd(int x){
int i = a[x].child;
while (i != 0){
lrd(i);
i = a[i].brother;
}
cout << x << ' ';
}

void hie(int x){
int q[12350], front = 0, rear = 0;
q[rear++] = x;
while (front != rear){
int now = q[front++];
cout << now << ' ';
int i = a[now].child;
while (i != 0){
q[rear++] = i;
i = a[i].brother;
}
}
}

int main(){
int n;
cin >> n;
for (int i = 1; i <= n; ++i){
int x, cx, sx;
cin >> x >> cx >> sx;
a[x].child = cx;
a[x].brother = sx;
v[cx] = true;
v[sx] = true;
}
int root = 0;
for (int i = 1; i <= n; ++i){
if (!v[i]){
root = i;
break;
}
}
dlr(root);
cout << endl;
lrd(root);
cout << endl;
hie(root);
cout << endl;
return 0;
}
``````

## q4x3's solution

``````/**
* 儿子兄弟表示法下的前后层序遍历
**/
#include <iostream>
#include <stdio.h>
using namespace std;

int N, ls[13000], rb[13000];
bool vis[13000];

void pre(int rt) {
printf("%d ", rt);
int son = ls[rt];
while(son) {
pre(son);
son = rb[son];
}
}

void pos(int rt) {
int son = ls[rt];
while(son) {
pos(son);
son = rb[son];
}
printf("%d ", rt);
}

void hie(int rt) {
int q[13000];
int head = 0, rear = 0;
q[rear] = rt; ++ rear;
printf("%d ", tmp);
tmp = ls[tmp];
while(1) {
if(tmp) {
q[rear] = tmp;
++ rear;
tmp = rb[tmp];
} else {
break;
}
}
}
}

int main() {
scanf("%d", &N);
int rt;
for(int i = 0;i < N;++ i) {
int tmp1, tmp2, tmp3;
scanf("%d%d%d", &tmp1, &tmp2, &tmp3);
ls[tmp1] = tmp2;
rb[tmp1] = tmp3;
vis[tmp2] = 1;
vis[tmp3] = 1;
}
for(int i = 1;i <= N;++ i) {
if(! vis[i]) {
rt = i;
break;
}
}
pre(rt);
printf("\n");
pos(rt);
printf("\n");
hie(rt);
printf("\n");
}
``````

## victrid's solution

``````#include <cstdio>
#include <iostream>
using namespace std;
int N;
struct node {
int son     = 0;
int brat    = 0;
bool isroot = true;
};
node treestr[12350];
int construct_tree() {
int P = N, a, b, c;
while (P--) {
scanf("%d%d%d", &a, &b, &c);
if (b != 0) {
treestr[a].son    = b;
treestr[b].isroot = false;
}
if (c != 0) {
treestr[a].brat   = c;
treestr[a].isroot = false;
treestr[c].isroot = false;
}
}
for (int i = 1; i <= N; i++) {
if (treestr[i].isroot)
return i;
}
return 0;
}
void pretrav(int root) {
printf("%d ", root);
if (treestr[root].son != 0) {
pretrav(treestr[root].son);
}
if (treestr[root].brat != 0) {
pretrav(treestr[root].brat);
}
return;
}
void postrav(int root) {
if (treestr[root].son != 0) {
postrav(treestr[root].son);
}
printf("%d ", root);
if (treestr[root].brat != 0) {
postrav(treestr[root].brat);
}
return;
}
int queuet[12350] = {};
int* queueex;
int* queueend;
void clearqueue() {
queueex  = queuet;
queueend = queuet + 1;
}
void enqueue(int tptr) {
*queueend = tptr;
queueend++;
}
int dequeue() {
if (queueex + 1 == queueend)
return 0;
else
queueex++;
return *queueex;
}
bool empty() {
return (queueex + 1 == queueend);
}
void lvltrav(int root) {
clearqueue();
enqueue(root);
while (!empty()) {
int a = dequeue();
while (a) {
printf("%d ", a);
if (treestr[a].son)
enqueue(treestr[a].son);
a = treestr[a].brat;
}
}
return;
}
int main() {
scanf("%d", &N);
int root = construct_tree();
pretrav(root);
putchar('\n');
postrav(root);
putchar('\n');
lvltrav(root);
putchar('\n');
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 12350;
struct node {
int lson = 0, rbro = 0;
};
node a[MAX_N];

void preorder(int t) {

cout << t << " ";
if (a[t].lson) preorder(a[t].lson);
if (a[t].rbro) preorder(a[t].rbro);
}

void postorder(int t) {

if (a[t].lson) postorder(a[t].lson);
cout << t << " ";
if (a[t].rbro) postorder(a[t].rbro);
}

void level(queue<int> t) {

queue<int> next;
while (!next.empty()) next.pop();
while (!t.empty()) {
int temp = t.front();
t.pop(); cout << temp << " ";
if (a[temp].lson) {
next.push(a[temp].lson);
int temp2 = a[a[temp].lson].rbro;
while (temp2) {
next.push(temp2);
temp2 = a[temp2].rbro;
}
}
}
if (!next.empty()) level(next);
}

int main() {

ios::sync_with_stdio(false);
int n; cin >> n;
int pre[MAX_N]; memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; ++i) {
int temp, lson, rbro;
cin >> temp >> lson >> rbro;
a[temp].lson = lson;
a[temp].rbro = rbro;
pre[lson] = temp;
if (rbro) {
pre[rbro] = pre[temp] = -1;
}
}
int root;
for (root = 1; root <= n; ++root) if (pre[root] == 0) break;

preorder(root);
cout << endl;
postorder(root);
cout << endl;
queue<int> p; p.push(root);
level(p);
cout << endl;
return 0;
}
``````