遍历一个无序的二叉树

Question

我有一种情况，我需要以并行方式访问树。 这怎么可能？没有递归，我无法想象树中的任何事情。

Answer 1

不知道你是否仍然在寻找答案，但我认为其他人可能会受益。

您仍然可以使用递归，但需要锁定树的分支并允许其他线程'跳过'这些分支，因为它们已经（或已经）已经被处理。

例如，假设您正在处理树进行广度优先遍历，因此在遍历当前节点的子节点的递归方法的每次运行中都如此。每个线程都必须遍历当前节点的子节点，并尝试锁定每个子节点，如果它已被锁定，则跳过它。

我不确定你使用的是什么树实现，所以你应该把下面的代码中的'Node'对象当作伪代码来处理，但其余部分是正确的Java。

在下面的示例中，选择预定深度以应用锁定 - 这确保线程不会简单地锁定在树的根部并串行访问整个树。

选择正确的深度将取决于您特定树的形状。例如，如果它是一棵二叉树，那么你的树可能在深度3有多达8个分支，这对于一些线程来说很可能是正常的，但如果你正在运行20个线程，你需要选择一个序列化点降低深度以确保所有线程都能够处理某个分支。

您也可以使用其他一些方法来决定何时锁定（例如，如果节点可以有效地报告它有多少叶节点可以设置阈值），重要的是所有线程都使用相同的方法用于决定锁定还是不锁定的代码。

Object master_LOCK = new Object(); 
HashMap locks = new HashMap(); 
int DEPTH = 5; 

public boolean lockNode(Object nodeID) { 
    synchronized(master_LOCK) { 
     Object node_LOCK = (Object)locks.get(nodeID); 
     if (node_LOCK == null) { 
      //we can lock this node 
      locks.put(nodeID,new Object()); 
      return true; 
     } else { 
      //node already locked 
      return false; 
     } 
    } 
} 

public void traverseBreadhFirst(Node node) {  
    locks.clear(); 
    traverseBreadthFirst(node,0); 
} 

public void traverseBreadthFirst(Node node, int currentDepth) { 
    currentDepth++; 

    //Process the current node here 


    //Iterate through children, locking to force serialised access only at a predetermined depth 
    List children = node.getChildren(); 

    for (int i = 0; i < children.size(); i++) { 

     Node child = (Node)children.get(i); 

     //If we are a certain depth in the tree we start serialising access from that point on 
     //This ensures that there are enough branches at this point to roughly evenly distribute them 
     //to all available threads. 

     if (currentDepth < DEPTH) { 
      //All threads are to go to depth N 
      traverseBreadthFirst(node,currentDepth); 

     } else if (currentDepth == DEPTH) { 
      //At depth N we lock all branches we intend to process 
      if (lockNode(child.getID())) { 
       //We have locked this child node so we should process it 
       traverseBreadthFirst(node,currentDepth); 
      } else { 
       //This child has been locked for processing already so we skip it 
      } 

     } else { 
      //We are deeper than depth N so we can traverse our locked branch without locking further 
      traverseBreadthFirst(node,currentDepth); 

     } 
    } 

}