搜索未排序二叉树

两个字符串我需要从字符串的二叉树显示不同节点的“路径”。该函数接收两个节点（开始和结束），假设它们存在于树中。该树不是有序的，不能订购。我一直在使用预订策略。搜索未排序二叉树

例如，如果输入的是周一和月份的结果应该是：

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); 
    } 
}

来源

2016-03-01 curry_30

你能只向下遍历树，或者你可以通过父母以及（如从周一到狮子）？ – callyalater

好的。然后，我会觉得这个问题是有向图，并使用[Dijkstra算法（https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）或[克鲁斯卡的（https://en.wikipedia.org/wiki/Kruskal％27s_algorithm）来遍历它。 – callyalater

首先，你不能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

来源

2016-03-01 18:37:53 radoh

@gpasch为什么两个孩子都会加入'visited'？我以不正确的路径移除孩子。如果已经有一个孩子在正确的道路上，我不检查另一个孩子。 – radoh

Double等于（'=='）总会让我在Java中进行比较时感到害怕。你认为调用equals（）方法会更好吗？ – callyalater

@callyalater没有，因为那正是** **我想要的东西 - 检查，如果情况是相同的。当然，这取决于OP如何使用功能 - 如果他创造NodeArbre'的'一个新的实例，并认为它们是当他们的'_contingut'字段相等相等，那么这将是比较这些区域，而不是一个好主意。 – radoh

搜索未排序二叉树

回答

相关问题