1

私は次のようなNodeクラスを持っています：

public class Node {

    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(Node leftNode, Node rightNode, int value){
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.value = value;
    }

   //Getter and Setter methods for these variables are defined here
}

このNodeクラスは、バイナリツリーを作成するために使用されます。すべてのノードの平均を計算するために、JAVAで再帰関数を作成しています。私が以下に書いたコードは正しい答えを与えません。これは、参照ではなく、パラメータaverageとnodeCountの値が渡されるためだと思います。

public double treeAverage(Node node, double average, int nodeCount){

    nodeCount ++;
    if(node == null) return Double.MAX_VALUE;
    if(node.getLeftNode()==null && node.getRightNode()==null){
        average = ( average + node.getValue() )/nodeCount;
    }

    if(node.getLeftNode()!=null){
        average = treeAverage(node.getLeftNode(), average, nodeCount); 
    }
    if(node.getRightNode()!=null){
        average = treeAverage(node.getRightNode(), average, nodeCount);
    }

    return average;

}

Javaでこの再帰関数を修正する正しい方法は何でしょうか？（CIでは、これらのパラメーターへの参照を渡すことができます）。私が間違っている場合は訂正してください。

4

5 に答える 5

3

ヘルパーメソッドを使用できると思います。このようなもの（私はこのコードをコンパイルしていません、ヒントとしてとらえるべきです）

private static long count = 0L;
private static long sum = 0L;


public static int treeAverageHelper(Node node){

    if(node == null) return 0;
    count ++;
    return node.val + treeAverageHelper(node.left) + treeAverageHelper(node.right);
}

public static double treeAvg(Node n){
    sum = treeAverageHelper(n);
    if (count == 0)
        return 0D;
    else
        return (double)sum/count;
}

ヘルパーは、ツリーを集計してカウントします。そして最後にあなたは2つを分けます。

于 2012-09-20T05:13:13.120 に答える
2

平均計算には問題があると思います。コードによると、ノードに左の子と右の子がない場合は、average + node.getValue（）を追加し、この結果をnodeCountで除算します。

実際には、

平均は、合計値をカウントで割ったものです。

つまり、最初に合計ノード値を取得し、これをnodeCountで割る必要があります。

于 2012-09-20T05:05:10.557 に答える
2

私はこれらの2つの部分のファンではありません：

if(node == null) return Double.MAX_VALUE;
if(node.getLeftNode()==null && node.getRightNode()==null){
    average = ( average + node.getValue() )/nodeCount;
}

最初のステートメントでは、空のツリーの平均が可能な限り最高のDoubleになるのはなぜですか？任意のようです。ツリーには要素が含まれていないため、存在しない、、Double.NaNまたは存在しないと言う方が簡単です。0.0

2番目のステートメントでは、両方の子がnullの場合、その値を取得するという論理が正しいです。ただし、途中で平均を壊してしまいます。ノードが12個あり、3番目のノードにいる場合は、4番目のノードに移動したときに平均値が異なります。

より高いスコープに移動nodeCountし、再帰呼び出しからすべてのノードの合計をカウントするまで、実際の平均を計算する必要はありません。最後に、ノードの合計を渡します。

于 2012-09-20T04:57:27.800 に答える
0

次のようなクラスを定義する必要があります

class RecursionValues {
     int nodeCount;
     double average;
}

...次に、再帰呼び出しで、このクラスのインスタンスを渡し、そのフィールドを変更します。

于 2012-09-20T04:52:32.913 に答える
0

これが私がそれを機能させることができた方法です。それが良い方法ではない場合は私に知らせてください。

private double sum = 0;
private int nodeCount = 0;

public double treeAverage(Node node){

    if(node == null) return Double.NaN; //Null check

    sum = treeSum(node);
    double average = (sum/nodeCount);

    // before returning, reset the sum and nodeCount, so that same object can use the same function starting with correct/zero values of sum and nodeCount
    sum = 0; nodeCount = 0;

    return average;

}

public double treeSum(Node node){

    nodeCount ++; //update the nodeCount
    sum = sum + node.getValue(); //update the sum to include this node

    /* If the current node has children, recurse*/      
    if(node.getLeftNode()!=null){
        sum = treeSum(node.getLeftNode()); 
    }
    if(node.getRightNode()!=null){
        sum = treeSum(node.getRightNode());
    }

    return sum;

}
于 2012-09-20T17:57:59.520 に答える