java寻找无树的最大值

Question

我有一个n元树，由

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

我想找到这样一棵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

我想这样做会有所帮助，你在树上做一些类似DFS的事情来遍历所有节点，然后查看每个节点的值，如果它大于你在公共类中作为静态变量保留的最大值（例如public static int max），你将max设为该节点的值，这样做可以（希望没有经过测试，请注意返回类型是void，您可以直接在公共类中更新一个变量）：

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

Answer 2

你的解决方案不是Recursive，所以它不会继续在你的子代中运行，如果有的话。你可能想看看Tabu Search。一个更简单的方法（但容易陷入local maximum）是Hill Climbing

Answer 3

public static int maximum(NTN t) {
    int max = t.value;
    Set<NTN> children = t.children;
    if (children != null && !children.isEmpty) {
        for (NTN e : children) {
            max = Math.max(max, maximum(e));
        }
    }
}

Answer 4

下面的代码从一棵树中使用maxm值重新运行完整节点

//下面是给定的树节点结构

template

class TreeNode
 {
    public:
        T data;
        vector<TreeNode<T>*> children;

        TreeNode(T data) {
            this->data = data;
        }

        ~TreeNode() {
            for (int i = 0; i < children.size(); i++) {
                delete children[i];
            }
        }
 };



TreeNode<int>* maxDataNode(TreeNode<int>* root) {

    if(root == NULL) return NULL;
    TreeNode<int>* maxNode = new TreeNode<int>(0);
    int max = 0;

    for(int i=0; i<root->children.size();i++){
        if(maxDataNode(root->children[i])->data > max)
        {    
            max = maxDataNode(root->children[i])->data;
            maxNode = maxDataNode(root->children[i]);
        }
    }
    if(root->data > maxNode->data)
    {
        maxNode = root;
        return maxNode;
    }
    return maxNode;

}

Answer 5

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

希望这有帮助：）