树的定义、表示与存储
从家谱到程序里的层级结构

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

const int MAXN = 105;
vector<int> child[MAXN];
int cnt[MAXN];                 // 每一层有多少个结点
int n, depth = 0;

void dfs(int u, int d) {
    if (d > depth) depth = d;
    cnt[d]++;
    for (int i = 0; i < (int)child[u].size(); i++) dfs(child[u][i], d + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        child[u].push_back(v);
    }

int sum = 0, treeDeg = 0, leaf = 0;
    cout << "各结点度数：";
    for (int u = 1; u <= n; u++) {
        int d = child[u].size();
        cout << d << " ";
        sum += d;
        if (d > treeDeg) treeDeg = d;
        if (d == 0) leaf++;
    }
    cout << endl;

cout << "① 结点数 n = " << n << "，边数 = " << n - 1
         << " → 树的边数恒等于结点数减一" << endl;
    cout << "② 度数之和 = " << sum << "，加 1 = " << sum + 1
         << " → 结点数 = 度数之和 + 1" << endl;
    cout << "③ 树的度 = " << treeDeg << "，叶子个数 = " << leaf << endl;

dfs(1, 1);
    cout << "④ 树的深度 = " << depth << endl;

cout << "各层结点数与该层上界（m 为树的度）：" << endl;
    int up = 1;
    for (int d = 1; d <= depth; d++) {
        cout << "  第 " << d << " 层：实际 " << cnt[d]
             << " 个，上界 " << up << " = " << treeDeg << "^" << d - 1 << endl;
        up *= treeDeg;
    }
    return 0;
}

#include <iostream>
using namespace std;

// 双亲表示法：每个结点只记一件事 —— 我的双亲在哪
const int MAXN = 105;
struct PNode {
    int data;      // 结点编号
    int parent;    // 双亲的下标，-1 表示没有双亲（根）
} t[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        t[i].data = i + 1;      // 下标 i 存编号 i+1
        cin >> t[i].parent;     // 依次输入每个结点的双亲下标，根输入 -1
    }

cout << "下标\t编号\t双亲下标\t双亲编号" << endl;
    for (int i = 0; i < n; i++) {
        cout << i << "\t" << t[i].data << "\t" << t[i].parent << "\t";
        if (t[i].parent == -1) cout << "无（根）" << endl;
        else cout << t[t[i].parent].data << endl;
    }

// ① 找根：parent == -1 的结点有且只有一个
    int root = -1, cnt = 0;
    for (int i = 0; i < n; i++)
        if (t[i].parent == -1) { root = i; cnt++; }
    cout << "根：下标 " << root << "，编号 " << t[root].data
         << "（双亲为 -1 的结点共 " << cnt << " 个）" << endl;

// ② 顺着 parent 一路往上爬，就得到祖先链
    int x = 7;                  // 想查编号 8 的祖先
    cout << t[x].data << " 的祖先链（含自己）：";
    while (x != -1) {
        cout << t[x].data << " ";
        x = t[x].parent;
    }
    cout << endl;
    return 0;
}

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

// 孩子表示法：每个结点拉一条链表，串起它所有的孩子
const int MAXN = 105;
vector<int> child[MAXN];      // child[u] 里存 u 的所有孩子
int n, maxDep = 0;

void dfs(int u, int dep) {                 // 先根遍历，顺便求深度
    if (dep > maxDep) maxDep = dep;
    cout << u << " ";
    for (int i = 0; i < (int)child[u].size(); i++)
        dfs(child[u][i], dep + 1);
}

int subtree(int u) {                       // 以 u 为根的子树有多大
    int s = 1;
    for (int i = 0; i < (int)child[u].size(); i++)
        s += subtree(child[u][i]);
    return s;
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {          // n 个结点恰好 n-1 条边
        int u, v;                          // u 是 v 的双亲
        cin >> u >> v;
        child[u].push_back(v);
    }

cout << "孩子表示法（邻接表）：" << endl;
    for (int u = 1; u <= n; u++) {
        cout << u << " -> ";
        for (int i = 0; i < (int)child[u].size(); i++)
            cout << child[u][i] << " ";
        cout << endl;
    }

cout << "先根遍历：";
    dfs(1, 1);
    cout << endl << "树的深度：" << maxDep << endl;

cout << "层序遍历：";                   // 队列实现层序
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int i = 0; i < (int)child[u].size(); i++) q.push(child[u][i]);
    }
    cout << endl;

cout << "叶子：";
    int leaf = 0;
    for (int u = 1; u <= n; u++)
        if (child[u].size() == 0) { cout << u << " "; leaf++; }
    cout << endl << "叶子个数：" << leaf << endl;

cout << "各结点子树大小：";
    for (int u = 1; u <= n; u++) cout << u << ":" << subtree(u) << " ";
    cout << endl;
    return 0;
}

#include <iostream>
using namespace std;

// 孩子兄弟表示法：两个指针就够了 —— 第一个孩子 + 下一个兄弟
const int MAXN = 105;
int fc[MAXN], ns[MAXN];        // firstChild / nextSibling，-1 表示空
int n;

void preorder(int u) {         // 按"根 → 孩子 → 兄弟"遍历整棵转换后的二叉树
    if (u == -1) return;
    cout << u << " ";
    preorder(fc[u]);           // 先一头扎进孩子
    preorder(ns[u]);           // 再回头处理兄弟
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) { fc[i] = -1; ns[i] = -1; }

for (int i = 1; i <= n; i++) {
        int u, k;
        cin >> u >> k;                     // u 有 k 个孩子，后面依次列出
        if (k > 0) {
            cin >> fc[u];
            int last = fc[u];
            for (int j = 1; j < k; j++) {
                int v; cin >> v;
                ns[last] = v; last = v;    // 把兄弟串成一条链
            }
        }
    }

cout << "编号\tfirstChild\tnextSibling" << endl;
    for (int i = 1; i <= n; i++)
        cout << i << "\t" << fc[i] << "\t\t" << ns[i] << endl;

cout << "各结点的孩子（顺着兄弟链走）：" << endl;
    for (int u = 1; u <= n; u++) {
        cout << u << " -> ";
        int v = fc[u];
        while (v != -1) { cout << v << " "; v = ns[v]; }
        cout << endl;
    }

cout << "转换后二叉树的先序遍历：";
    preorder(1);
    cout << endl;
    return 0;
}

#include <iostream>
using namespace std;

// ① 并查集：双亲表示法的"高级玩法"，只关心"谁和谁是一伙的"
const int MAXN = 105;
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int a, int b) { fa[find(a)] = find(b); }

// ② 二叉树的链式存储（下一讲的主角，先认识一下）
struct Node {
    int val;
    int lch, rch;               // 左右孩子的下标，-1 表示空
} bt[MAXN];

int main() {
    for (int i = 1; i <= 5; i++) fa[i] = i;
    merge(1, 2); merge(3, 4); merge(2, 3);
    cout << "并查集：1 与 4 是否同集合？" << (find(1) == find(4) ? "Yes" : "No") << endl;
    cout << "代表元 find(1) = " << find(1) << endl;

bt[1].val = 1; bt[1].lch = 2; bt[1].rch = 3;
    bt[2].val = 2; bt[2].lch = -1; bt[2].rch = -1;
    bt[3].val = 3; bt[3].lch = -1; bt[3].rch = -1;
    cout << "二叉树：根 " << bt[1].val
         << "，左孩子 " << bt[bt[1].lch].val
         << "，右孩子 " << bt[bt[1].rch].val << endl;
    return 0;
}