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

助手，通过树聚合和计数。最后你把两者分开。

于 2012-09-20T05:13:13.120 回答
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- 因为树中有零个元素。

对于第二个语句，你的逻辑是正确的，如果两个孩子都是空的，你会得到它的值。但是，您将在此过程中破坏您的平均值 - 如果您有十二个节点，并且您在第三个节点上，那么当您移动到第四个节点时，您的平均值将有所不同。

移动nodeCount到更高的范围，在计算递归调用中所有节点的总和之前，不要担心计算实际平均值。最后，在进行过程中传递节点的总和。

于 2012-09-20T04:57:27.800 回答
2

我认为平均计算有问题。根据您的代码，如果节点没有左孩子也没有右孩子，则添加平均值 + node.getValue() 并将此结果除以 nodeCount。

实际上，

平均值是总值除以计数。

这意味着您应该首先获得总节点值并将其除以 nodeCount。

于 2012-09-20T05:05:10.557 回答
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 回答
0

您需要定义一个类，例如

class RecursionValues {
     int nodeCount;
     double average;
}

...然后在您的递归调用中，您传递此类的一个实例并修改其字段。

于 2012-09-20T04:52:32.913 回答