计算二叉搜索树中的节点 [英] Counting the nodes in a binary search tree

问题描述

我需要创建一个以二进制搜索树的根节点为参数的递归方法.然后，此递归方法将返回整个二叉搜索树中节点总数的int值.

I need to create a recursive method that takes as a parameter the root node of a binary search tree. This recursive method will then return the int value of the total number of nodes in the entire binary search tree.

这是我到目前为止所拥有的:

This is what I have so far:

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方法这样调用节点:

The main method calls nodes like so:

        System.out.println ("\nThis section finds the number of nodes "
             + "in the tree"); 

        System.out.println ("The BST has " + bst.nodes() + " nodes");

因此，我按顺序运行搜索，一旦到达没有子节点的节点，我将删除当前节点并返回父节点并继续.我对上面的方法进行了调试，当程序最终计数并删除了根节点左右两侧的所有节点并尝试返回1时，程序崩溃并显示NullPointerException().

So I was running the search by traveling in order, once I'd get to a node with no children I would delete the current node and return to the parent node and continue. I ran a debug of the method I have above and the program crashes with a NullPointerException() when it finally counts and removes all the nodes on the left and right side of the root node and tries to return 1.

这是我的实验室，该方法必须是递归的.

This is for my lab, the method MUST be recursive.

我现在很迷茫，有人知道我在做什么错吗?

I'm very lost at this point, does anyone know what I'm doing wrong?

推荐答案

您使这种方式过于复杂.面向对象编程的基本思想是，您信任对象来完成他们知道答案的工作.因此，如果我是父母，我可以数数自己，让我的孩子数数自己，依此类推.

You are making this way too complicated. The basic idea of object oriented programming is that you trust objects to do the jobs they know the answers to. So if I'm a parent, I can count myself, and I let my children count themselves, and so forth.

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);
}

这篇关于计算二叉搜索树中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！