实现树形数据结构有哪些可选方案？各方案优缺点是什么？

基于指针的递归实现 #

优点 #

• 逻辑完全贴合树的递归定义，理解成本低，节点增删、子树遍历的代码写起来非常直观
• 节点所有权清晰，std::unique_ptr自动管理生命周期，删除节点时子节点会自动同步释放，不会出现内存泄漏
• 不需要维护额外的全局关联结构，单个节点的操作完全独立，不会影响其他节点

缺点 #

• 所有节点分散在堆上，内存布局不连续，缓存命中率极低，遍历大规模树时性能差距能达到几十倍
• 深拷贝成本极高，必须递归遍历整棵子树才能完成复制
• 序列化/反序列化难度大，必须先把指针关系转换为索引才能持久化，读取时还要重建指针关联
• 无法通过下标随机访问节点，查找特定节点必须遍历整棵树
• 递归遍历深度过大的树时容易触发栈溢出，必须额外实现迭代式遍历，增加开发成本

基于节点对的邻接表实现 #

优点 #

• 所有数据存储在连续的vector中，内存布局友好，遍历性能远高于指针方案
• 拷贝、序列化操作极其简单，直接对两个vector做操作即可，不需要处理复杂的指针关系
• 支持通过下标随机访问任意节点，不需要遍历就能定位目标节点
• 批量新增节点/连接时性能极高，直接往vector尾部插入即可

缺点 #

• 操作逻辑不够直观，每次修改树结构都要同时维护数据数组和连接数组，很容易出现二者不一致的bug
• 删除节点成本极高，要么需要调整后续所有节点的索引，要么要额外实现墓碑标记逻辑，都会增加复杂度和运行开销
• 需要自行保证连接中的索引都是合法值，很容易出现悬垂索引的问题
• 查找某个节点的子节点时，必须遍历整个连接列表匹配父节点索引，性能极低，除非额外为每个节点维护子节点索引列表，反而会额外增加内存开销

你的要求是每个节点支持多子节点、具备可选数据字段，除了上述两种，还有以下常见的实现方案：

1. 父索引数组实现 #

每个节点除了可选数据外，仅存储自身父节点的索引，适合经常需要向上查找父节点的场景：

struct Node {
    std::unique_ptr<T> data = nullptr;
    size_t parent_idx = static_cast<size_t>(-1); // 根节点的父索引设为无效值
};
struct Tree {
    std::vector<Node> nodes;
};

这种方案内存开销极小，仅用一个字段就能维护整棵树的结构，适合节点数量极多、对内存占用敏感的场景。

2. 左孩子右兄弟链式实现 #

每个节点仅存储第一个子节点和下一个兄弟节点的指针，不需要为每个节点单独维护子节点vector，大幅节省内存开销：

struct Node {
    std::unique_ptr<T> data = nullptr;
    std::unique_ptr<Node> first_child = nullptr;
    std::unique_ptr<Node> next_sibling = nullptr;
};

遍历子节点时从first_child开始，顺着next_sibling指针遍历即可，非常适合单个节点子节点数量极多的场景。

3. 连续存储索引式实现 #

综合了前两种方案的优势，是当前工业界最常用的实现方式：所有节点存储在连续的vector中，每个节点单独存储自身子节点的索引列表：

struct Node {
    std::unique_ptr<T> data = nullptr;
    std::vector<size_t> child_indices;
};
struct Tree {
    std::vector<Node> nodes;
    size_t root_idx = 0;
};

既保留了连续内存的高性能优势，又不需要维护全局的连接列表，查找子节点直接读取当前节点的child_indices即可，操作逻辑也非常直观。

内容的提问来源于stack exchange，提问作者jan.sende