PAT – ADVANCED – 树形结构精讲

本文详细解析二叉树、二叉搜索树、哈夫曼树、并查集、堆等树形结构和算法在PAT真题中的选型原因、应用方法及实现细节

树

A1004 叶节点计数

题意为统计每层叶节点个数，可采用BFS方式遍历树计数，遍历时记录当前层数level，每到叶节点处将对应层的计数变量自增

ε=ε=ε=(~￣▽￣)~ Q：DFS怎么做？

(〃￣︶￣) A：一层叶节点个数由“数组[层数]”记录，递归式DFS(root, level + 1)可递增层数，每到一个节点都判断是否叶节点再计数

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 100;
vector<int> tree[maxn];
int num[maxn];
int level = 0;

int main() {
    queue<int> q;
    int N, M, ID, K, S, sz;
    scanf("%d %d", &N, &M);

    while (M--) {
        scanf("%d %d", &ID, &K);
        while (K--) {
            scanf("%d", &S);
            tree[ID].push_back(S);
        }
    }

    q.push(1);
    while (!q.empty()) {
        sz = q.size();
        for (int i = 0; i < sz; i++) {
            S = q.front();
            q.pop();
            if (!tree[S].size())
                num[level]++;
            for (int &x : tree[S])
                q.push(x);
        }
        level++;
    }

    for (int i = 0; i < level - 1; i++)
        printf("%d ", num[i]);
    printf("%d\n", num[level - 1]);

    return 0;
}

A1020 中后序建树+层序遍历

每个子树都能和相应的中序、后序子序列一一对应，子树后序的末尾节点总是根节点，对应的中序中该根节点左右部分为左右子树，从而不断拿到子树的根节点作为当前节点的叶节点递归建树，建好的树用队列层序遍历

(○´･д･)ﾉQ:不是可以省略树的结构体，直接将节点按完全二叉树的方式存进数组中吗，这样层序遍历直接从头到尾扫描数组就OK啊？

( •̀ ω •́ )✧A:问得好，确实可以只传一个索引i进来，递归时左子树根存在2i，右子树根存在2i+1，层序遍历如此简洁的想法也很棒！然而这个题最多有31个节点，看似节省了非常多的内存，如果是只有右子树那种长链型的，内存占用2的31次方，OMG，而且输出巨慢

(○´･д･)ﾉQ:这个递归的传参给我整傻了，而且怎么结束递归啊

(╯‵□′)╯炸弹！•••～● A:我TM当时也傻了，后来画了个图，嗯…具体如下图，找到中序根节点的位置可以帮我们计算出左右子树的大小，这样的话就能在后序序列中确定出左子树和右子树的范围。递归下去，范围划到只有一个节点的时候必然是一个独立的叶节点了，把它返回链接到父结点上，如果范围不合法说明没这个叶节点返回空指针，当前层本身是一个根节点也给它返回挂到父结点上

(⊙o⊙)？Q:输出的时候，我拿队列只有一个节点的情况判断末尾的，然后就GG了

ο(=•ω＜=)ρ⌒☆A:比如只有根节点的时候也是只有一个节点啊，换个思路，那个节点数目n很重要，每出队列一次，就给它自减，判0就OK了

#include <iostream>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

const int maxn = 31;
int po[maxn];
int in[maxn];

struct TreeNode {
    int val;
    TreeNode *lNode;
    TreeNode *rNode;
    TreeNode(int v, TreeNode *l, TreeNode *r) : val(v), lNode(l), rNode(r) {}
};

TreeNode *buildTree(int plo, int phi, int ilo, int ihi) {
    if (phi < plo) return nullptr;
    if (phi == plo) return new TreeNode(po[plo], nullptr, nullptr);

    int irId;
    int root = po[phi];
    for (irId = ilo; root != in[irId]; irId++);
    int lLen = irId - ilo;
    int rLen = ihi - irId;

    return new TreeNode(root, buildTree(plo, plo + lLen - 1, ilo, irId - 1), buildTree(plo + lLen, phi - 1, irId + 1, ihi));
}

int main() {
    memset(po, 0, sizeof(po));
    memset(in, 0, sizeof(in));

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &po[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &in[i]);

    queue<TreeNode *> q;
    q.push(buildTree(1, n, 1, n));
    while (!q.empty()) {
        TreeNode *node = q.front();
        q.pop(); n--;
        if (n == 0) printf("%d\n", node->val);
        else printf("%d ", node->val);
        if (node->lNode) q.push(node->lNode);
        if (node->rNode) q.push(node->rNode);
    }

    return 0;
}

A1053 路径权值和

典型的DFS类问题。可分解为两个问题：一是找到给定路径并记录，二是非升序输出

(⓿_⓿) Q：DFS我会，但是给定路径怎么记录，而且还要记录不同路径，眼花头秃

(ง •_•)ง A：别慌。DFS的遍历过程可由栈模拟，每进入子层相当于子节点入栈，每回到父层相当于子结点出栈，且栈中始终只有一条路径，由此从栈底到栈顶可唯一打印路径。然鹅使用stack和queue均需所有节点弹出数据结构，破坏继续调用的条件，因此换用vector最为妥当

……]((o )’彡☆ Q：非升序输出怎么搞？

( •̀ ω •́ )y A：举个栗子~现在定位到DFS访问子节点的代码行，如果我们递归访问子节点3，返回到当前层之后接着访问更小子节点2的话，输出的访问结果将依次是3XXX，2XXX。由此读入子序列后顺带排个降序，DFS每层就都会降序访问子节点啦，排序就用库函数sort简单方便！

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int S;
const int maxn = 100;
vector<int> q;

struct Node {
    int w;
    vector<int> v;
} tree[maxn];

bool cmp(int a, int b) {
    return tree[a].w > tree[b].w;
}

void DFS(int root, int sum) {
    q.push_back(tree[root].w);
    int add = sum + tree[root].w;

    if (add > S) return;

    if (add == S && !tree[root].v.size()) {
        for (int i = 0; i < q.size() - 1; i++)
            printf("%d ", q[i]);
        printf("%d\n", q[q.size() - 1]);
    }

    else for (int &x : tree[root].v) {
        DFS(x, add);
        q.pop_back();
    }
}

int main() {
    int N, M, W, i, n, s;
    scanf("%d %d %d", &N, &M, &S);
    for (int i = 0; i < N; i++)
        scanf("%d", &tree[i].w);

    while (M--) {
        scanf("%d %d", &i, &n);
        while (n--) {
            scanf("%d", &s);
            tree[i].v.push_back(s);
        }
        sort(tree[i].v.begin(), tree[i].v.end(), cmp);
    }

    DFS(0, 0);

    return 0;
}

A1079 叶节点及深度

题意为货物从初始供货商经过多级分销商加价到达零售商的售卖总价，即 $\scriptsize 总价=\sum\limits_{零售商1}^{零售商n} 单价×数量×(1+百分比)^{零售商i层级}$，供货商即根节点，分销商为非叶节点，零售商为叶节点，零售商层级即叶节点深度，此题关键点在于判断叶节点和获取叶节点深度

( •̀ .̫ •́ )✧ Q：我有一个想法，用树的数组表示，每个节点存储其父结点索引；读到叶节点时入队列，最后只取队列中的叶节点，逐次溯到根即为深度，这样处理的节点数是不是大大减小啦

ฅʕ•̫͡•ʔฅ A：想法很棒哟，这种树的表示想必是来自并查集吧！浇盆冷水，当存在大量叶节点的时候，假设为满m叉树，计算叶节点深度的总次数为 $\scriptsize O(m^{logn}logn)$，$\scriptsize 10^5$问题规模会超时的！而如果我们采用DFS或BFS，$\scriptsize O(n)$ 已经保证计算所有节点深度啦。那为何用BFS没用DFS呢，因为递归调用的开销较大，采用迭代的性能当然会更好咯，而且层序遍历的层数就是深度，计数方便很多嘛

(○｀ 3′○) Q：那我在建树的时候，每连一个子节点就让它在父结点深度上累加1，这样就能直接用！

(￣▽￣)" A：呃…如果输入数据是先建立子树，后续才挂到父结点上，那怎么办，向下遍历改变所有子节点嘛？存储子节点再去遍历，这样好像和DFS遍历树结构没什么区别

((￣_￣|||)) Q：是哦……等一下！让子节点溯根的时候在已计算的节点上标记一下深度，其他子节点访问到公共节点的时候就能共用…

d=====(￣▽￣*)b Q：哦，是嘛？灵魂三问：问题一：公共节点真的很多嘛？问题二：公共节点真的足够深以减少重复计算嘛？最后致命一击：从根到叶累计才可以共用深度，你的方向是从叶到根！你可能是想到并查集的合并：两根节点保存了各自树的大小，合并时直接溯根合并大小，得的是整体的结果；而这里是每个叶节点都要计算到根的距离，是个体的结果！别挣扎啦……听话，乖乖去遍历

(╬▔皿▔)凸 Q：ehhhhhh，生气(脏话！)，还有段错误什么鬼？

( •̀ ω •́ )y A：快去检查你有没有数组越界，无限递归，空指针赋值！弱弱的提醒一下，10的五次方后面有5个0

#include <iostream>
#include <cmath>
#include <queue>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100001;

struct TreeNode {
    int qty;
    vector<int> sub;
} tree[maxn];

int main() {
    int N, num, qty, sub, size, depth = 0;
    double P, r, sum = 0;
    TreeNode node;
    scanf("%d %lf %lf\n", &N, &P, &r);
    for (int i = 0; i < N; i++) {
        scanf("%d", &num);
        if (num == 0) {
            scanf("%d\n", &qty);
            tree[i].qty = qty;
        }
        else while (num--) {
            scanf("%d", &sub);
            tree[i].sub.push_back(sub);
        }
    }

    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        size = q.size();
        while (size--) {
            node = tree[q.front()];
            q.pop();
            if (node.sub.size() <= 0)
                sum += P * node.qty * pow(1 + r / 100, depth);
            else for (int x : node.sub)
                q.push(x);
        }
        depth++;
    }

    printf("%.1f\n", sum);

    return 0;
}

