Skip to content

11048: 【原1048】二叉树遍历

题目

题目描述

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

Description

给出一棵完美二叉树(所有叶子节点高度相同,所有非叶子节点都有两个子节点)的描述,输出按层次顺序遍历这棵二叉树的结果。

二叉树的每个节点都对应于一个正整数作为标记。对于一棵有\(n\)个节点的二叉树,其节点标记的取值范围为\(1\)至\(n\),且任意两个节点标记不相等。

Input Format

第\(1\)行:\(1\)个正整数\(n\),表示二叉树的节点个数为\(n\);

第\(2\)行至输入结束:每行有\(3\)个正整数a、b和c,设分别为节点A、B和C的标记,表示A的左儿子节点是B,右儿子节点是C。

Output Format

输出共\(n\)行,每行一个正整数,为遍历结果中相应次序的节点的标记。

Sample Input

7
3 2 1
1 7 6
2 4 5

Sample Output

3
2
1
4
5
7
6

Limits

对于30%的数据,3 <= n <= 127;对于100%的数据,3 <= n <= 1023。所有输入数据保证有效。

时间限制:1000ms,内存限制:30000kb。

Hint

先根据输入数据找到该二叉树的根,然后从根开始逐层遍历该二叉树。

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;
}