第9章 树和图

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

int main() {
    int h = 4;
    cout << "深度 " << h << " 最多结点 = " << (int)pow(2, h) - 1 << "\n";   // 15
    int n = 10;
    cout << "完全二叉树 n=" << n << " 叶子数 = " << (n + 1) / 2 << "\n";    // 5
    cout << "完全二叉树 n=" << n << " 深度 = " << (int)log2(n) + 1 << "\n"; // 4
    return 0;
}

#include <iostream>
using namespace std;

// 链式结点
struct TNode { int v; TNode *l, *r; TNode(int x): v(x), l(nullptr), r(nullptr) {} };

int main() {
    // 数组式（根下标 1）：a[1]=A, a[2]=B(左), a[3]=C(右)
    int a[8] = {0, 1, 2, 3, 0, 0, 0, 0};     // 1-based
    cout << "根=" << a[1] << " 左子=" << a[2] << " 右子=" << a[3] << "\n";   // 1 2 3
    // 链式：A 的左 B、右 C
    TNode* A = new TNode(1); A->l = new TNode(2); A->r = new TNode(3);
    cout << "链式 根=" << A->v << " 左=" << A->l->v << " 右=" << A->r->v << "\n";
    return 0;
}

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

struct TNode { int v; TNode *l, *r; TNode(int x): v(x), l(nullptr), r(nullptr) {} };

void preorder(TNode* p)  { if (!p) return; cout << p->v << " "; preorder(p->l);  preorder(p->r); }
void inorder(TNode* p)   { if (!p) return; inorder(p->l);  cout << p->v << " "; inorder(p->r); }
void postorder(TNode* p) { if (!p) return; postorder(p->l); postorder(p->r); cout << p->v << " "; }
void levelorder(TNode* p) {
    if (!p) return; queue<TNode*> q; q.push(p);
    while (!q.empty()) { TNode* u = q.front(); q.pop(); cout << u->v << " ";
        if (u->l) q.push(u->l); if (u->r) q.push(u->r); }
}

int main() {
    // 建树：A(1) 左 B(2) 右 C(3)
    TNode* A = new TNode(1); A->l = new TNode(2); A->r = new TNode(3);
    cout << "前序: "; preorder(A);  cout << "\n";   // 1 2 3
    cout << "中序: "; inorder(A);   cout << "\n";   // 2 1 3
    cout << "后序: "; postorder(A); cout << "\n";   // 2 3 1
    cout << "层序: "; levelorder(A);cout << "\n";   // 1 2 3
    return 0;
}

#include <iostream>
using namespace std;

struct TNode { int v; TNode *l, *r; TNode(int x): v(x), l(nullptr), r(nullptr) {} };

TNode* insert(TNode* p, int x) {
    if (!p) return new TNode(x);
    if (x < p->v) p->l = insert(p->l, x);
    else if (x > p->v) p->r = insert(p->r, x);
    return p;
}
bool find(TNode* p, int x) {
    if (!p) return false;
    if (x == p->v) return true;
    return x < p->v ? find(p->l, x) : find(p->r, x);
}
void inorder(TNode* p) { if (!p) return; inorder(p->l); cout << p->v << " "; inorder(p->r); }

int main() {
    TNode* root = nullptr;
    for (int x : {5, 3, 7, 1, 9}) root = insert(root, x);
    inorder(root); cout << "\n";                 // 1 3 5 7 9（升序）
    cout << "查找 7? " << (find(root, 7) ? "是" : "否") << "\n";  // 是
    return 0;
}

#include <iostream>
using namespace std;

struct TNode { int v; TNode *l, *r; TNode(int x): v(x), l(nullptr), r(nullptr) {} };

TNode* insert(TNode* p, int x) {
    if (!p) return new TNode(x);
    if (x < p->v) p->l = insert(p->l, x);
    else if (x > p->v) p->r = insert(p->r, x);
    return p;
}
TNode* minNode(TNode* p) { while (p->l) p = p->l; return p; }
TNode* erase(TNode* p, int x) {
    if (!p) return nullptr;
    if (x < p->v) p->l = erase(p->l, x);
    else if (x > p->v) p->r = erase(p->r, x);
    else {                                  // 找到待删结点
        if (!p->l) { TNode* t = p->r; delete p; return t; }
        if (!p->r) { TNode* t = p->l; delete p; return t; }
        TNode* suc = minNode(p->r);          // 中序后继
        p->v = suc->v; p->r = erase(p->r, suc->v);
    }
    return p;
}
void inorder(TNode* p) { if (!p) return; inorder(p->l); cout << p->v << " "; inorder(p->r); }

int main() {
    TNode* root = nullptr;
    for (int x : {5, 3, 7, 1, 9}) root = insert(root, x);
    root = erase(root, 3);
    inorder(root); cout << "\n";             // 1 5 7 9（删 3）
    return 0;
}

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

// 由前序 pre 与中序 in（长度 n）建树并返回根；用区间 [ps,pe]/[is,ie]
int preIdx = 0;
void build(const string& pre, const string& in, int is, int ie) {
    if (is > ie) return;                       // 空区间
    char root = pre[preIdx++];
    int mid = in.find(root);
    build(pre, in, is, mid - 1);               // 递归建左子树
    build(pre, in, mid + 1, ie);              // 递归建右子树
}

