Skip to content

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

题目

题目描述

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

Description

输入一棵左儿子右兄弟表示的树，输出它(按照正常表示的)前序、后序和层次遍历的结果。

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

样例说明：

2

/|\

1 3 4

/ \ \

5 6 7

   |

   8

Input Format

第一行，N<=12345，表示二叉树节点数。

接下来共N行，每行3个整数：X, Cx, Sx

表示X号节点的左儿子是Cx并且右兄弟是Sx。如果Cx=0表示它没有左儿子，类似地如果Sx=0表示没有右兄弟。

保证所有的X都在1到N中且没有重复

Output Format

第1行 输出N个整数，为这个树的前序遍历的结果，输出的数之间用空格隔开。

第2行 输出N个整数，为这个树的后序遍历的结果，输出的数之间用空格隔开。

第3行 输出N个整数，为这个树的层次遍历的结果，输出的数之间用空格隔开。

Hint

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;
    while(head < rear) {
        int tmp = q[head];
        ++ head;
        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;
}