202504252122 树的代码表示

邻接表表示法 无权

// 邻接表（适用于一般树和图）
const int MAXN = 1e5 + 5;
vector<vector<int>> family(MAXN);  // 存储每个节点的子节点
 
// 添加边
void addEdge(int u, int v) {
    adj[u].push_back(v);
    // 如果是无向图/树，还需要:
    // adj[v].push_back(u);
}

链式向前星 带权

// 链式前向星（常用于有权树/图）
struct Edge {
    int to, weight, next;
} edges[MAXN * 2];  // 对于树，边数为n-1，但通常预留更多空间
 
int head[MAXN], tot = 0;
 
void addEdge(int u, int v, int w) {
    edges[tot].to = v;
    edges[tot].weight = w;
    edges[tot].next = head[u];
    head[u] = tot++;
}

数组表示 适合堆和完全二叉树

// 堆的数组表示
const int MAXN = 1e5 + 5;
int heap[MAXN];
int heapSize = 0;
 
// 获取相关节点的索引
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }