2

我有一个由短 NTN 类定义的 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] 的子集。如何更改它以便该方法找到所有后续子项的最大值？

4

5 回答 5

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

希望这可以帮助 ：）

于 2012-11-02T07:00:44.683 回答
1

您的解决方案不是Recursive，因此如果有的话，它不会继续存在于您的子孩子中。您可能想看看禁忌搜索。一种更简单的方法（但容易陷入局部最大值）是爬山。

于 2012-11-02T07:01:13.123 回答
0

我想这样的事情会有所帮助，你在树上做一个 DFS 来遍历所有节点，然后查看每个节点的值，如果它大于你作为静态变量保留的最大值公共类（例如公共静态 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;
        }
于 2012-11-02T07:05:57.073 回答
0

以下代码从 nary 树中重新运行具有最大值的完整节点

// 以下是给定的树节点结构。

模板

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;

}
于 2019-06-05T05:09:56.140 回答
0 
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));
        }
    }
}
于 2018-08-05T16:22:54.967 回答