java - 无法获取 k-ary 树的叶子数

Question

我用Java编写了一个K-ary树结构的程序，所以我试图找到树的叶子数..

import java.util.List;
import java.util.ArrayList;

/**
A tree in which each node has an arbitrary number of children.
*/
public class Tree
{
 private Node root;

 class Node
 {
  public Object data;
  public List<Node> children;

  public int size()
  {
      int sum = 0;
      for (Node child : children)
      {
      sum = sum + child.size();
      }
      return 1 + sum;
  }

  public int leaves()
  {
    return children.size();
  }

  }

  /**
     Computes the size of the subtree whose root is this node.
     @return the number of nodes in the subtree
  */


  /**
     Counts the number of leaves in the subtree whose root is this node.
     @return the number of leaves in the subtree
   */
  public int leaves()
   {
    int size=0;
    if(root==null)
        return 0;
    else{
        for(Node child: root.children){
            if(child.children!=null){
                size+=child.size();
            }else{
                size++;
            }
        }
    }
    return size;
    }

  public String printTree(int level)
  {
    return (String) root.data;


   }

  /**
    Constructs an empty tree.
  */
  public Tree()
 {
   root=new Node();
   root.children=new ArrayList<Node>();
  }

 /**
  Constructs a tree with one node and no children.
    @param rootData the data for the root
*/
    public Tree(Object rootData)
 {
root=new Node();
root.data=rootData;
root.children=new ArrayList<Node>();
  }

  /**
  Adds a subtree as the last child of the root.
 */
 public void addSubtree(Tree subtree)
 {
root.children.add(subtree.root);
 }

/**
  Computes the size of this tree.
  @return the number of nodes in the tree
 */
  public int size()
  {

   if(root==null)
       return 0;
   else 
       return root.size();
  }

 /**
 * Get the number of leaves in this tree
 * @return the number of leaves in this tree
 */

  public String printTree()
 {
   System.out.println(root.data);
   return (""+root.data);

   }


 }

这是我的主程序

package draftb;

/**
This class demonstrates the tree class.
*/
public class TreeTester
{
public static void main(String[] args)
{
  Tree t = new Tree();
 System.out.println(t.leaves());
System.out.println("Expected: " + 0);

Tree t1 = new Tree("Anne");
System.out.println(t1.leaves());
System.out.println("Expected: " + 1);

Tree t2 = new Tree("Mary");    
t2.addSubtree(new Tree("John"));
t2.addSubtree(new Tree("Carl"));
t2.addSubtree(new Tree("Liz"));

System.out.println(t2.leaves());
System.out.println("Expected: " + 3);

t1.addSubtree(t2);
t1.addSubtree(new Tree("Miles"));
System.out.println(t1.leaves());
System.out.println("Expected: " + 4);

Tree t3=new Tree("Jose");
t3.addSubtree(new Tree("Josh"));
t3.addSubtree(new Tree("Peter"));

t3.addSubtree(t1);
System.out.println(t3.leaves());
System.out.println("Expected: " + 6);

System.out.println(t3.size());
System.out.println("Expected: " + 9);

t3.printTree();
System.out.println("Expected: Jose");

}
}


The output which I am getting and the one which I expect is 
0
Expected: 0
0
Expected: 1
3
Expected: 3
Expected: 4
8
Expected: 6
9
Expected: 9
Jose
Expected: Jose

所以，可以看出，当没有插入节点时，我得到的 3 和 9 也写为 0，但是我得到的中间结果是错误的..有人可以指出我的错误吗..？谢谢

Answer 1

对于没有子节点的节点计数 1，否则使用递归叶计数的总和。

在节点中:

public int leaves() {
  if (children.size() == 0) {
    return 1;  // This is a leaf
  }
  int count = 0;  // No leaf, sum up leaves of children
  for (Node child : children) {
    count += child.leaves();
  }
  return count;
}

在树中:

public int leaves() {
  return root == null ? 0 : root.leaves();
}