寻找n元树

Question

的最大I具有由短NTN类的

public class NTN P { 
    public int value; 
    public Set<NTN> children; 
} 

我要找到最大的这样一个n元树的定义的N叉树。假设它是一个简单的整数n元树，值为：[parent：1 children：2,3,4] [parent：2 children：5,6] [parent：4 children 7，8，9]仅仅是9.我不知道如何开始编写一个方法来寻找与原型最大：

public static int maximum(NTN t); 

从我已经试过：

public static int maximum(NTN t) { 
    int max = 0; 
     for (NTN e : t.children) { 
      if (e.value > max) 
       max = e.value; 
     } 

    return max; 
} 

上面的代码将返回最多4个，这意味着它只检查t的孩子，但不检查后面的孩子。在这种情况下，它不会检查4，[7,8,9]和2，[5,6]的儿童组。我该如何改变它，以便该方法找到所有后续孩子的最大值？

Answer 1

public static int maximum(NTN t) { 
    int max = t.value; 
    Set<NTN> children = t.children; 

    // only check if this node is not a leaf 
    if (children != null && !children.isEmpty) { 
    for (NTN e : children) { 
     // here is the recursion 
     int maxNext = maximum(e); 

     if (maxNext > max) max = maxNext; 
    } 
    } 

    return max; 
} 

希望这有助于:)

Answer 2

您的解决方案是不Recursive，这样就不会在你的子儿去，如果有的话。你可能想看看Tabu Search。一个更简单的方法（但容易陷入local maximum）将是Hill Climbing。

Answer 3

我想这样的事情会有所帮助，你正在做的就像你的树上的DFS遍历所有的节点，你看看每个节点的值，如果它大于你保留的静态变量的最大值在你的公共类（例如public static int max）中，你将max设置为该节点的值，就像这样（希望没有测试过，注意返回类型是无效的，并且你直接更新你的变量公开课）：

 public void maximum(NTN T){ 
      if (!T.children.isEmpty() && T.children != null){ 
       for(NTN e: T.children) 
        maximum(e) 
      } 
      if (PUBLIC_CLASS.MAX < T.value) 
       PUBLIC_CLASS.MAX = T.value; 
     }