algorithm - 使用树遍历具有相同父/子关系的一组单独的元素

Question

这里是对相当神秘的标题问题的重述:

假设我们有一个已经构建的原型(prototype)树，它包含关于树结构的所有信息和每个节点的通用描述。现在我们要用包含额外唯一数据的元素创建这棵树的实例。我们称这些为混凝土树。

具体 和原型(prototype) 树之间的唯一区别是具体 树节点中的额外数据。假设 Concrete 树的每个节点都有一个指针/链接到 Prototype 树中的相应元素以获取有关节点的一般信息，但没有自己的父/子信息:

是否可以遍历 Concrete 树？

特别是，给定具体树中的起始节点，以及通过原型(prototype)树的路径，是否有可能有效地获取具体树中的相应节点？可以有很多具体树，所以从原型(prototype)树返回的链接是不可能的。

即使我可能不需要在我的代码中优化到这种程度，但这仍然是一个有趣的问题!

提前致谢!

注意:对树的分支因子没有限制 - 一个节点可以有一个到数百个子节点。

---

额外的杂谈/想法:

我问的原因是，每次创建具体树的新实例时复制父/子信息似乎是一种浪费，因为这种结构与原型(prototype)树相同。在我的特殊情况下，子节点由字符串名称标识，因此我必须在每个节点存储一个字符串到指针的哈希值。可以有许多具体树的实例，复制这个散列似乎是对空间的巨大浪费。

作为第一个想法，也许路径可以以某种方式散列为 int 或紧凑地标识元素的东西(不是字符串，因为它太大)，然后用于在散列中查找每个具体元素的具体元素树？

Answer 1

一旦创建，原型(prototype)树是否会改变(即是否会插入或删除节点)？

如果不是，您可以考虑数组支持的树(即子/父链接由数组索引表示，而不是原始指针)，并为您的具体树使用一致的索引。这样，从具体到原型(prototype)的映射就很简单了，反之亦然。