树

数叶子结点

由于给出的是非叶子结点和它对应的子节点，所以采用邻接表的形式来建树
判断叶子结点：h[u] == -1

#include <time.h>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int h[N], e[N], ne[N], idx;
int cnt[N], max_depth;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u, int depth) {
    if (h[u] == -1) {
        cnt[depth]++;
        max_depth = max(max_depth, depth);
        return;
    }
    for (int i = h[u]; i != -1; i = ne[i]) {
        dfs(e[i], depth + 1);
    }
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int fa, k;
        cin >> fa >> k;
        while (k--) {
            int id;
            cin >> id;
            add(fa, id);
        }
    }    
    dfs(1, 0);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; i++)
        cout << ' ' << cnt[i];
    cout << endl;
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

树的遍历

模板：由后序/前序遍历+中序遍历得到层序遍历

#define SUBMIT
#include <time.h>
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 40;
int post[N], in[N];
unordered_map<int, int> l, r, pos;
queue<int> q;
int build(int il, int ir, int pl, int pr) {
    int root = post[pr];
    int k = pos[root];
    if (il < k) {
        l[root] = build(il, k - 1, pl, pl + k - 1 - il);
    }
    if (ir > k) {
        r[root] = build(k + 1, ir, pl + k - il, pr - 1);
    }
    return root;
}
void bfs(int root) {
    q.push(root);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (l.count(t)) q.push(l[t]);
        if (r.count(t)) q.push(r[t]);
        cout << t;
        if (!q.empty()) cout << ' ';
    }
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> post[i];
    for (int i = 0; i < n; i++) {
        cin >> in[i];
        pos[in[i]] = i;
    }
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

最深的根

一个无环连通图可以被视作一个树，注意是图中是无向边
判断是不是连通图可以看连通分量的个数是否为1，采用并查集
遍历时需要避开父结点，这题不好直接用h[u] == -1来判断根节点，因为相邻的结点至少有父节点

#include <time.h>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e4 + 10, M = N * 2;
int p[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int dfs(int u, int pa) {
    int ans = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        if (e[i] != pa) {
            ans = max(ans, dfs(e[i], u) + 1);
        }
    }
    return ans;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    int k = n;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
        int fa = find(a), fb = find(b);
        if (fa != fb) {
            p[fa] = fb;
            k--;
        }
    }
    if (k > 1) {
        printf("Error: %d components", k);
    }
    else {
        vector<int> ans;
        int max_depth = -1;
        for (int i = 1; i <= n; i++) {
            int depth = dfs(i, -1);
            if (depth > max_depth) {
                max_depth = depth;
                ans.clear();
                ans.push_back(i);
            }
            else if (depth == max_depth) {
                ans.push_back(i);
            }
        }
        for (auto r: ans) {
            printf("%d\n", r);
        }
    }
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

判断二叉搜索树

整数序列从小到大排序的结果就是二叉搜索树中序遍历
判断它是否可能是某个二叉搜索树或其镜像进行前序遍历的结果，就是看能否构建出这样一棵树
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值，提示我们根节点是第一个遍历到的结点，对于镜像，遍历的方向要反过来

#include <time.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int pre[N], in[N], post[N];
int cnt;
bool build(int il, int ir, int pl, int pr, int type) {
    int root = pre[pl];
    int k;
    if (type == 0) {
        for (k = il; k <= ir; k++) {
            if (in[k] == root) {
                break;
            }
        }
        if (k > ir) return false;
    }
    else {
        for (k = ir; k >= il; k--) {
            if (in[k] == root) {
                break;
            }
        }
        if (k < il) return false;
    }
    bool flag = true;
    if (il < k) {
        flag &= build(il, k - 1, pl + 1, pl + k - il, type);
    }
    if (ir > k) {
        flag &= build(k + 1, ir, pl + k - il + 1, pr, type);
    }
    post[cnt++] = root;
    return flag;
}
void printpost(int n) {
    cout << post[0];
    for (int i = 1; i < n; i++) {
        cout << ' ' << post[i];
    }
    cout << endl;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        in[i] = pre[i];
    }
    sort(in, in + n);
    if (build(0, n - 1, 0, n - 1, 0)) {
        cout << "YES" << endl;
        printpost(n);
    }
    else {
        reverse(in, in + n);
        cnt = 0;
        if (build(0, n - 1, 0, n - 1, 1)) {
            cout << "YES" << endl;
            printpost(n);
        }
        else cout << "NO" << endl;
    }
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

完全二叉搜索树

已知中序遍历，由于是完全二叉树，所以可以唯一确定，进行中序遍历填充树即可
完全二叉树的数组表示就是层序遍历

