java - 需要帮助编写一个函数来确定二叉树数组有多少个子节点

Question

对于我的 CSCE 230 类(class)，我正在编写一个处理二叉树数组的程序，我们的部分作业是编写一个函数来确定树是否平衡。对于那些不知道的人来说，要使树平衡，左子树和右子树的高度不能相差超过 1。她和我都希望该函数是递归的，但绝不必须如此。

我们不允许在这个程序中使用节点，我的老师为我们提供了这种方法来了解每个 child 应该存储在哪里:

The root of the tree is at index 0.

The array that stores the values in the tree is called values, we are using values.length to represent its length.

Assuming a node is located at index n, its left child is at index 2n+1 and its right child is located at index 2n+2.

We are using "" to indicate that a node does not have a left and/or right child.

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

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

Answer 1

您似乎忘记在某个时候包含根目录。

一个简单的健全性检查是记住您有 4 种情况:情况1:节点不存在，所以count = 0情况 2:该节点没有子节点，因此 count = 1情况 3:该节点有一个子节点，因此 count = 2(因为你说我们包括根节点)情况 4:该节点有两个子节点，因此 count = 3。

您的代码绝不会因为忘记包含根而返回 3。

此外，此方法的最大值始终为 3，因此，如果您想知道整个树的节点数，您可能需要修改该方法，以便为每个子节点递归地调用自身。

附注，您检查左右节点两次。您可以将代码简化为如下所示，因为我们不关心首先计算哪个节点:

private int getNonNullSC(int a) {
int count = 0;
if (a+a+2 < values.length) {
    if (values[a] == null) 
    {
        count = count + 1; // Or simplified: count++; which means count is now 1
    }

    if (values[a+a+1] != null) {
        count++; // which means counts is now 2
    }

    if (values[a+a+2] != null) {
        count++; // which means count is now 3 or 2 if there was no left node
    }
}
return count;

}