A1086 非递归建树

非递归建树的特点是：连续的push一定是栈顶节点的左孩子，pop之后的push是栈顶节点的右孩子；依此保存本次top节点作为下个push节点的父结点，标记push或pop操作决定左还是右子节点。建树后后序遍历。

(ˉ▽￣～) 切～～ Q:人家有更好的想法，push序列是先序的，pop序列是中序的，这个问题不就是中序和先序序列建树嘛

(＃°Д°) A:斯……斯国以

┑(￣Д ￣)┍ Q:不过这个读入格式怎么搞

(●ˇ∀ˇ●) A:你要是会可以用正则表达式啊！不过scanf读入字符串会在空格处结束，这是不是天然分开了push和数字，strcmp和strlen都能解决你的问题

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int n;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

void post(TreeNode *root) {
    if(root == nullptr) return;
    post(root->left);
    post(root->right);
    if (--n) printf("%d ", root->val);
    else printf("%d\n", root->val);
}

int main() {
    int t;
    char s[5];
    bool isL = true;
    scanf("%d\n", &n);

    stack<TreeNode *> stk;
    TreeNode *top, *cur, *root;
    for (int i = 0; i < 2 * n; i++) {
        scanf("%s", s);
        if (strcmp(s, "Push") == 0) {
            scanf("%d", &t);
            if (i == 0) {
                root = new TreeNode(t);
                stk.push(root);
                top = root;
                continue;
            }

            cur = new TreeNode(t);
            if (isL) top->left = cur;
            else {
                top->right = cur;
                isL = true;
            }
            stk.push(cur);
            top = cur;
        }
        else {
            isL = false;
            top = stk.top();
            stk.pop();
        }
    }

    post(root);
}

A1090 DFS遍历树

这道题还是叶节点深度问题，无非新增了一条保存最大深度。在A1079时采用BFS做，这次改用DFS做一下

(oﾟvﾟ)ノ Q：每层递归都比较一下高度嘛

