1020 Tree Traversals

发表于

定义结构体变量时，关键字struct可以省略吗？
在C++中可以bai，但在duc中不行zhi。

1
2
3
4
5
6
7
8
9
10
11
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

struct LNode {
    ElemType data;
    struct LNode *next;
};
typedef struct LNode LNode；
typedef struct LNode* LinkList;
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50;

int n, post[maxn], in[maxn];

typedef struct LNode {
    int data;
    struct LNode* lc;
    struct LNode* rc;
}LNode, *Tree;

Tree creatTree(int postL, int postR, int inL, int inR) {
    if (postL > postR || inL > inR) return NULL;
    LNode* root = new LNode;
    root->data = post[postR];
    int indexRoot;
    for (indexRoot = inL; indexRoot <= inR; indexRoot++) {
        if (in[indexRoot] == post[postR])
            break;
    }
    int lengthOfLeftTree = indexRoot - inL;
    root->lc = creatTree(postL, postL + lengthOfLeftTree - 1, inL, indexRoot - 1);
    root->rc = creatTree(postL + lengthOfLeftTree, postR - 1, indexRoot + 1, inR);
    return root;
}

void BFS(Tree root) {
    int num = 0;
    queue<LNode*> q;
    q.push(root);
    while (!q.empty()) {
        LNode* now = q.front();
        q.pop();
        printf("%d", now->data);
        num++;
        if (num < n) printf(" ");
        if (now->lc != NULL) q.push(now->lc);
        if (now->rc != NULL) q.push(now->rc);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    // 后序
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    // 中序
    Tree root = creatTree(0, n - 1, 0, n - 1);
    BFS(root);

    return 0;
}


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

4 1 6 3 5 7 2
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
34
35
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
vector<int> post, in;
vector<node> ans;
void pre(int root, int start, int end, int index) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    ans.push_back({index, post[root]});
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n - 1, 0, n - 1, 0);
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i].value;
    }
    return 0;
}