Как вычислить число childern в дереве с помощью рекурсии

Question

Я разработал рекурсивный алгоритм для поиска числа детей в строке. Строка представляет собой массив, такой как [1,0,1,0,1]. Там три возможных ребенка этой строки, которые являются [0,0,1,0,1], [1,0,0,0,1] и [1,0,1,0,0]. Таким образом, критерии для создания дочерних элементов - это уменьшение только одной ненулевой записи в строке. Поскольку в [1,0,1,0,1] имеется три ненулевых элемента, то есть три возможных дочерних элемента. Продолжая таким образом, у каждого ребенка теперь могут быть два возможных ребенка и так далее. Рекурсия останавливается, когда в строке есть только одна ненулевая запись.

Это мой код:

public class Recursion { 

/** 
* @param args the command line arguments 
*/ 
    public static void main(String[] args) { 
     // TODO code application logic here 
     int[] c={1,0,1,0,1}; 
     System.out.println(num(c)); 
    } 

    private static int num(int[] v){ 
     if(numChildren(v)==1){ 
      return 1; 
     }  
     else{ 
      int[][] ge=children(v); 
      for(int[] e:ge){ 
      return 1+num(e); 
      } 
      System.out.print("this return should never execute"); 
      return 0; 
     } 
    } 

    private static int numChildren(int[] val){ 
     int sum=0; 
     for(int i=0;i<val.length;i++){ 
      if(val[i]!=0){ 
       sum+=1; 
      } 
     } 
     return sum; 
    } 

    private static int[][] children(int[] p){ 
     int pChildern=numChildren(p); 
     int[] d=new int[pChildern]; 
     int[][] r=new int[pChildern][]; 
     int c=0; 
     for(int j=0;j<p.length;j++){ 
      if(p[j]!=0){ 
       d[c]=j; 
       c++; 
      }  
     } 

     for(int i=0;i<pChildern;i++){ 
      p[d[i]]--; 
      r[i]=p.clone(); 
      p[d[i]]++; 
     } 
     return r; 
    } 
} 

Мой код делает казнить, но не дает правильный результат. Он должен печатать 6, но печатает 3.

Может ли кто-нибудь предложить мне, что не так с этим кодом?

Answer 1

Я действительно не вдаваться в подробности, но этот блок выглядит странно:

int[][] ge=children(v); 
for(int[] e:ge){ 
    return 1+num(e); 
} 
System.out.print("this return should never execute"); 
return 0; 

Вы хотите, чтобы подвести итог всех своих детей здесь, но вы возвращаетесь слишком рано. Это должно быть что-то вроде этого:

int[][] ge=children(v); 
int totChild = 0; 
for(int[] e:ge){ 
    totChild = totChild + num(e); 
} 

return totChild; 

Answer 2

// Returns size of subtree including the root 
int getNumChilds(Node node) { 
    int count = 1; 
    for (Node child : node.getChildren()) { 
     count += getNumChilds(child); 
    }   
    return count; 
} 

Answer 3

Я думаю, следующий код может быть хорошо подходит для ваших нужд.

{1, 0, 1, 0, 1} -> дает 7 (2 х 2 х 2 - 1)

{1, 1, 1, 1, 1} -> дает 31 (2 х 2 х 2 х 2 х 2 - 1)

{4, 4, 1, 1, 1} -> дает 199 (5 х 5 х 2 х 2 х 2 - 1)

- 1 - удалить {0, 0, 0, 0, 0} из детей.

public class Recursion { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     // TODO code application logic here 
     int[] c={4,4,1,1,1}; 
     System.out.println(num(c, 0)); 
    } 

    private static void print(int[] v) { 
     System.out.print("["); 
     for (int i = 0; i < v.length; ++i) { 
      System.out.print(v[i] + ","); 
     } 
     System.out.println("] "); 
    } 

    private static int num(int[] v, int k){ 
     if(numChildren(v)==1){ 
      return 1; 
     } 
     else{ 
      int r = 1; 
      for (int i = k; i < v.length; ++i) { 
       if (v[i] > 0) { 
        int o = v[i]; 
        v[i] = o - 1; 
        print(v); 
        r += num(v, i); 
        v[i] = o; 
       } 
      } 
      return r; 
     } 
    } 

    private static int numChildren(int[] val){ 
     int sum=0; 
     for(int i=0;i<val.length;i++){ 
      if(val[i]!=0){ 
       sum+=1; 
      } 
     } 
     return sum; 
    } 
}