3

注意：これは宿題に関連していますが、「宿題」タグが廃止（？）としてマークされているため、そのようにタグ付けしていません。

二分木を実装する次のクラスを使用して...

class TreeNode
{
  private Object value; 
  private TreeNode left, right;

   public TreeNode(Object initValue)
  { 
     value = initValue; 
     left = null; 
     right = null; 
  }

   public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
  { 
     value = initValue; 
     left = initLeft; 
     right = initRight; 
  }

   public Object getValue()
  { 
     return value; 
  }

   public TreeNode getLeft() 
  { 
     return left; 
  }

   public TreeNode getRight() 
  { 
     return right; 
  }

   public void setValue(Object theNewValue) 
  { 
     value = theNewValue; 
  }

   public void setLeft(TreeNode theNewLeft) 
  { 
     left = theNewLeft;
  }

   public void setRight(TreeNode theNewRight)
  { 
     right = theNewRight;
  }

}

「一人っ子」であるバイナリツリー内のノードの数を計算する必要があります。これは、親に由来する別のノードがないノードとして定義されています。

これは私がこれまでに持っているものです：

public static int countOnlys(TreeNode t)
  {
     if(t == null)
         return 0;
     if(isAnOnlyChild(t))
         return 1;
     return countOnlys(t.getLeft()) + countOnlys(t.getRight());
  }

booleanメソッドの実装方法がわかりませんisAnOnlyChild(TreeNode t)

誰か助けてくれませんか？

4

6 に答える 6

6

あなたはかなり近くにいて、トラバーサルは見栄えが良いですが、Treenodeには、子とその親の間にリンクがありません。したがって、兄弟（右の子）が存在するかどうかは、左の子とは言えません。

親Treenodeを（左と右とともに）持つことができるので、特定のノードの親が持っている子の数を確認できます。または、ajp15243が提案したように、代わりに、特定のノードにある子の数をチェックするメソッドを使用します。

後者のいくつかの擬似コード：

//we still need to check if that only child has its own children
if hasOnlyChild(t) 
      return 1 + checkOnlys(left) + checkOnlys(right)
else 
      return checkOnlys(left) + checkOnlys(right)
于 2013-02-06T00:26:08.170 に答える
2

すでにお気づきのように、1つの解決策は、子供が1人だけの親の数を数えることです。これは機能するはずです：

public static int countOnlys(TreeNode t)
  {
     if(t == null || numberOfChildren(t)==0){
         return 0;
     }
     if(numberOfChildren(t)==1){
         return 1+ countOnlys(t.getLeft()) + countOnlys(t.getRight());
     }
         if(numberOfChildren(t)==2 ){
         return countOnlys(t.getLeft()) + countOnlys(t.getRight());
    }
         return 0;
  }

public static int numberOfChildren (TreeNode t){
    int count = 0;
    if(t.getLeft() != null ) count++;
    if(t.getRight() != null) count++;       
    return count;   
    }
于 2013-02-06T01:13:19.043 に答える
1

子の1つだけがnullでない場合、親には1人の子があります（これは、その子の1つだけがnullであることを意味します）。

((t.getLeft() == null || t.getRight() == null)) && !(t.getLeft() == null && t.getRight() == null)

ただし、再帰コードがツリーをトラバースするため、ノードにアクセスしたときにノードをテストしません。（これはVisitorパターンに似ています。）あなたがすることは、あなたが親の上に座っているときに一人っ子をテストすることです。これは実際には論理排他的論理和です。つまり、このノードに1人の子があることを検出するには、子の1つだけがnull以外である必要があるためです。

したがって、アルゴリズムは

  1. ツリーの各ノードにアクセスします。
  2. ノードに子が1つしかない場合は、カウントします

それでおしまい。残りは配管です。

于 2013-02-06T00:13:03.100 に答える
1 
public static int onlyChild(TreeNode t){
    int res = 0;
    if( t != null){
        // ^ means XOR 
        if(t.getLeft() == null ^ t.getRight() == null){
            res = 1;
        }

        res += onlyChild(t.getLeft()) + onlyChild(t.getRight()));
    }

    return res;
}
于 2016-04-30T03:43:33.020 に答える
0

二分木をトラバースするときはいつでも、再帰的に考えてください。これはうまくいくはずです。

public static int countOnlys(TreeNode t)
  {
     if(t == null)
         return 0;
     if (t.getLeft()==null&&t.getRight()==null)
         return 1;

     return countOnlys(t.getLeft())+countOnlys(t.getRight());

  }
于 2013-02-06T00:14:39.083 に答える
-1 
public int countNode(Node root) {

         if(root == null)
             return 0;

         if(root.leftChild == null && root.rightChild == null)
             return 0;
         if(root.leftChild == null || root.rightChild == null)
             return 1 + countNode(root.leftChild) + countNode(root.rightChild);
         else
             return countNode(root.leftChild) + countNode(root.rightChild);

     }
于 2013-07-02T13:58:53.750 に答える