对于我的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;
}
您似乎在某个时刻忘记了包含根。
一个简单的检查健全性检查是记住你有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;
}