10 树与二叉树

#include <iostream>
using namespace std;
const int N = 1005;
// 数组存法（适合完全二叉树）：根在下标 1，左孩子 2*i，右孩子 2*i+1
int treeArr[N];

// 结构体/动态存法（一般二叉树，支持任意形态）
struct Node {
    int data;
    Node *left, *right;                     // 左右孩子指针
    Node(int d) : data(d), left(nullptr), right(nullptr) {}  // 构造
};

int main() {
    // 数组存法示例：根为 treeArr[1]，其左孩子 2、右孩子 3
    treeArr[1] = 10;
    treeArr[2] = 20;
    treeArr[3] = 30;
    cout << "根" << treeArr[1] << " 左" << treeArr[2] << " 右" << treeArr[3] << endl;
    return 0;
}

#include <iostream>
using namespace std;

struct Node { int data; Node *left, *right; };
// 以数组下标法演示，left_[u] = -1 表示 u 没有左孩子
int left_[10], right_[10];   // 存左右孩子下标

// 先序遍历：根 - 左 - 右
void pre(int u) {
    if (u == -1) return;          // 空节点返回
    cout << u << " ";             // 1) 访问根
    pre(left_[u]);                // 2) 遍历左子树
    pre(right_[u]);               // 3) 遍历右子树
}
// 中序遍历：左 - 根 - 右
void in(int u) {
    if (u == -1) return;
    in(left_[u]);                 // 1) 左子树
    cout << u << " ";             // 2) 根
    in(right_[u]);                // 3) 右子树
}
// 后序遍历：左 - 右 - 根
void post(int u) {
    if (u == -1) return;
    post(left_[u]);               // 1) 左子树
    post(right_[u]);              // 2) 右子树
    cout << u << " ";             // 3) 根
}
// 层序遍历：用队列逐层扫描（BFS 思想）
#include <queue>
void level(int root) {
    queue<int> q;
    q.push(root);                 // 根先入队
    while (!q.empty()) {
        int u = q.front(); q.pop();   // 取队首节点
        cout << u << " ";
        if (left_[u] != -1) q.push(left_[u]);    // 左孩子入队
        if (right_[u] != -1) q.push(right_[u]);  // 右孩子入队
    }
}

int main() {
    // 建一棵树：1 的左孩子 2，右孩子 3；2 的左孩子 4
    left_[1] = 2; right_[1] = 3;
    left_[2] = 4; right_[2] = -1;
    left_[3] = -1; right_[3] = -1;
    left_[4] = -1; right_[4] = -1;
    cout << "先序: "; pre(1); cout << endl;
    cout << "中序: "; in(1); cout << endl;
    cout << "后序: "; post(1); cout << endl;
    cout << "层序: "; level(1); cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
vector<int> children[N];      // 邻接表存树：children[u] 存 u 的所有子节点

void dfs(int u) {             // 树的深度优先遍历（前序）
    cout << u << " ";         // 访问当前节点
    for (int v : children[u]) dfs(v);   // 依次递归每个孩子
}

int main() {
    children[1] = {2, 3};     // 1 的孩子是 2、3
    children[2] = {4, 5};     // 2 的孩子是 4、5
    dfs(1);                   // 从根 1 开始
    cout << endl;
    return 0;
}

int depth[N];                          // 记录每个节点的深度
// 求深度：父节点深度 + 1 传给子节点
void dfsDepth(int u, int d) {
    depth[u] = d;                      // 当前节点深度
    for (int v : children[u]) dfsDepth(v, d + 1);   // 孩子深度 +1
}

#include <iostream>
using namespace std;
const int N = 100005;
int fa[N];                              // fa[i] 记录 i 的父节点（并查集）
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }  // 各自成集合
int find(int x) {            // 找根 + 路径压缩（沿途节点直接指向根）
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b) {   // 合并两个集合
    int ra = find(a), rb = find(b);    // 找各自的根
    if (ra != rb) fa[ra] = rb;         // 不同根才合并
}
int main() {
    init(6);                 // 初始化 1~6 各自独立
    merge(1, 2);             // 1、2 合并
    merge(2, 3);             // 2、3 合并 → 1、2、3 同组
    cout << find(1) << " " << find(3) << endl;   // 同组根相同
    cout << (find(1) == find(3)) << endl;        // 1
    return 0;
}