#include <time.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], t[N];
int cnt, n;
void dfs(int u) {
    if (u * 2 <= n) dfs(u * 2);
    t[u] = a[cnt++];
    if (u * 2 + 1 <= n) dfs(u * 2 + 1);
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    dfs(1);
    cout << t[1];
    for (int i = 2; i <= n; i++) cout << ' ' << t[i];
    cout << endl;
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

再次树遍历

使用栈可以以非递归方式实现二叉树的中序遍历
push前面如果也是push，那么该结点就是上面一个结点的左儿子，不然是右儿子
两个儿子表示法即可

#define SUBMIT
#include <time.h>
#include <iostream>
#include <stack>
using namespace std;
const int N = 40;
stack<int> s;
int l[N], r[N];
void dfs(int u, int root) {
    if (!u) return;
    dfs(l[u], root);
    dfs(r[u], root);
    cout << u;
    if (u != root) cout << ' ';
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    int root;
    int last = -1;
    int type;
    for (int i = 0; i < 2 * n; i++) {
        string op;
        cin >> op;
        if (op == "Push") {
            int x;
            cin >> x;
            if (last == -1) {
                root = x;
            }
            else if (type == 0) {
                l[last] = x;
            }
            else {
                r[last] = x;
            }
            type = 0;
            last = x;
            s.push(x);
        }
        else {
            int t = s.top();
            s.pop();
            last = t;
            type = 1;
        }
    }
    dfs(root, root);
    cout << endl;
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

完全二叉树

判断完全二叉树的话，考虑数组表示法，下标从1开始计数，这样比较最大下标与结点数目之间的关系，完全二叉树应该是正好n个

#include <time.h>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int l[N], r[N];
int has_fa[N];
int maxk, maxid;
void dfs(int u, int k) {
    if (u == -1) return;
    if (k > maxk) {
        maxk = k;
        maxid = u;
    }
    dfs(l[u], k * 2);
    dfs(r[u], k * 2 + 1);
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    for (int i = 0; i < n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s1 != "-") {
            l[i] = stoi(s1);
            has_fa[l[i]] = true;
        }
        if (s2 != "-") {
            r[i] = stoi(s2);
            has_fa[r[i]] = true;
        }
    }    
    int root = -1;
    while (has_fa[++root]);
    dfs(root, 1);
    if (maxk == n) {
        cout << "YES" << ' ' << maxid << endl;
    }
    else {
        cout << "NO" << ' ' << root << endl;
    }
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

二叉搜索树最后两层结点数量

构建二叉搜索树模板
dfs获取最大深度，记录每个深度对应的结点数目

#include <time.h>
#include <iostream>
using namespace std;
const int N = 1010;
int l[N], r[N], idx, w[N];
int max_depth, num[N];
void insert(int &root, int v) {    // root可变
    if (!root) {
        root = ++idx;
        w[root] = v;
        return;
    }
    if (v <= w[root]) insert(l[root], v);
    else insert(r[root], v);
}
void dfs(int u, int depth) {
    if (!u) return;
    num[depth]++;
    max_depth = max(max_depth, depth);
    dfs(l[u], depth + 1);
    dfs(r[u], depth + 1);
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    int root = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        insert(root, x);
    }    
    dfs(root, 0);
    int n1 = num[max_depth], n2 = num[max_depth - 1];
    printf("%d + %d = %d\n", n1, n2, n1 + n2);
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

前序和后序遍历

如果只通过前序遍历和后序遍历，则有可能无法确定唯一二叉树
那么枚举前序遍历当中左子树的边界就好了，注意可以没有左子树
中序遍历如果需要右子树来判断合法性，此时使用字符串拼接是个好办法，先暂存左右子树的结果

#include <time.h>
#include <iostream>
using namespace std;
const int N = 40;
int pre[N], post[N];
int dfs(int l1, int r1, int l2, int r2, string &s) {
    if (l1 > r1) return 1;
    if (pre[l1] != post[r2]) return 0;
    int root = pre[l1];
    int cnt = 0;
    for (int i = l1; i <= r1; i++) {    // 可以没有左子树
        string l, r;
        int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, l);
        int rcnt = dfs(i + 1, r1, l2 + i - l1, r2 - 1, r);
        if (lcnt && rcnt) {
            s = l + to_string(root) + ' ' + r;    // 中序遍历
            cnt += lcnt * rcnt;
        }
    }
    return cnt;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) cin >> post[i];
    string ans;
    int cnt = dfs(0, n - 1, 0, n - 1, ans);
    if (cnt > 1) {
        puts("No");
    }
    else {
        puts("Yes");
    }
    ans.pop_back();
    cout << ans << endl;
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

AVL树的根

模板

#include <time.h>
#include <iostream>
using namespace std;
const int N = 30;
int l[N], r[N], h[N], v[N], idx;
int get_balance(int u) {
    return h[l[u]] - h[r[u]];
}
void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}
void L(int &u) {
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u), update(p);
    u = p;
}
void R(int &u) {
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u), update(p);
    u = p;
}
void insert(int &u, int w) {
    if (!u) u = ++idx, v[u] = w;
    else if (w < v[u]) {
        insert(l[u], w);
        if (get_balance(u) == 2) {
            if (get_balance(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }
    }
    else {
        insert(r[u], w);
        if (get_balance(u) == -2) {
            if (get_balance(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    int root = 0;
    while (n--) {
        int w;
        cin >> w;
        insert(root, w);
    }    
    cout << v[root] << endl;
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

判断完全 AVL 树

把判断的过程放到层序遍历当中去

#include <time.h>
#include <iostream>
using namespace std;
const int N = 30;
int l[N], r[N], h[N], w[N], idx;
int pos[N * 2];
int q[N], hh, tt = -1;
int n;
int get_balance(int u) {
    return h[l[u]] - h[r[u]];
}
void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}
void L(int &u) {
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u), update(p);
    u = p;
}
void R(int &u) {
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u), update(p);
    u = p;
}
void insert(int &u, int v) {
    if (!u) {
        u = ++idx;
        w[u] = v;
    }
    else if (v < w[u]) {
        insert(l[u], v);
        if (get_balance(u) == 2) {
            if (get_balance(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }        
    }
    else {
        insert(r[u], v);
        if (get_balance(u) == -2) {
            if (get_balance(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}
bool bfs(int root) {
    q[++tt] = root;
    pos[root] = 1;
    bool flag = true;
    while (hh <= tt) {
        int t = q[hh++];
        int p = pos[t];
        if (p > n) flag = false;
        if (l[t]) {
            pos[l[t]] = p * 2;
            q[++tt] = l[t];
        }
        if (r[t]) {
            pos[r[t]] = p * 2 + 1;
            q[++tt] = r[t];
        }
    }
    return flag;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    cin >> n;
    int root = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        insert(root, v);
    }    
    bool ans = bfs(root);
    cout << w[q[0]];
    for (int i = 1; i < n; i++) cout << ' ' << w[q[i]];
    cout << endl;
    if (ans) puts("YES");
    else puts("NO");
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

判断红黑树

和红黑树关系不大，在建树的过程中递归完成判断即可
注意有可能无法构建出二叉搜索树
权值因为红色结点会变成负数，因此排序的时候要用正数来排

#include <time.h>
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 40;
int in[N], pre[N];
unordered_map<int, int> pos;
bool ans;
int build(int il, int ir, int pl, int pr, int &sum) {
    int root = pre[pl];
    int k = pos[abs(root)];    // 用正数判断
    if (k < il || k > ir) {    // 可能不存在
        ans = false;
        return 0;
    }
    int left = 0, right = 0, ls = 0, rs = 0;
    if (il < k) {
        left = build(il, k - 1, pl + 1, pl + k - il, ls);
    }
    if (k < ir) {
        right = build(k + 1, ir, pl + k - il + 1, pr, rs);
    }
    if (ls != rs) ans = false;
    sum = ls;
    if (root < 0) {
        if (left < 0 || right < 0) {
            ans = false;
        }
    }
    else sum++;
    return root;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int k;
    cin >> k;
    while (k--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> pre[i];
            in[i] = abs(pre[i]);
        }
        sort(in, in + n);
        pos.clear();
        for (int i = 0; i < n; i++) pos[in[i]] = i;
        ans = true;
        int sum = 0;
        int root = build(0, n - 1, 0, n - 1, sum);
        if (root < 0) ans = false;
        if (ans) puts("Yes");
        else puts("No");
    }    
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

中缀表达式

如果结点不是叶子，那么需要加上左右括号

#define SUBMIT
#include <time.h>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int l[N], r[N], has_fa[N];
bool leaf[N];
string v[N];
string dfs(int u) {
    string ls, rs;
    if (l[u] != -1) {
        ls = dfs(l[u]);
        if (!leaf[l[u]]) ls = '(' + ls + ')';
    }
    if (r[u] != -1) {
        rs = dfs(r[u]);
        if (!leaf[r[u]]) rs = '(' + rs + ')';
    }
    return ls + v[u] + rs;
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> l[i] >> r[i];
        if (l[i] == -1 && r[i] == -1) leaf[i] = true;
        if (l[i] != -1) has_fa[l[i]] = true;
        if (r[i] != -1) has_fa[r[i]] = true;
    }
    int root = 0;
    while (has_fa[++root]);
    cout << dfs(root);
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}