(o゜▽゜)o☆ A：题设所问的最大深度仅在叶节点处，所以我们仅在叶结点处记录更新最大高度可以大幅减少操作次数，况且叶节点处也是递归边界喔

(oﾟvﾟ)ノ Q：哇哦，树的表示又进一步简化了

◕‿◕ A：毕竟每个节点不需要额外存储值，仅记录所有节点的子节点就好啦。索引表示节点，索引值是子节点集合，很容易想到是vector数组！

┏ (゜ω゜)=☞ Q：~t代表什么

(。・∀・)ノ A：这是一个小trick，-1在计算机中是以补码 $\scriptsize (11111111)_B$ 来表示的，取反为0可用来判断-1

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int maxn = 100001;
vector<int> sub[maxn];
int maxH = 0, num = 0;

void DFS(int root, int height) {
    if (sub[root].size() == 0) {
        if (height > maxH) {
            maxH = height;
            num = 1;
        }
        else if (height == maxH)
            num++;

        return;
    }

    for (int &x : sub[root])
        DFS(x, height + 1);
}

int main() {
    int n, t, root;
    double P, r;
    scanf("%d %lf %lf", &n, &P, &r);

    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        if (~t) sub[t].push_back(i);
        else root = i;
    }

    DFS(root, 0);
    printf("%.2f %d\n", P * pow(1 + r / 100, maxH), num);

    return 0;
}

A1094 最大深度节点

题意简化为查询树中最大节点的层所在层数及节点数目

(o-ωｑ)).oO 困 A：树的简化表示，BFS、DFS，是不是都很熟啦，这道题手顺很多了吧

,,ԾㅂԾ,, A：还吼啦，多设个变量来保存最大值就OK！

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int maxNum = 0, maxLevel = 0;
    int N, M, i, s, n, sz, level = 0;
    scanf("%d %d\n", &N, &M);
    vector<int> tree[N + 1];
    queue<int> q;

    while (M--) {
        scanf("%d %d", &i, &n);
        while (n--) {
            scanf("%d", &s);
            tree[i].push_back(s);
        }
    }

    q.push(1);
    while (!q.empty()) {
        level++;
        sz = q.size();
        if (sz > maxNum) {
            maxNum = sz;
            maxLevel = level;
        }
        for (int j = 0; j < sz; j++) {
            i = q.front();
            q.pop();
            for (int &x : tree[i])
                q.push(x);
        }
    }

    printf("%d %d", maxNum, maxLevel);

    return 0;
}

A1102 反转二叉树

二叉树反转实际是将每个节点的左右子树互换。
如果不修改树的原结构，只需修改遍历方式，先右再左即可。
若需修改树的结构，以前中后任一顺序将每一节点左右子树互换即可。

(○｀ 3′○) Q：你没有建树！你根节点在哪！这不是树的结构体表示啊

♪(´▽｀) A：只要逻辑上满足树的结构即可，数组索引标识为根节点，两个数组分别存根节点对应的左右节点，本质上是一样的，甚至更省内存。你看题给输入都是子节点，没给出的自然是根节点咯，标记一下遍历筛选就好嘛。建树的时候直接把它的子树互换反转，这样输出顺序还可以统一

(ノへ￣、) Q：谁能告诉我一下我的输入为什么一直取不对

（￣︶￣）↗　A：先别哭，其实命题人还是蛮贴心的(我信了)。由于存在"-"符号所以只能统一以字符形式输入，你看输入指定了最大10个节点，这样的话0-9就顺理成章。如果没有这个限定，还需要进行多位字符串到数字的转换，要麻烦很多。坑爹的是，首先不要忘记把字符转换回数字！其次"%c"会将空格和换行符也读入进来，所以输入格式一定要考虑到采用"%c %c\n"的形式，第一个读入的数字也给它把换行符拿掉！

#include <iostream>
#include <unordered_set>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

const int maxn = 10;
int root = 0, n;
bool node[maxn];
int lNode[maxn];
int rNode[maxn];
queue<int> q;

