在有效地处理树节点下的每个叶子

Question

简短版本： 在具有许多级别的儿童的树中（非二进制），其中每个节点可以有多个叶子，在给定节点的情况下达到某个条件的最佳方法是什么？

长，复杂的版本： 假设您有文件夹，可以包含更多文件夹。在生产中，我的系统最深处有大约15层文件夹。每个文件夹都可能有文档。

当用户导航到文件夹时，他们需要知道该文件夹中有多少个文档，总计。他们还需要知道这些文件中有多少已被“标记”。如果在某个时间段之后，可以将文档标记为未更新。这是基于历史条目确定的 - 采用文件夹的最后一个历史条目，如果它大于X，则标记为标记。

现在我迭代所有文件夹>子文件夹>等>儿童，以检查历史记录条目和递归。这现在变得非常慢，所以我需要一种新的方法。

我想出了两个选项，但想知道是否有更好的方法，或者其中一个是最好的。

选项1 ：每当添加文档或删除文档时，遍历父图和递增/递减存储在文件夹实体中的“documentcount”属性。这意味着添加/删除采取最小的绩效命中。但这里的问题在于我实际上需要计算文件总数，以及标记的文档总数（通过检查历史记录条目），这样它就意味着我需要另一个字段和另一个进程在此时调用状态更改。这介绍了更复杂，因为检查是否标记了某些东西是一种方法调用，而不是属性。

选项2：有一个定时器作业运行并更新系统中每个文件夹的“未开放的documentcount”属性，将是大量的CPU周期，似乎是浪费的。

选项3 ：刚才想到这一点 - 也许迭代每个文档，并在评估之前迭代该文档是目标节点的直接或远处的子节点，比通过递归迭代更好。我觉得这对树的节点更好，但是在树中的每个孩子迭代低级节点会很荒谬。 HMMM ...

我很想实施选项1 ..有什么其他选择？

Answer 1

如果您知道将节点添加到树中的条件，则可以设计添加例程以通过树重复，而不是踩下，然后放松递归和更新父节点中的概率。

同样，在更新节点时，您将重复到它们，然后再次退影并更新父母。

如果您预先不知道条件，则拧紧。你别无选择，只能以任何顺序遍历树是有意义的。从你所说的话，听起来好像你在节点在节点做什么都是左边和右子的任何函数，这使得职业翻译是正确的答案。

注意：如果上面对您没有意义，请阅读 Knuth卷。1