【数据结构】树和二叉树

防止复制粘贴，代码还是结束之后补上。

这次稍微变难了点，但是主要问题还是函数题你想调试就只能直接提交，然后盲调；或者补出来他隐藏的函数本地调，运行测试这个功能跟没有一样。

函数题#

二叉搜索树中的最近公共祖先#

我勒个 LCA 不记录父亲，给我整不会了😇，那我只能暴搜了，如果两个点都在一个子树里，就递归往那个子树搜，直到第一次不在同一边，这次的点就是 LCA。

本来 LCA 可以树上倍增，预处理 $O(n \log n)$ ，单次查询 $O(\log n)$ ，然后这题强制单次查询最劣可能达到 $O(n^2)$ ，不理解。

1
int find(Tree T, int val) {
2
    if (!T) return 0;
3
    else if (T->Key == val) return 1;
4
    else return find(T->Left, val) | find(T->Right, val);
5
}
6

7
int LCA( Tree T, int u, int v ) {
8
    if (!T) return ERROR;
9
    // printf(" %d", T->Key);
10
    if (find(T->Left, u) && find(T->Left, v)) return LCA(T->Left, u, v);
11
    else if (find(T->Right, u) && find(T->Right, v)) return LCA(T->Right, u, v);
12
    else if (find(T, u) && find(T, v)) return T->Key;
13
    else return ERROR;
14
}

先序输出叶结点#

直接 dfs 即可。

1
void PreorderPrintLeaves( BinTree BT ) {
2
    if (!BT) return;
3
    if (!BT->Left && !BT->Right) printf(" %c", BT->Data);
4
    else {
5
        PreorderPrintLeaves(BT->Left);
6
        PreorderPrintLeaves(BT->Right);
7
    }
8
}

求二叉树高度#

dfs 回溯的时候统计高度，当前结点的高度 = max{左子树高度，右子树高度} + 1。这种回溯时更新状态的做法有个更专业的名字，叫树形dp，是动态规划的一个分支。

1
int max(int a, int b) {
2
    return a > b ? a : b;
3
}
4

5
int GetHeight( BinTree BT ) {
6
    if (!BT) return 0;
7
    else return max(GetHeight(BT->Left) + 1, GetHeight(BT->Right) + 1);
8
}

二叉树的遍历#

按要求模拟即可。

1
void InorderTraversal( BinTree BT ) {
2
    if (!BT) return;
3
    InorderTraversal(BT->Left);
4
    printf(" %c", BT->Data);
5
    InorderTraversal(BT->Right);
6
}
7

8
void PreorderTraversal( BinTree BT ) {
9
    if (!BT) return;
10
    printf(" %c", BT->Data);
11
    PreorderTraversal(BT->Left);
12
    PreorderTraversal(BT->Right);
13
}
14

15
void PostorderTraversal( BinTree BT ) {
16
    if (!BT) return;
17
    PostorderTraversal(BT->Left);
18
    PostorderTraversal(BT->Right);
19
    printf(" %c", BT->Data);
20
}
21

22
typedef struct _node {
23
    struct TNode *val;
24
    struct _node *ne;
25
} Node;
26
Node *h, *t;
27

28
int empty() {
29
    return h == NULL;
30
}
31

32
void push(BinTree val) {
33
    Node *p = (Node *)malloc(sizeof(Node));
34
    p->val = val, p->ne = NULL;
35
    if (empty()) h = t = p;
36
    else t->ne = p, t = p;
37
}
38

39
BinTree pop() {
40
    Node *p = h;
41
    h = h->ne;
42
    if (!h) t = NULL;
43
    return p->val;
44
}
45

46
void LevelorderTraversal( BinTree BT ) {
47
    if (!BT) return;
48
    push(BT);
49
    while (!empty()) {
50
        BinTree x = pop();
51
        printf(" %c", x->Data);
52
        if (x->Left) push(x->Left);
53
        if (x->Right) push(x->Right);
54
    }
55
}

编程题#

这几个题都不是很容易，感觉加点数据量可以去 xcpc 当签到题了。

哈夫曼编码#

