遍历带有重复子树的树

Question

我有一棵树，用简单的递归后序遍历打印出所有可能的路径。但问题在于这需要很长时间。

我想利用我树的一个特性来节省遍历时间。这个特性是我有重复的子树，在下面的例子中，头结点为1的子树在树中出现了3次。

          10
  /        |        \
 5         15        1
 /\        / \      / \
2  1      1   6    3   8
  / \    / \
 3   8  3   8

我希望改进我的遍历算法来跳过已经遍历过的子树。我的想法是要记录下已经遍历过的每一个子树，但我不知道怎样将其运用到后序遍历算法中。

谢谢您的帮助。

- Kfozli

---

想一想，当你遍历树的时候，如何在不遍历子树的情况下知道一个子树是否已经出现过？因此，尝试重新组织你的树，并在重复的子树上做标记。这可能会有所帮助。 - Shindou

节点ID是否总是与相同的子树相关联？例如，如果您看到ID为1的节点，您可以确定它始终代表相同的子树（1、3、8）吗？在这种情况下，我会构建一个所有遍历过的节点id的哈希表。对于您即将检查的每个节点，我首先会询问哈希表是否已经看到该节点，因此可以跳过它以及其整个子树。 - nv3

是的，每个节点ID都与一个子树相关联。我尝试了你的想法，但由于我必须打印树中的所有路径，我不知道如何将已经在该子树中的路径与算法相匹配。 - Kfozli

你似乎实际上有一个DAG，而不是一棵树。因此，您需要通过添加数据结构来跟踪已访问的节点，将您的树遍历更改为完整的DFS。 - gen-y-s

Answer 1

使用哈希集合来存储已访问过的节点，并对每个访问的节点进行检查，如果尚未被访问，则将其添加到已访问的集合中，并按照通常方式继续操作，否则返回。

- gen-y-s

---

但是这假设如果你遇到一个与已经遇到的根节点相同的根节点，你应该返回。实际上，问题的提出者想要的是整个子树与已经遍历过的子树完全相同。考虑这样一种情况，根节点为1，左节点为2，右节点为3。你遍历了这棵树，然后稍后你遇到了一个子树，其中根节点为1，左节点为2，右节点为4。按照你的建议，算法在第二次遇到1后应该跳过后面的子树，但实际上不应该这样做，因为右节点为4而不是3，所以这两个子树是不同的。 - AndyG

@NiklasB。谢谢，我没看到那个评论。在这种情况下，我撤回我之前的评论。 - AndyG

Answer 2

我不知道你的程序是否允许这种更改...由于在遍历时我们无法知道子树是否已经出现过，一种可能的方法是重新组织你的树，以共享重复的子树。

          10
  /        |        \
 5         15        1
 /\        / \      / \
2  1 ------   6    3   8
  / \     
 3   8     

- Shindou

---

你说的“share”是什么意思？请注意，子树（1,3,8）在示例中出现了3次。 - Kfozli

如果出现3个相同的子树(1, 3, 8)出现3次，通过共享只保留一个子树的副本，然后让节点5、10...指向该副本。 - Shindou

@Adrian 是的，这可能会导致循环。但我认为这并不重要...毕竟必须有一种方法来知道子树是否已被访问过。 - Shindou

有方法，只是不是这种方式。这种方式会将我们的树转换为图形，这可能不是我们想要的。最好的方法是使用哈希表来存储已访问的节点，如上所述。 - Adrian Buzea

但是这样做不仅可以节省存储空间，还可以节省编程工作。 - Shindou

Answer 3

我认为这是主要问题。您的程序运行时间与输出数据量成线性关系，每一步在树中执行时，程序至少应该输出一个符号。因此，只要您保持所需的输出相同（即只要您需要输出所有路径），就没有速度提升的余地，您无法获得比 O(R) 更快的算法，其中 R 是您需要生成的总输出大小。

实际上，最可能的瓶颈是输出本身（控制台或磁盘性能通常比仅在内存中遍历差得多），因此我认为如果您对程序进行分析，您会发现90%的时间都花费在输出上。因此，您不仅无法获得更好的渐近解决方案，而且根本无法获得更快的解决方案。（除非您优化输出本身，但那是另一个问题。）

然而，如果您不需要打印所有路径，而是以某种方式处理它们 - 例如计算存在多少条路径或查找最长路径等 - 那么您的解决方案可以从具有重复子树的事实中获得巨大好处。实际上，这意味着您没有一个树，而是一个有向无环图，这通常允许使用相当简单的动态规划方法。

- Petr

---

你假设他在遍历时不进行任何计算，但这可能并不正确。 - avim

@avim，我猜这应该是相当沉重的计算，以超过输出为代价。无论如何，这不会导致渐近更好的解决方案；此外，如果是这种情况，那么OP肯定应该在问题中提到这一点，因为问题将不是“如何优化遍历”，而是“如何优化计算”。 - Petr

@Petr 即使不打印结果，它也需要很长时间。看起来可以节省一些时间，因为如果我已经访问了特定子树并访问了所有子路径，那么我就不应该再次执行它。 - Kfozli

@Kfozli，即使您删除输出（但仅限输出），它仍将是O(R)，其中R是所有路径的总长度，因为您仍然必须遍历每个路径。 “如果我已经在特定子树中访问过并且在其所有子路径中都访问过，则不应再次执行” --- 然后您不会打印或枚举所有可能的路径，因为您留下了其中一些。 - Petr

Answer 4

假设每个节点表示一个唯一的以该节点为根的子树，并且节点值集不是很大，您可以使用此方法来优化遍历：

string s[MAX_NODE_VALUE + 1];

string post_traverse(Node root)
{
    if(root == NULL)
        return "";
    if(s[root.value].length() == 0)
    {
        s[root.value] += post_traverse(root.left);
        s[root.value] += post_traverse(root.right);
        s[root.value] += itoa(root.value);
        s[root.value] += ' ';
    }
    cout << s[root.value];
    return s[root.value];
}

只有在您有太多重复的子树且节点值集非常小的情况下，这才会有所帮助，否则它将占用过多的空间并需要更长的时间。

- Milan Patel