我需要创建一个递归方法,该方法将二叉搜索树的根节点作为参数。此递归方法将返回整个二叉搜索树中节点总数的 int 值。
这是我到目前为止所拥有的:
public class BinarySearchTree<E> extends AbstractSet<E>
{
protected Entry<E> root;
//called by the main method
public int nodes()
{
return nodes(root);
}
//nodes() will count and return the nodes in the binary search tree
private int nodes(Entry<E> current)
{
if(current.element != null)
{
if(current.left == null && current.right == null)
{
if(current.element == root.element)
return 1;
deleteEntry(current);
return 1 + nodes(current.parent);
}
else if(current.left != null && current.right == null)
return nodes(current.left);
else if(current.left == null && current.right != null)
return nodes(current.right);
else if(current.left != null && current.right != null)
return nodes(current.left) + nodes(current.right);
} else return 1;
return 0;
}
main方法像这样调用节点:
System.out.println ("\nThis section finds the number of nodes "
+ "in the tree");
System.out.println ("The BST has " + bst.nodes() + " nodes");
因此,我通过按顺序移动来运行搜索,一旦到达没有子节点的节点,我将删除当前节点并返回到父节点并继续。我对上面的方法进行了调试,当它最终计数并删除根节点左侧和右侧的所有节点并尝试返回 1 时,程序因 NullPointerException() 崩溃。
这是我的实验室,该方法必须是递归的。
我现在很迷茫,有人知道我做错了什么吗?
最佳答案
你把这种方式搞得太复杂了。面向对象编程的基本思想是,您相信对象会完成它们知道答案的工作。所以如果我是 parent ,我可以数自己,我也让我的 child 数自己,等等。
private int nodes(Entry<E> current) {
// if it's null, it doesn't exist, return 0
if (current == null) return 0;
// count myself + my left child + my right child
return 1 + nodes(current.left) + nodes(current.right);
}
关于java - 计算二叉搜索树中的节点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13756605/