[需要帮助编写函数来确定二叉树数组有多少个子代]] << [

Question

对于我的CSCE 230类，我正在编写一个处理二叉树数组的程序，我们的部分工作是编写一个确定树是否平衡的函数。对于那些不知道的对象，要使一棵树保持平衡，左右子树的高度相差不能超过1。她和我都希望函数具有递归性，但决不是必须的。

我们不允许在该程序中使用节点，我的老师为我们提供了这种方法，该方法可以知道每个孩子应该存储在哪里：

树的根在索引0处。

在树中存储值的数组称为values，我们使用values.length表示其长度。

假设节点位于索引n处，其左子节点位于索引2n + 1处，而其右子节点位于索引2n + 2处。

我们使用“”来表示节点没有左孩子和/或右孩子。

假设我正确地存储了所有内容，可能是什么原因导致下面的函数（该函数应该测量子树的高度（包括子树的根）返回错误的答案？

/**
 * Determines if the tree is balanced. A tree is balanced if a 
 * node's left and right subtree heights differ by at most one.
 * @return True if balanced, false otherwise.
 */
public boolean isBalanced() { 
    boolean balanced = false;
    if (values[0] == null) balanced = true;
    // count non-null subchildren for all nodes. Use P-L-R format (parent-L-R)
    // then for all non-leaf nodes, subtract the larger from the smaller.

    for (int i = 0; i < values.length; i++) {
        if (values[i] != "") System.out.println("values["+i+"] has " + getNonNullSC(i) + " non-null children.");
    }

    for (int i = 0; i < values.length; i++) {
        for (int j = 0; j < values.length; j++) {
            if (Math.abs(getNonNullSC(i)-getNonNullSC(j)) >= 0 && Math.abs(getNonNullSC(i)-getNonNullSC(j)) <= 1)
                balanced = true;
        }
    }

    return balanced;
}

// returns the number of non-null children a subtree has
private int getNonNullSC(int a) {
    int count = 0;
    if (a+a+2 < values.length) {
        if (values[a] == null) count = 1; // if it is a leaf node, it has no children
        else if (values[a+a+1] != null) { // if it has a left child
            if (values[a+a+2] == null) count = 2; // it has one child if no right child
            else count = 2; // otherwise it has two children
        }
        else if (values[a+a+2] != null) { // if it has a right child
            if (values[a+a+1] == null) count = 1; // it has one child if no left child
            else count =  2; // otherwise it has two children
        }
    }
    return count;
}

对于我的CSCE 230类，我正在编写一个处理二叉树数组的程序，我们的部分工作是编写一个确定树是否平衡的函数。对于那些...

Answer 1

看来您在某些时候忘记了包含根。