做一遍哈夫曼算法，求出来最优树的权值。然后只需要检查是不是前缀码以及权值是否和这个最优的相等。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
const int N = 64;
7
int f[128];
8
string s[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n, m;
14
    cin >> n;
15
    priority_queue<int, vector<int>, greater<int>> q;
16
    for (int i = 1; i <= n; ++i) {
17
        char c;
18
        int t;
19
        cin >> c >> t;
20
        f[c] = t;
21
        q.emplace(t);
22
    }
23
    int w = 0;
24
    while (q.size() != 1) {
25
        int a = q.top();
26
        q.pop();
27
        int b = q.top();
28
        q.pop();
29
        q.emplace(a + b);
30
        w += a + b;
31
    }
32
    cin >> m;
33
    while (m--) {
34
        int tw = 0;
35
        for (int i = 1; i <= n; ++i) {
36
            char c;
37
            cin >> c >> s[i];
38
            tw += s[i].length() * f[c];
39
        }
40
        bool flag = true;
41
        for (int i = 1; i <= n; ++i) {
42
            for (int j = 1; j <= n; ++j) {
43
                if (i == j) continue;
44
                if (s[j].length() <= s[i].length() && s[j] == s[i].substr(0, s[j].length())) {
45
                    flag = false;
46
                    break;
47
                }
48
            }
49
            if (!flag) break;
50
        }
51
        if (tw != w || !flag) cout << "No" << endl;
52
        else cout << "Yes" << endl;
53
    }
54
    return 0;
55
}

是否完全二叉搜索树#

先把树构建出来，然后我的判断逻辑是这样的，bfs 入队的时候允许非空的结点的空的儿子入队，出队的时候如果出现空结点 …… 空，这种情况相当于前面缺结点了，就判定为不是。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
struct Node {
7
    int val;
8
    Node *ls, *rs;
9
};
10

11
Node *insert(Node *u, int val) {
12
    if (!u) {
13
        u = new Node;
14
        u->val = val;
15
        u->ls = u->rs = nullptr;
16
        return u;
17
    }
18
    else if (val > u->val) u->ls = insert(u->ls, val);
19
    else u->rs = insert(u->rs, val);
20
    return u;
21
}
22

23
int main() {
24
    ios::sync_with_stdio(0);
25
    cin.tie(0), cout.tie(0);
26
    int n;
27
    cin >> n;
28
    Node *tr = nullptr;
29
    for (int i = 1; i <= n; ++i) {
30
        int val;
31
        cin >> val;
32
        tr = insert(tr, val);
33
    }
34
    queue<Node*> q;
35
    q.emplace(tr);
36
    bool first = true;
37
    int flag = 0;
38
    while (!q.empty()) {
39
        Node *x = q.front();
40
        q.pop();
41
        if (x == nullptr) {
42
            if (flag == 0) flag = 1;
43
        }
44
        else {
45
            if (flag == 1) flag = 2;
46
            if (first) first = false;
47
            else cout << ' ';
48
            cout << x->val;
49
            q.emplace(x->ls);
50
            q.emplace(x->rs);
51
        }
52
    }
53
    cout << endl;
54
    cout << (flag != 2 ? "YES" : "NO") << endl;
55
    return 0;
56
}

完全二叉树的层序遍历#

这道题关键应该在于一个小性质，对于一个完全二叉树，子树一定都是完全二叉树；一个结点的两个子树中一定至少有一棵满的（假设左子树一共有 n 层，考虑两棵子树排在最后一层，如果不够 2ⁿ，那右子树是满的，如果超过了，那么左子树是满的），左子树一定不比右子树小，而且两棵子树的大小一定相差不超过 2ⁿ。因此对于一个序列，先取最右边的为根，然后枚举哪棵子树是满的，满的那棵子树的大小，有且仅有一个组合是满足所有限制的。然后按照算出的子树大小分割剩余的序列，递归生成左右子树。最后再 bfs 一遍输出。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
const int N = 40;
7

8
struct Node {
9
    int val;
10
    Node *ls, *rs;
11
};
12

13
int a[N];
14

