2

私は短いNTNクラスによって定義されたn-aryツリーを持っています

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

そのようなn-aryツリーの最大値を見つけたいと思います。値が次の単純な整数n-aryツリーであるとしましょう：[親：1子：2、3、4] [親：2子：5、6] [親：4子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

あなたの解決策は再帰的ではないので、もしあれば、それはあなたのサブの子供たちに行き続けることはありません。タブーサーチをご覧になることをお勧めします。より簡単なアプローチ（ただし、極大値でスタックする傾向があります）は、山登り法です。

于 2012-11-02T07:01:13.123 に答える
0

このようなことが役立つと思います。ツリーでDFSのようにすべてのノードをトラバースし、各ノードの値を確認します。これが、静的変数として保持している最大値よりも大きい場合は、 public class（たとえば、public static int max）、maxをそのノードの値に設定します。これは次のようになります（テストされていない場合は、return typeが無効であり、public class内の変数を直接更新することに注意してください）： 

     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 
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 に答える
0

次のコードは、naryツリーからmaxm値を使用して完全なノードを再実行します

//以下は、指定されたツリーノード構造です。

レンプレート

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 に答える