2

二分探索木のルート ノードをパラメーターとして受け取る再帰的メソッドを作成する必要があります。この再帰メソッドは、二分探索木全体のノードの総数の 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;
}

メイン メソッドは次のようにノードを呼び出します。

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

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

そのため、順番に移動して検索を実行していました。子のないノードに到達したら、現在のノードを削除し、親ノードに戻って続行しました。上記のメソッドのデバッグを実行したところ、最終的にルート ノードの左側と右側のすべてのノードをカウントして削除し、1 を返そうとすると、プログラムが NullPointerException() でクラッシュします。

これは私のラボ用です。メソッドは再帰的でなければなりません。

私はこの時点で非常に迷っています。誰かが私が間違っていることを知っていますか?

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彼らはそうではありません。完全に排他的ではない3つのケースがあります。
    • 現在のノードがnullでない場合は、カウントに1を追加します。（これは常に当てはまるはずです。これがfalseになる可能性がある唯一のケースは、現在のノード==の場合で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実際には、ルートへの参照用の単なるコンテナです。

また、私はsについて気にしないことに注意してくださいparent。ルートからカウントを開始し、各ノードがその子をカウントし、子をカウントするなどの場合、すべてのノードが考慮されます。

于 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

で削除currentした後：deleteEntry(current);、で使用current.parentしますreturn 1 + nodes(current.parent);

これがNullPointerExceptionをスローする理由である可能性があります。

于 2012-12-07T03:55:41.567 に答える