我有一个二叉树,其中每个节点的值为0或1,从根节点到叶节点的每个路径表示一个特定长度的二进制字符串。程序的目的是找到所有可能的二进制字符串(即从根到叶的所有可能路径)。现在我想把它并行化,这样它就可以使用多个核。我假设我需要以某种方式在分支节点上分配工作负载,但是我不知道从哪里开始。我正在研究forkjoin功能,但是我不知道如何分割工作,然后合并它。
public class Tree{
Node root;
int levels;
Tree(int v){
root = new Node(v);
levels = 1;
}
Tree(){
root = null;
levels = 0;
}
public static void main(String[] args){
Tree tree = new Tree(0);
populate(tree, tree.root, tree.levels);
tree.printPaths(tree.root);
}
public static void populate(Tree t, Node n, int levels){
levels++;
if(levels >6){
n.left = null;
n.right = null;
}
else{
t.levels = levels;
n.left = new Node(0);
n.right = new Node(1);
populate(t, n.left, levels);
populate(t, n.right, levels);
}
}
void printPaths(Node node)
{
int path[] = new int[1000];
printPathsRecur(node, path, 0);
}
void printPathsRecur(Node node, int path[], int pathLen)
{
if (node == null)
return;
/* append this node to the path array */
path[pathLen] = node.value;
pathLen++;
/* it's a leaf, so print the path that led to here */
if (node.left == null && node.right == null)
printArray(path, pathLen);
else
{
/* otherwise try both subtrees */
printPathsRecur(node.left, path, pathLen);
printPathsRecur(node.right, path, pathLen);
}
}
/* Utility function that prints out an array on a line. */
void printArray(int ints[], int len)
{
int i;
for (i = 0; i < len; i++)
{
System.out.print(ints[i] + " ");
}
System.out.println("");
}
}
1条答案
按热度按时间t98cgbkg1#
您可以使用线程池在不同的线程之间有效地分配负载。
一种可能的方法:
但是,这种方法不再是深度优先搜索,因为在搜索第一个分支之前,您会列出您所在位置的分支。在我的理解中,dfs是一种严格的线性方法,因此不能完全并行(尽管可以在评论中纠正我)。