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

Question

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

Answer 1

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

我只需要补充一点,你达到关卡后不要继续开火.你只做一次.所以在2级你最多可以发射4个线程.每个traveral线程都将它的子树视为自己的root树.除非你有一些节点和一个合理平衡的树,否则你也不会这样做.Buttload是一个技术术语,意思是"衡量".UI线程遍历遍历分裂点的遍历部分.如果这是我的问题,我会长时间地思考我需要实现的目标,因为它可能会产生重大影响.

让我再添加一件事(这会成为Monty 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的索引移动到下一个条目).