0

m-ary ツリーのすべてのノードがいっぱいかどうかを判断しようとしています。私は一般的な考えを持っていると思いますが、よくわかりません。これが私がこれまでに行ったことです。

私の TreeNode クラスには、次のメソッドがあります。

    public class TreeNode
    {
       private String label;
       private String message;
       private TreeNode[] nodes;
       private int numChildren;
       private TreeNode parent;
       private String prompt;

           ***other methods and constructors***

      public boolean isFull()
    {
      for(int i = 0; i < numChildren; ++i)
      {
        if(nodes[i] == null)
            return false;
      }
      return true;
    }

ここで、numChildren は配列 nodes[] (または単に nodes.length) 内の可能な子の総数であり、nodes[] は現在のノードのすべての子ノードの配列です。また、必要に応じて現在のノードの親ノードを取得できるように、TreeNode が二重にリンクされていることを知っておくと役立つ場合があります。

次に、私の Tree クラスには、次の再帰メソッドがあります。

    public boolean allNodesFull(TreeNode n)
    {
      boolean allFull = false;
      if(!n.isFull())
      {
        return allFull;
      }
      for (int i = 0; i < n.getNumChildren(); ++i)
      {
        allFull = allNodesFull(n.getChild(i));
      }
      return allFull;
    }
4

1 に答える 1

1

まだテストしていません。すでにテストケースを用意して、動作するかどうか教えてください ;)

public boolean allNodesFull(TreeNode n) {
  if(!n.isFull()) {
    return false;
  }
  for (int i = 0; i < n.getNumChildren(); ++i) {
    if (!allNodesFull(n.getChild(i))) {
      return false;
    }
  }
  return true;
}
于 2012-11-03T18:17:00.650 に答える