如何确定二叉树是否完整？

Question

完整的二叉树被定义为二叉树,其中除了可能是最深的之外,每个级别都被完全填充.在最深层,所有节点必须尽可能远.

我认为一个简单的递归算法将能够判断给定的二叉树是否完整,但我似乎无法弄明白.

Answer 1

相近:

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right))

你有:

perfect(t) = if (t==NULL) then 0 else { 
                  let h=perfect(t.left)
                  if (h != -1 && h==perfect(t.right)) then 1+h else -1
             }

如果叶子不是全部在同一深度,或者任何节点只有一个孩子,则perfect(t)返回-1; 否则,它返回高度.

编辑:这是为了"完整"="一个完美的二叉树是一个完整的二叉树,其中所有叶子处于相同的深度或相同的水平.1(这被模糊地称为完整的二叉树.)"(维基百科).

这是一个递归检查:"一个完整的二叉树是一个二叉树,其中除了可能是最后一个级别之外,每个级别都被完全填充,所有节点都尽可能地离开." 如果树不完整则返回(-1,false),否则(高度,满)如果是,则为full == true如果它是完美的.

complete(t) = if (t==NULL) then (0,true) else { 
                  let (hl,fl)=complete(t.left)
                  let (hr,fr)=complete(t.right)                      
                  if (fl && hl==hr) then (1+h,fr)
                  else if (fr && hl==hr+1) then (1+h,false)
                  else (-1,false)
              }