void invertLevelTraverse() {
    int c, l, r, cnt = n;
    q.push(root);
    while (!q.empty()) {
        c = q.front();
        q.pop();
        if (--cnt)  printf("%d ", c);
        else        printf("%d\n", c);
        l = lNode[c]; r = rNode[c];
        if (l != -1) q.push(l);
        if (r != -1) q.push(r);
    }
}

void invertInTraverse(int c) {
    if (c == -1) return;
    invertInTraverse(lNode[c]);
    if (--n) printf("%d ", c);
    else printf("%d\n", c);
    invertInTraverse(rNode[c]);
}

int main() {
    char l, r;
    scanf("%d\n", &n);
    memset(lNode, -1, sizeof(lNode));
    memset(rNode, -1, sizeof(rNode));

    for (int i = 0; i < n; i++) {
        scanf("%c %c\n", &l, &r);
        if (l == '-' && r == '-') continue;
        if (l != '-') {
            node[l - '0'] = true;
            rNode[i] = l - '0';
        }
        if (r != '-') {
            node[r - '0'] = true;
            lNode[i] = r - '0';
        }
    }

    for (; node[root]; root++);
    invertLevelTraverse();
    invertInTraverse(root);

    return 0;
}

A1106 最小深度节点

本题同A1094

(≧∇≦)ﾉ Q：我一次就AC了！

=￣ω￣= A：棒哦！不过有两个点要提醒一下。一是INTMAX在判题环境中应使用\_INTMAX_\，否则会导致编译错误；二是一个小小的优化，叶节点处只比较深度，价格只在全局最小时计算一次就OK

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int maxn = 100001;
vector<int> tree[maxn];
int lowL = __INT_MAX__;
int cnt = 0;

void DFS(int root, int level) {
    if (tree[root].size() <= 0) {
        if (level < lowL) {
            lowL = level;
            cnt = 1;
        }
        else if (level == lowL)
            cnt++;
        return;
    }

    for (int &x : tree[root])
        DFS(x, level + 1);
}

int main() {
    int n, s, q;
    double P, r;
    scanf("%d %lf %lf", &n, &P, &r);
    r /= 100;

    for (int i = 0; i < n; i++) {
        scanf("%d", &q);
        while (q--) {
            scanf("%d", &s);
            tree[i].push_back(s);
        }
    }

    DFS(0, 0);
    printf("%.4f %d\n", P * pow(1 + r, lowL), cnt);

    return 0;
}

二叉搜索树

A1043 建立和遍历

本题主要考察的是BST的建立和遍历，要从题设和样例解读出输入序列即为建树插入节点顺序。本题要分清楚 先序、后序遍历和镜像遍历的区别，不要混淆：先后序遍历是指根节点操作在递归之前还是递归之后，镜像遍历是指先递归左节点还是先递归右节点

(・∀・(・∀・(・∀・*) Q：和我在Robert Sedgewick老爷子书上看到的BST不太一样？

╰(￣ω￣ｏ) A：对的。本题在BST建立时，允许重复节点的存在，视新节点 $\scriptsize \geqslant$ 同值节点，注意读题！不过我建树使用的是老爷子的递归版本哦~

(o゜▽゜)o☆ Q：我有更好的建树方法，可以减少递归返回传参。持有root->child的指针将其指向新节点new TreeNode(val)，代码如下

void insert(TreeNode *&root, int val) {
    if(root == nullptr) {
        root = new TreeNode(val);
        return;
    }
    if(val < root->val) insert(root->left, val);
    else insert(root->right, val);
}

o̖⸜((̵̵́ ̆͒͟˚̩̭ ̆͒)̵̵̀)⸝o̗ A：来自蓝胖的鼓掌！

ᕦ(･ㅂ･)ᕤ Q：猴里孩哦~边先序遍历边和输入序列比较

(๑•́ ∀ •̀๑) A：那当然！简便方法是递归先序遍历全部节点，用vector保存遍历结果，再与输入序列vector比较。这里做了一个小优化，题设仅判断是不是即可，因此无需遍历所有节点：由于&&的短路特性，只要左子结果为false，就会节省不必要的右子递归

#include <iostream>
using namespace std;

const int maxn = 1000;
int N, cnt = 0;
int pre[maxn];

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode *insert(int val, TreeNode *root) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) root->left = insert(val, root->left);
    else root->right = insert(val, root->right);
    return root;
}

