前几天我问了一个关于同一个项目的问题,从那时起我们的小组已经设法完成了我们所有的方法,除了一个用于确定二叉搜索树是否是完成。Recursivley测试二进制搜索树是否完整
我们使用一个包装方法和一个辅助方法递归地做到这一点。
我们知道我们需要检查树的h-1层(h是高度)以确保它是完美的,那么我们需要确保最后一层上的所有叶节点都从左边开始没有差距的权利。
无论我们尝试什么,我们都无法弄清楚如何递归检查剩余的叶节点,以确保它们从左到右依次连续。但是,我们可以确保它完美达到(h-1)级别。
有人能指出我们在正确的方向上如何递归检查最后一级的叶节点,以确保它们左对齐吗?
迄今为止这是代码?
public boolean isComplete()
{
if (isPerfect(root))
return true;
return isComplete(root);
}
/**
*
* @param node
* @return
*/
private boolean isComplete(Node node)
{
if (height(node) > 1)
{
if (node.left != null && node.right != null && (height(node.left) == height(node.right)))
return isComplete(node.left) && isComplete(node.right);
else
return false;
}
}
PS,因为每一个完美的树中的所有琐碎的案件在isPerfect()方法处理也完全
我没有测试或运行或编译此。所以,当你的代码可能工作时,请小心一些小错误 –
,它偏离了在包装方法中只使用一个参数的要求。尽管感谢您的输入!我可以使用你给出的步骤来变出一些东西。 – sbowde4
@ sbowde4我不知道你是否注意到,包装器只使用一个参数 –