Ale*_*kiy 1 algorithm data-structures
这是对相当神秘的标题问题的重述:
假设我们已经构建了一个Prototype树,它包含树结构的所有信息以及每个节点的通用描述.现在,我们要使用包含额外唯一数据的元素创建此树的实例.我们称之为混凝土树.
唯一的区别混凝土和原型树在的节点的额外数据混凝土树.假设Concrete树的每个节点都有一个指向原型树中相应元素的指针/链接,以获取有关该节点的一般信息,但没有自己的父/子信息:
是否可以遍历混凝土树？
特别是,给定Concrete树中的起始节点和通过Prototype树的路径,是否可以有效地获取Concrete树中的相应节点？可能有许多 Concrete树,因此无法从Prototype树返回链接.
即使我可能不需要在我的代码中对事物进行优化,但这仍然是一个有趣的问题!
提前致谢!
注意:树的分支因子没有限制 - 节点可以有一到几百个子节点.
额外的ramblings /想法:
我问的原因是,每次创建Concrete树的新实例时,复制父/子信息似乎都是浪费,因为这个结构与Prototype树相同.在我的特定情况下,子项由字符串名称标识,因此我必须在每个节点存储字符串到指针的哈希.可能有很多 Concrete树的实例,重复这个哈希似乎是一个巨大的空间浪费.
作为第一个想法,也许路径可能以某种方式融入一个int或者紧凑地标识一个元素的东西(不是一个字符串,因为它太大了),然后用它来查找每个Concrete树的哈希中的具体元素？
一旦创建,原型树是否会改变(即节点是否会被插入或移除)？
如果没有,您可以考虑阵列支持的树(即子/父链接由数组索引表示,而不是原始指针),并为您的具体树使用一致的索引.这样,从具体到原型的映射是微不足道的,反之亦然.