bool PreTraverse(TreeNode *root) {
    if (root == nullptr) return true;
    if (root->val == pre[cnt++])
        return PreTraverse(root->left) && PreTraverse(root->right);
    else return false;
}

bool MirrorTraverse(TreeNode *root) {
    if (root == nullptr) return true;
    if (root->val == pre[cnt++])
        return MirrorTraverse(root->right) && MirrorTraverse(root->left);
    else return false;
}

void prePostPrint(TreeNode *root) {
    if (root == nullptr) return;
    prePostPrint(root->left);
    prePostPrint(root->right);
    if (--N) printf("%d ", root->val);
    else printf("%d\n", root->val);
}

void mirPostPrint(TreeNode * root) {
    if (root == nullptr) return;
    mirPostPrint(root->right);
    mirPostPrint(root->left);
    if (--N) printf("%d ", root->val);
    else printf("%d\n", root->val);
}

int main() {
    int v;
    TreeNode *root = nullptr;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &v);
        pre[i] = v;
        root = insert(v, root);
    }

    if (PreTraverse(root)) {
        printf("YES\n");
        prePostPrint(root);
    }
    else if (MirrorTraverse(root)) {
        cnt = 0;
        printf("YES\n");
        mirPostPrint(root);
    }
    else printf("NO\n");

    return 0;
}

* A1064 中序建立BST

题目未给建树序列和建树方式，只给层序结果并告知是BST，应是考察BST性质：中序访问是递增序列。中序访问空树时将节点从小到大依次插入就构成了满足BST性质的CBT，由此需对待插元素序列排序

ᶘ ᵒᴥᵒᶅ Q：这个方法真心没想到

(o´ω`o) A：理解不透彻，中序访问是递增序列意味着：中序操作的访问次序与元素递增次序一致，也即中序操作所在位置就是对应的递增元素在BST中的位置，观察详细过程更容易理解：递归过程中第一次中序操作是在最小节点所在位置，第二次是在次小节点位置。还是刷题不够多，要多积累经验！

(≡•̀·̯•́≡) A：仅有满二叉树和堆才会考虑使用以1开始的数组表示方式，父节点表示为i/2，子节点表示为2i、2i+1，访问简单且最大限度节省空间。注意区分odr和cbt哦，odr是下标从0开始的排序后的递增数字序列，cbt是下标从1开始的满二叉搜索树

ᶘ ᵒᴥᵒᶅ Q：学到了

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1001;
int cbt[maxn];
int odr[maxn];
int N, j = 0;

void inTraverse(int i) {
    if (i > N) return;
    inTraverse(2 * i);
    cbt[i] = odr[j++];
    inTraverse(2 * i + 1);
}

int main() {
    int t, i;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d", &odr[i]);

    sort(odr, odr + N);
    inTraverse(1);

    for (i = 1; i < N; i++)
        printf("%d ", cbt[i]);
    printf("%d\n", cbt[N]);
    return 0;
}

A1099 中序建立BST

本题思路与A1064完全相同。不同点在于本题所给结构是静态二叉树，而非满二叉树，因而数据结构选用结构体数组，相应的中序、层序遍历均改用通用方法

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 101;
int N, odr[maxn], j = 0;

struct TreeNode {
    int val;
    int left;
    int right;
} tree[maxn];

void inOrder(int i) {
    if (i == -1) return;
    inOrder(tree[i].left);
    tree[i].val = odr[j++];
    inOrder(tree[i].right);
}

int main() {
    int i;
    queue<int> q;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d %d", &tree[i].left, &tree[i].right);
    for (i = 0; i < N; i++)
        scanf("%d", &odr[i]);

    sort(odr, odr + N);
    inOrder(0);

    q.push(0);
    while (!q.empty()) {
        i = q.front();
        q.pop();
        if (--N)    printf("%d ", tree[i].val);
        else        printf("%d\n", tree[i].val);
        if (tree[i].left != -1)  q.push(tree[i].left);
        if (tree[i].right != -1) q.push(tree[i].right);
    }
    return 0;
}

并查集

A1107 分组topK

题意为有共同爱好的人分为一组，求分组总数和每组人数。并查集针对分组问题和图的连通性问题，详细解析参考本博客理论讲解
类topK问题可用堆处理，使用queue库的数据结构priority_queue，实现自定义排序的声明写法如下

/**
  * @parameter 数据类型
  * @parameter 存储容器
  * @parameter 自定义排序函数
  */
priority_queue<int, vector<int>, cmp> q;

ー( ´ ▽ ` )ﾉ Q：并查集中的id数组在这里代表什么？

