在未排序的二叉树中搜索两个字符串

Question

我需要从字符串的二叉树中显示不同节点的"路径"。该函数接收两个节点（开始和结束），假设它们存在于树中。树未排序，也无法排序。我已经使用预购策略了。

例如，如果输入是星期一和月份，则结果应为：

monday party of month

使用预购，结果是

monday party of friday month

有谁知道打印正确的路径？

        family 
      /         
    day        monday 
   /          /    
  zoo  night  party  brother
 /    /     /     /   
lion        of   at      club
            /  
        friday  month
public void fa(NodeArbre inicial,NodeArbre fi){
    if(inicial!=null){
        System.out.println(inicial._contingut+ " _ ");
        fa(inicial._esq,fi);
        fa(inicial._dret,fi);
    }
}

Answer 1

首先，您无法println当前节点，因为您不知道它是否在正确的路径上。这意味着您应该将访问过的节点收集到list中，并在到达目标节点后打印出来。

此外，我非常怀疑您显示的输出是由您的程序生成的 - 您的程序不检查目标节点，它遍历整个子子树。

您可以通过定义一个辅助递归函数来实现这一点，该函数需要一个额外的参数 - list访问的节点。例如：

public boolean fa(NodeArbre inicial, NodeArbre fi, List<NodeArbre> visited) {
  if (inicial == null)
    return false;
  visited.add(inicial);
  if (inicial == fi || inicial.contingut.equals(fi.contingut)) { // depends on how you want to determine node equality  
    // print list of visited?
    return true;
  }
  if (fa(inicial._esq, fi, visited))
    return true;
  else if (fa(inicial._dret, fi, visited))
    return true;
  visited.remove(inicial);
  return false;
}

您将从原始方法调用fa

public void fa(NodeArbre inicial, NodeArbre fi) {
  // assign the list to a variable if you want to do something with it...
  // fa will return true if it found the path
  fa(inicial, fi, new LinkedList());
}

注意：我假设_esq指向左子项，_dret指向右子项，反之亦然。

对于非信徒 - 我已经测试过它：http://ideone.com/U1sI7t