2

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

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

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?

4

5 回答 5

18

你让这种方式太复杂了。面向对象编程的基本思想是您信任对象来完成它们知道答案的工作。所以如果我是父母，我可以数数自己，我让我的孩子数数自己，等等。

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);
}
于 2012-12-07T03:58:35.977 回答
4

你有几个问题：

  • 您在计算节点时正在删除节点？是不是nodes()要清理树？
  • 您将root==null, root!=null&left==null&&right==null,root!=null&left!=null&right==null等视为单独的案例。他们不是。您有三种情况，它们并不完全排他性：
    • 如果当前节点不为空，则将计数加一。（应该总是这样。唯一可能为假的情况是当前节点 == root，我们可以事先检测并回避它。）
    • 如果当前节点有左孩子，则添加左孩子的计数。
    • 如果当前节点有右孩子，则添加右孩子的计数。
  • 出于某种不敬虔的原因，您正在遍历树。看起来它与删除节点有关......？

但在我看来，最重要的是，你没有给Entrys 足够的自主权。:P

一个节点可以计算它自己的子节点。相信它。

class Entry<E> {
    ...

    int count() {
        int result = 1;
        if (left != null) result += left.count();
        if (right != null) result += right.count();
        return result;
    }
}

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

如果你的老师不称职，并且坚持在节点之外使用一些节点计数功能，你可以做你想做的同样的事情：

private int nodes(Entry<E> current) {
     int result = 1;
     if (current.left) result += nodes(current.left);
     if (current.right) result += nodes(current.right);
     return result;
}

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

但在我看来，那个老师应该被解雇。Entry类是真正的树； BinarySearchTree实际上只是一个引用根的容器。

另请注意，我不在乎parents。如果我们从根开始计数，每个节点都计算它的子节点，计算它们的子节点等等……那么所有节点都将被计算在内。

于 2012-12-07T03:57:09.473 回答
1 
public int countNodes(Node root){
    // empty trees always have zero nodes
    if( root == null ){
        return 0;
    }

    // a node with no leafes has exactly one node
    // note from editor: this pice of code is a micro optimization
    // and not necessary for the function to work correctly!
    if( root.left == null && root.right == null ){
        return 1;
    }

    // all other nodes count the nodes from their left and right subtree
    // as well as themselves
    return countNodes( root.left ) + countNodes( root.right ) + 1;
}
于 2017-01-12T09:38:11.953 回答
0

删除currentin:后deleteEntry(current);，使用current.parentinreturn 1 + nodes(current.parent);

可能这就是抛出 NullPointerException 的原因。

于 2012-12-07T03:55:41.567 回答
0

嘿，我为二叉树实现了非常干净的计数：

public class Binary<T> where T: IComparable<T>
{
    private Node _root;

    public int Count => _root.Count;

    public void Insert(T item)
    {
        Node newNode = new Node(item);
        if (_root == null)
            _root = newNode;
        else
        {
            Node prevNode = _root;
            Node treeNode = _root;
            while (treeNode != null)
            {
                prevNode = treeNode;
                treeNode = newNode.Item.CompareTo(treeNode.Item) < 1 ? treeNode.Left : treeNode.Right;
            }
            newNode.Parent = prevNode;
            if (newNode.Item.CompareTo(prevNode.Item) < 1)
                prevNode.Left = newNode;
            else
                prevNode.Right = newNode;
        }
    }

    public class Node
    {
        public T Item;

        public Node Parent;
        public Node Left;
        public Node Right;

        public Node(T item, Node parent = null, Node left = null, Node right = null)
        {
            Item = item;
            Parent = parent;
            Left = left;
            Right = right;
        }

        public int Count
        {
            get
            {
                int count = 1;
                count += Left?.Count ?? 0;
                count += Right?.Count ?? 0;
                return count;
            }
        }
    }
}

也许这可以帮助您了解如何为带有计数的简单二叉树实现类。

此实现通过树中相应节点中的计数来访问计数。

如果您不熟悉 .NET 4.6 的标记，请告诉我

于 2015-06-12T19:58:48.183 回答