ε-(=｀ω´=) A：id数组索引代表并查集中分组对象的标号，值代表所属树的根节点索引，本题中代表被分组的人的标号

〣( ºΔº )〣 Q：怎么进行人员分组？

( •o•) A：仔细读题，并根据样例理解题意，拥有共同爱好的人分为一组：一种思路是建立一个数据结构保存同样爱好的人，map再适合不过，爱好集合中只有一个人说明不是公共爱好无需分组，否则将其依次与集合中第一个人分为同一组；更省内存的思路是map仅保存第一个拥有该爱好的人，每次都将映射相同的人与该人分组

Σ( ⚆൧⚆) Q：分组总数怎么算？

( ´͈ ᵕ `͈ )◞♡ A：两种方法：经典方法是指定一个全局变量，初始每个对象自成一组，每进行一次合并操作减少一组，并查集建立完毕直接可读取数目；另外一种是并查集建立后，遍历所有节点并统计根节点的数目即得分组总数，根节点的判定为i=id[i]

|д･)っ Q：组内数量怎么算？

o(｀ω´ )o A：两种方法：经典方法是指定一个数组保存各节点表示的树大小，初始每个对象自成一组，每合并时修改根节点树大小；另外一种是并查集建立后，遍历累加同根节点的数目即得分组总数

o(｀ω´ )o Q：分组数量怎么排序？

๑乛◡乛๑ A：其实排的是少数几个根节点所对应的树的大小，建立并查集之后，遍历所有节点，检查仅将根节点入堆即可

┻━┻ (ヽ(`Д ́)ノ( ┻━┻ Q：路径压缩的写法有点奇怪？

(∩•̀ω•́)⊃-*⋆ A：看惯了Robert老爷子的递归版本，一下子是不是有点适应不过来了hhh？这里改为迭代版本了，就两个操作：把当前节点指向树根，把子树的节点也指向树根

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

const int maxn = 1001;
int N, num, t, i, cnt;
unordered_map<int, vector<int>> mp;

int sz[maxn];
int id[maxn];

int find(int j) {
    int t0 = j, t1;
    while (j != id[j])
        j = id[j];
    while (t0 != id[t0]) {
        t1 = t;
        t0 = id[t0];
        id[t0] = j;
    }
    return j;
}

void insert(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) return;
    if (pRoot >= qRoot) {
        id[qRoot] = pRoot;
        sz[pRoot] += sz[qRoot];
    }
    else {
        id[pRoot] = qRoot;
        sz[qRoot] += sz[pRoot];
    }
    cnt--;
}

int main() {
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
        sz[i] = 1;
        id[i] = i;
    }
    cnt = N;
    for (i = 1; i <= N; i++) {
        scanf("%d:", &num);
        while (num--) {
            scanf("%d", &t);
            mp[t].push_back(i);
        }
    }

    for (unordered_map<int, vector<int>>::iterator it = mp.begin(); it != mp.end(); it++) {
        vector<int> val = it->second;
        int first = val[0];
        if (val.size() > 1)
            for (i = 1; i < val.size(); i++)
                insert(first, val[i]);
    }
    printf("%d\n", cnt);

    priority_queue<int> q;
    for (i = 1; i <= N; i++)
        if (i == id[i]) q.push(sz[i]);
    for (i = 1; i < cnt; i++) {
        printf("%d ", q.top());
        q.pop();
    }
    printf("%d\n", q.top());

    return 0;
}