15
Node *build(int l, int r) {
16
    if (l > r) return nullptr;
17
    Node *u = (Node *)malloc(sizeof(Node));
18
    u->val = a[r];
19
    r--;
20
    for (int i = 1; i <= 5; ++i) {
21
        int lsize = (1 << i) - 1, rsize = r - l + 1 - lsize;
22
        if (lsize >= rsize && rsize >= 0 && abs(lsize - rsize) <= (1 << i)) {
23
            u->ls = build(l, l + lsize - 1), u->rs = build(l + lsize, r);
24
            break;
25
        }
26
        rsize = (1 << i) - 1, lsize = r - l + 1 - rsize;
27
        if (lsize >= 0 && rsize >= 0 && abs(lsize - rsize) <= (1 << i)) {
28
            u->ls = build(l, l + lsize - 1), u->rs = build(l + lsize, r);
29
            break;
30
        }
31
    }
32
    return u;
33
}
34

35
int main() {
36
    int n;
37
    scanf("%d", &n);
38
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
39
    Node *tr = build(1, n);
40
    queue<Node*> q;
41
    q.emplace(tr);
42
    bool first = true;
43
    int flag = 0;
44
    while (!q.empty()) {
45
        Node *x = q.front();
46
        q.pop();
47
        if (x == nullptr) {
48
            if (flag == 0) flag = 1;
49
        }
50
        else {
51
            if (flag == 1) flag = 2;
52
            if (first) first = false;
53
            else cout << ' ';
54
            cout << x->val;
55
            q.emplace(x->ls);
56
            q.emplace(x->rs);
57
        }
58
    }
59
    cout << endl;
60
    return 0;
61
}

银行排队问题之单队列多窗口服务#

我不能理解，题上说 这里假设每位顾客事务被处理的最长时间为60分钟，然后样例给出了 61，如果不管就 wa，如果强制让 p 和 60 取 min 就过了。我只能说诡异。

模拟就行，按照时间遍历顾客，假设现在遍历到第 i 个，开一个数组 ls 维护每个窗口处理完前 i - 1 个顾客需要的时间。考虑当前顾客选择窗口，所有时间小于t_i 都是等价的，为了方便处理直接改成 t_i，对后来的顾客也没有影响，现在只需要求 $idx = \argmin_k ls_k$ 。然后 ls_idx += t_i，更新一下这个窗口的任务，之后继续下一个人。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1010, M = 11;
6

7
int ls[M], cnt[M]; // last finish tine
8
int t[N], p[N];
9

10

11
int main() {
12
    int n, k;
13
    scanf("%d", &n);
14
    for (int i = 1; i <= n; ++i) {
15
        scanf("%d%d", &t[i], &p[i]);
16
        p[i] = min(p[i], 60);
17
    }
18
    scanf("%d", &k);
19
    int tot = 0, max_t = 0, lst_t = 0;
20
    for (int i = 1; i <= n; ++i) {
21
        int mn_idx = 1;
22
        for (int j = 1; j <= k; ++j) {
23
            ls[j] = max(ls[j], t[i]);
24
            if (ls[j] < ls[mn_idx]) mn_idx = j;
25
        }
26
        tot += ls[mn_idx] - t[i];
27
        max_t = max(max_t, ls[mn_idx] - t[i]);
28
        ls[mn_idx] += p[i];
29
        cnt[mn_idx]++;
30
    }
31
    for (int i = 1; i <= k; ++i) lst_t = max(lst_t, ls[i]);
32
    printf("%.1f %d %d\n", (double)tot / n, max_t, lst_t);
33
    for (int i = 1; i <= k; ++i) {
34
        if (i != 1) putchar(' ');
35
        printf("%d", cnt[i]);
36
    }
37
    printf("\n");
38
    return 0;
39
}

银行业务队列简单模拟#

奇数偶数先单独存一下，然后两个奇数一个偶数一直输出，如果没有了就跳过，直到全输出完。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
bool first = true;
7

8
void pop(queue<int> &q) {
9
    if (!q.empty()) {
10
        if (first) first = false;
11
        else printf(" ");
12
        printf("%d", q.front());
13
        q.pop();
14
    }
15
}
16

17
int main() {
18
    queue<int> q1, q2;
19
    int n;
20
    scanf("%d", &n);
21
    for (int i = 1; i <= n; ++i) {
22
        int t;
23
        scanf("%d", &t);
24
        if (t & 1) q1.emplace(t);
25
        else q2.emplace(t);
26
    }
27
    int f = 1;
28
    while (!q1.empty() || !q2.empty()) {
29
        if (f % 3 == 0) pop(q2);
30
        else pop(q1);
31
        f = (f + 1) % 3;
32
    }
33
    printf("\n");
34
    return 0;
35
}

Star's Blog