int main() {
    string pre = "ABC", in = "BAC";           // 前序 A B C，中序 B A C
    preIdx = 0; build(pre, in, 0, (int)in.size() - 1);   // 重建结构：A 的左 B、右 C
    cout << "重建完成（后序应为 B C A）\n";
    return 0;
}

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

void siftDown(vector<int>& a, int i, int n) {
    while (i * 2 <= n) {
        int j = i * 2;
        if (j + 1 <= n && a[j + 1] > a[j]) j++;   // 取较大子结点
        if (a[i] >= a[j]) break;
        swap(a[i], a[j]); i = j;
    }
}
void push(vector<int>& a, int x) {            // a[0] 不用，1-based
    a.push_back(x); int i = (int)a.size() - 1;
    while (i > 1 && a[i] > a[i / 2]) { swap(a[i], a[i / 2]); i /= 2; }  // 上浮
}

int main() {
    vector<int> a = {0};                      // 占位，1-based
    for (int x : {4, 2, 8, 5, 1}) push(a, x);
    for (int i = 1; i < (int)a.size(); ++i) cout << a[i] << " ";  // 堆结构（根 8）
    cout << "\n堆顶=" << a[1] << "\n";         // 8
    return 0;
}

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

int kthSmallest(vector<int>& a, int k) {
    priority_queue<int> pq;                   // 大根堆，维护最小的 k 个
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    cout << "第 3 小 = " << kthSmallest(a, 3) << "\n";   // 2
    return 0;
}

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

// 返回最小 WPL；权值集合 ws
int huffmanWPL(vector<int> ws) {
    priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆
    for (int w : ws) pq.push(w);
    int wpl = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int s = a + b; wpl += s; pq.push(s);
    }
    return wpl;
}

int main() {
    vector<int> ws = {5, 6, 2, 9, 7};
    cout << "哈夫曼 WPL = " << huffmanWPL(ws) << "\n";   // 65
    return 0;
}

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

struct DSU {
    vector<int> fa, rk;
    DSU(int n) : fa(n + 1), rk(n + 1, 0) { for (int i = 1; i <= n; ++i) fa[i] = i; }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }   // 路径压缩
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;               // 已连通
        if (rk[x] < rk[y]) swap(x, y);          // 按秩合并
        fa[y] = x; if (rk[x] == rk[y]) rk[x]++;
        return true;
    }
};

int main() {
    DSU dsu(5);
    dsu.unite(1, 2); dsu.unite(3, 4); dsu.unite(2, 3);
    cout << "1 与 4 连通? " << (dsu.find(1) == dsu.find(4) ? "是" : "否") << "\n";  // 是
    cout << "1 与 5 连通? " << (dsu.find(1) == dsu.find(5) ? "是" : "否") << "\n";  // 否
    return 0;
}

#include <iostream>
using namespace std;

int fa[1001];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    int n = 6, m = 3;                          // 6 点，3 条边
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int edges[3][2] = {{1,2},{2,3},{4,5}};
    int blocks = n;
    for (auto& e : edges) {
        int x = find(e[0]), y = find(e[1]);
        if (x != y) { fa[y] = x; --blocks; }
    }
    cout << "连通块数 = " << blocks << "\n";    // 3（{1,2,3},{4,5},{6}）
    return 0;
}

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

const int S = 26;
struct TrieNode { TrieNode* ch[S]; bool end; TrieNode() : end(false) { for (int i = 0; i < S; ++i) ch[i] = nullptr; } };

void insert(TrieNode* p, const string& s) {
    for (char c : s) {
        int i = c - 'a';
        if (!p->ch[i]) p->ch[i] = new TrieNode();
        p = p->ch[i];
    }
    p->end = true;
}
bool find(TrieNode* p, const string& s) {
    for (char c : s) { int i = c - 'a'; if (!p->ch[i]) return false; p = p->ch[i]; }
    return p->end;
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "abc"); insert(root, "abd");
    cout << "查 abc? " << (find(root, "abc") ? "是" : "否") << "\n";  // 是
    cout << "查 ab?  " << (find(root, "ab")  ? "是" : "否") << "\n";  // 否（非整词）
    return 0;
}

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

int main() {
    const int N = 5;
    // 邻接矩阵：无向边 (1,2,w=3)
    int g[N + 1][N + 1] = {0};
    g[1][2] = g[2][1] = 3;
    cout << "矩阵 g[1][2] = " << g[1][2] << "\n";          // 3

    // 邻接表：存 (到达点, 边权)
    vector<pair<int,int>> adj[N + 1];
    adj[1].push_back({2, 3}); adj[2].push_back({1, 3});
    cout << "邻接表 1 的第一条边 -> " << adj[1][0].first << " 权 " << adj[1][0].second << "\n";  // 2 权 3
    return 0;
}

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

vector<int> adj[6]; bool vis[6];
void dfs(int u) {
    vis[u] = true; cout << u << " ";
    for (int v : adj[u]) if (!vis[v]) dfs(v);
}