堆

A1098 堆排和插排

实际是两种排序算法，只是在每一轮操作后比较待排序列是否是此次操作结果。排序算法详见理论讲解
插入排序是每次将序列右侧元素插回已排序列。
堆排序要建堆、调堆、排序。分别是：初始序列建堆；N/2递减下沉调堆；顶max换末尾排序，顶元素下沉调堆。要牢记上浮和下沉算法细节。

┭┮﹏┭┮ Q：我写的代码好冗长啊，有点凌乱，宽面条泪~

٩̋(ˊ•͈ ꇴ •͈ˋ)و A：两种方法除排序过程外其实是相同的，比如序列相同判定、序列输出两个功能可以抽出函数共用，减少工作量。为省去麻烦，序列下标统一从1开始，减少出错可能性。否则一个i另一个i-1不仅麻烦而且很容易忘记！

(ू˃̣̣̣̣̣̣︿˂̣̣̣̣̣̣ ू) Q：堆排过程有个N–部分，每次都写不对，落雨泪~

((꜆꜄•௰•)꜆꜄ A：这里主要是理解算法。保留N是要互换堆顶a[1]和堆末a[N]，互换之后a[N]已经有序了，这个时候堆顶的下沉操作一定不能再去干扰a[N]，序列边界为[1,N-1]。所以应该在互换后、下沉操作前将N–，N如果别有他用的话另外用个变量保存传i-1

(つД｀)･ﾟ･ Q：输出下次排序结果不会实现，嘤嘤泪~

(｡•̀ᴗ-)✧ A：啊这个！每轮排序后都会比较序列，来判断是否所求步骤。确定是所求步骤的时候设置一个标志，在下轮排序结束后读取这个标志走分支退出即可

(;´༎ຶД༎ຶ`) Q：堆排的结果凑不成样例，大哭不止~

ღ( ´･ᴗ･` ) A：PAT中一般首先推荐本博客提供的标准建堆方法和调整方法，将输入序列视为堆从而无需建堆过程，并从N/2开始倒序依次下沉调整堆序，这样操作的节点数相比其他方法大幅减少。你可能建堆的时候是依次添加进来的，调整堆序是从后向前依次上浮或者从前向后依次下沉的，这样确实会导致堆不唯一而不符合样例

#include <iostream>
using namespace std;

const int maxn = 101;
int ieq[maxn];
int heq[maxn];
int seq[maxn];
int N;

bool isEqual(int *a, int *b) {
    int k = 1;
    for (; k < N; k++)
        if (a[k] != b[k])
            break;
    if (k == N) return true;
    return false;
}

void printSeq(int *a) {
    int k = 1;
    for (; k < N; k++)
       printf("%d ", a[k]);
    printf("%d\n", a[k]);
}

bool iSort() {
    int i, j, k;
    bool go = false;
    for (i = 2; i <= N; i++) {
        for (j = i; j >= 1; j--)
            if (ieq[j] < ieq[j - 1])
                swap(ieq[j], ieq[j - 1]);

        if (go) {
            printf("Insertion Sort\n");
            printSeq(ieq);
            return true;
        }

        go = isEqual(ieq, seq);
    }
    return false;
}

void dn(int i, int n) {
    while (2 * i <= n) {
        int l = 2 * i;
        int r = l + 1;
        if (r <= n && heq[l] < heq[r])
            l = r;
        if (heq[i] < heq[l])
            swap(heq[i], heq[l]);
        else break;
        i = l;
    }
}

void hSort() {
    bool go = false;
    for (int i = N / 2; i >= 1; i--)
        dn(i, N);
    for (int i = N; i > 1; i--) {
        swap(heq[1], heq[i]);
        dn(1, i - 1);

        if (go) {
            printf("Heap Sort\n");
            printSeq(heq);
            break;
        }

        go = isEqual(heq, seq);
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &ieq[i]);
        heq[i] = ieq[i];
    }
    for (int i = 1; i <= N; i++)
        scanf("%d", &seq[i]);
    if(!iSort()) hSort();
    return 0;
}