有效地找到深标志着树节点的孩子

 A 
    /\ 
     B C 
    /\ \ 
    D* E* F 
/\ \ \ 
    G H* I J*

与所述标记节点d *，E * H *和J *，是去取回的快捷方式全部在给定节点下标记的孩子，除了走遍所有子树或为每个节点存储所有标记的孩子？即：

B -> D*, E*, H* 
C -> J* 
A -> D*, E*, H*, J*

有很多不同的方式来存储中间结果以加快速度，但没有更多的上下文，很难说什么会有帮助。 – trutheality 2012-02-27 00:45:46

@PhilBolduc请确保您在发布之前思考 - 谢谢。 – 2012-02-27 00:55:45

@trutheality我需要一些用户界面的工作;基本上，只要父母的大小发生变化，子窗口小部件就必须能够接收调整大小的事件 - 即，如果窗口被调整大小，一些深埋文本框必须接收调整大小事件，但是没有中间窗口小部件。 – 2012-02-27 00:58:33

原则上，您在树的行走和存储标记值的列表之间进行权衡。你提到了两个极端，下面我会给你一个例子，它们位于它们中间的某个地方。

想到的一个想法是在每个标记的节点上存储标记的孩子的下一个“层”，这应该在存储和时间之间给出一个相当平衡的混合，所以在你的例子中它不会节省很多，但对于例如，如果你有

 A 
    /\ 
     B* C 
    /\ \ 
    D* E F 
/\ \ \ 
    G H* I* J* 
//\ 
K L M

你会在D和“空”的标记存储在BD,I和H在H,I,J。

要获取列表，你只需要步行，直到每一个分支命中一个显着的节点，因此，例如，以获取列表为A一个节点，你就必须从A->B和A->C->F->J走，然后B会给你I,D，D会给你H。

你也可以把它当做只是一起存储标节点的树木与原树，在这种情况下，两棵树

B  J 
/\ 
D I 
| 
H

根据标节点的分布，你也许能够为您的应用程序优化这个想法。

2012-02-27 01:21:49 trutheality

这听起来像个好主意，谢谢！ – 2012-02-27 10:02:56

那么你必须走的树至少一次。没有比这更快的方法。你不想存储它们，所以你必须每次都重新走一遍。

2012-02-27 01:10:17 user1227804

嗯，我可以保存它们，我只是不想存储所有标记的列表每个子节点中的子节点（并且它必须是*每个*节点）。如果有一种有效的方式来存储它们 - 我完全赞成。 – 2012-02-27 01:18:07

如果你自下而上，你可以访问树的更小的部分。

该算法可以工作以最小空间表示的树：即只是一个结构向量，除“父节点”索引和“标记的标志”（根为-1）以外的完整有效载荷。

for each node 
    if marked && given parent in parents'chain 
    ok, save (for instance) the index 
    endif 
next

国际海事组织，并根据数据分布统计，我觉得这可能是有效的。

2012-02-27 01:41:26 CapelliC

可以存储在每一个为1（true）节点的一个位（或boolean）当且仅当存在扎根于当前节点的子树的显着节点。这个标签在更新树时很容易维护，并允许您在递归和迭代算法中轻松地跳过无趣的子树。不过，您必须遍历路径上的所有节点才能标记节点。

确保访问零开销但更难维护的另一个想法是：让每个标记的节点都有第二对子指针。有了这些，您可以存储标记节点的树，而只需很少的存储开销。你甚至可以用这种方法对标记进行编码;当且仅当至少一个指针不是null时，节点才被标记。根必须以特殊的方式处理。

2012-02-27 17:47:56 Raphael

我喜欢国旗的想法，但问题是，你仍然必须遍历大量中间无标记的节点。但是你的第二个建议（如果我理解正确，这基本上与真理的想法基本相同）实际上使得标志不必要，并且是我要做的事情:) – 2012-02-28 00:09:04

@PhilipK第一个引入太多开销真的取决于你的情况，即你有多少标签相对。我不完全明白什么是真实性。 – Raphael 2012-02-28 06:30:58

回答