int main() {
    adj[1] = {2, 3}; adj[2] = {4}; adj[3] = {4};   // 无向
    adj[4] = {1, 2, 3};
    dfs(1); cout << "\n";                           // 一种 DFS 序：1 2 4 3
    return 0;
}

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

vector<int> adj[6]; int dist[6];
void bfs(int s) {
    for (int i = 0; i < 6; ++i) dist[i] = -1;
    queue<int> q; q.push(s); dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
}

int main() {
    adj[1] = {2, 3}; adj[2] = {4}; adj[3] = {4}; adj[4] = {1, 2, 3};
    bfs(1);
    cout << "1->4 最短距离 = " << dist[4] << "\n";    // 2
    return 0;
}

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

const int INF = 1e9;
int main() {
    int n = 5;
    vector<vector<pair<int,int>>> adj(n + 1);    // (to, w)
    adj[1] = {{2,1},{3,4}}; adj[2] = {{3,2},{4,7}};
    adj[3] = {{4,3},{5,2}}; adj[4] = {{5,5}};

    vector<int> d(n + 1, INF); d[1] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > d[u]) continue;                  // 过期堆顶
        for (auto [v, w] : adj[u])
            if (d[u] + w < d[v]) { d[v] = d[u] + w; pq.push({d[v], v}); }
    }
    for (int i = 1; i <= n; ++i) cout << d[i] << " ";   // 0 1 3 6 5
    cout << "\n";
    return 0;
}

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

int main() {
    const int N = 4, INF = 1e9;
    vector<vector<int>> d(N + 1, vector<int>(N + 1, INF));
    for (int i = 1; i <= N; ++i) d[i][i] = 0;
    // 边：1-2(3) 2-3(4) 3-4(5) 1-3(8) 2-4(9)
    d[1][2] = 3; d[2][3] = 4; d[3][4] = 5; d[1][3] = 8; d[2][4] = 9;
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
    cout << "1->4 最短路 = " << d[1][4] << "\n";   // 12（1-2-3-4）
    return 0;
}

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

struct Edge { int u, v, w; };
const int INF = 1e9;

int main() {
    int n = 4;
    vector<Edge> e = {{1,2,3},{2,3,-1},{3,4,2},{4,2,-4}};   // 含环 2-3-4-2 权 -3
    vector<int> d(n + 1, INF); d[1] = 0;
    bool neg = false;
    for (int i = 1; i <= n; ++i) {                  // n 轮（多一轮判负环）
        bool upd = false;
        for (auto& ed : e) {
            if (d[ed.u] != INF && d[ed.u] + ed.w < d[ed.v]) {
                d[ed.v] = (i == n) ? d[ed.v] : d[ed.u] + ed.w;   // 第 n 轮仍松弛→负环
                if (i == n) neg = true; upd = true;
            }
        }
        if (!upd) break;
    }
    cout << "存在负权环? " << (neg ? "是" : "否") << "\n";    // 是
    return 0;
}

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

struct Edge { int u, v, w; bool operator<(const Edge& o) const { return w < o.w; } };
int fa[1001];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    vector<Edge> e = {
        {1,2,4},{1,3,2},{1,4,3},{2,3,3},{2,5,6},
        {3,4,1},{3,5,4},{4,6,5},{5,6,7}
    };
    int n = 6; for (int i = 1; i <= n; ++i) fa[i] = i;
    sort(e.begin(), e.end());
    int mst = 0, cnt = 0;
    for (auto& ed : e) {
        int x = find(ed.u), y = find(ed.v);
        if (x != y) { fa[y] = x; mst += ed.w; ++cnt; }
    }
    cout << "MST 总权 = " << mst << " 边数 = " << cnt << "\n";   // 15, 5
    return 0;
}

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

const int INF = 1e9;
int main() {
    int n = 6;
    vector<vector<pair<int,int>>> adj(n + 1);     // (to, w)
    auto add = [&](int u, int v, int w){ adj[u].push_back({v,w}); adj[v].push_back({u,w}); };
    add(1,2,4); add(1,3,2); add(1,4,3); add(2,3,3); add(2,5,6);
    add(3,4,1); add(3,5,4); add(4,6,5); add(5,6,7);

    vector<int> d(n + 1, INF); d[1] = 0; vector<bool> vis(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1}); int mst = 0;
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (vis[u]) continue; vis[u] = true; mst += du;
        for (auto [v, w] : adj[u]) if (!vis[v] && w < d[v]) { d[v] = w; pq.push({w, v}); }
    }
    cout << "Prim MST 总权 = " << mst << "\n";      // 15
    return 0;
}

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

int main() {
    int n = 4;
    vector<int> adj[5]; int indeg[5] = {0};
    // 依赖：A(1)->B(2), A(1)->C(3), B(2)->D(4), C(3)->D(4)
    adj[1] = {2, 3}; adj[2] = {4}; adj[3] = {4};
    for (int u = 1; u <= n; ++u) for (int v : adj[u]) indeg[v]++;

    queue<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop(); topo.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    for (int x : topo) cout << x << " ";          // 一种拓扑序：1 2 3 4
    cout << "\n";
    return 0;
}