我用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,但是我得到的中间结果是错误的..有人可以指出我的错误吗..?谢谢
最佳答案
对于没有子节点的节点计数 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();
}
关于java - 无法获取 k-ary 树的叶子数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20411256/