使用树遍历具有相同父/子关系的单独元素集

Question

这里重述了一个相当神秘的标题问题：

假设我们已经构建了一个原型树，它包含了关于树的结构的所有信息以及每个节点的一般描述。现在，我们希望使用包含额外唯一数据的元素来创建此树的实例。我们把这些混凝土树叫做。

混凝土树和原型树的唯一区别是混凝土树节点中的额外数据。假设具体树的每个节点都有指向原型树中相应元素的指针/链接，以获取有关该节点的通用信息，但没有自己的父/子信息：

有可能穿过这棵混凝土树吗？

特别是，给定具体树中的起始节点和通过原型树的路径，是否有可能有效地在具体树中得到相应的节点？可能有很多混凝土树，所以从原型树返回链接是不可能的。

尽管我可能不需要在代码中对事情进行如此程度的优化，但这仍然是一个有趣的问题！

提前感谢！

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

额外的胡言乱语/想法：

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

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

Answer 1

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

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

Answer 2

您可以为每个原型节点提供一个具体的叶子，但是您需要对每棵树进行某种散列(如您所建议的那样)，以使不同的具体树保持独立。此时，您的存储成本与一个完全独立的具有冗余子/父指针的树相同。你肯定想要一个从原型树到混凝土树的链接。

如果您想要对原型树进行结构更改，影响所有链接的具体树，我可以看到这种方法是有用的。移动节点会立即影响所有的混凝土树。您可能会产生额外的成本，因为如果不发送每个具体树或执行一些extract操作来删除一棵树，就不可能传输单个具体树。

通常，您将无法在int中唯一地编码路径。

Answer 3

只需将父-子关系存储在具体的树中，然后忘记它。最好是一个指针值，最坏的是两个指针值。无论如何，您至少需要这么多才能在原型树和具体树之间保持链接。