c++ - 如何以线程安全的方式遍历二叉树？

Question

我需要一种方法来遍历二叉树，使用多个线程并将符合条件的元素存储到列表中。 我该如何以线程安全的方式做到这一点？

Answer 1

正如 SDG 指出的那样，答案在很大程度上取决于问题的确切性质。如果你想分解遍历(即并行遍历)，那么你可以让线程在 2 级之后作用于不同的子树。然后每个线程可以附加到它自己的列表，然后可以在连接点合并/连接.最简单的做法是在进行遍历时防止对树进行修改。

我只需要补充一点，您不会在达到您的级别后继续触发线程。你只做一次。所以在第 2 级你最多触发 4 个线程。每个遍历线程都将其子树视为自己的根树。除非您有大量节点和合理平衡的树，否则您也不会这样做。 Buttload 是一个技术术语，意思是“测量”。遍历到 split 点的部分由UI线程遍历。如果这是我的问题，我会认真思考我需要实现的目标，因为它可能会产生重大影响。

让我再补充一件事(这会变成 M​​onty Python 素描吗？)。如果您只需要处理结果，您实际上并不需要将结果列表连接或合并到一个新列表中。即使您需要排序的结果，最好还是单独对每个列表进行排序(可能并行)，然后以 GetNextItem 拉式方式“合并”它们。这样你就不需要太多额外的内存。您可以通过具有两个“缓冲区”(可以是指向实际条目的指针/索引)以这种方式一次合并 4 个列表。我正在尝试找到一种无需绘制图片即可对其进行解释的方法。

                     0 1 2 3 4 5 6 7 8 9   

             L1(0):  4 4 4 5 5 6 8 
    B1[L2,3]        \  
             L2[1]:  3 4 5 5 6 7 7 8 9
 \   
             L3[1]:  2 2 4 4 5 5 6 8 
    B2[L3,2]          /
             L4[0]:  2 4 5 5 6 7 7 8 9

您不断从满足您需要的顺序的列表中拉取。如果你从 B2 中拉取，那么你只需要更新 B2 及其子列表(在这种情况下，我们从 L3 中拉取 2，并将 L3 的索引移动到下一个条目)。