检查树是完整的二叉树

Question

我必须编写一个检查树是完整二叉树的算法（每个节点，除叶子之外，必须有2个孩子），但我不知道这个版本是否正确。

 isComplete(u) 
{
        if(u == NULL)
                return false
        else
        {
                left = isComplete(u.left);
                right = isComplete(u.right);
                complete = left && right;

                return complete.
        }
}

.

Answer 1

由于您的算法是递归，您需要考虑：

• 初始/最终案例：叶子
• 和常规案例：节点

例如，在因子的情况下：

• 初始案例 $ f（1）= 1 $
• 和常规情况是 $ f（n）= n * f（n-1）$

正式，证明它可以使用诱导的正确性。