如何判断一个二叉树是否完成？ [英] How to determine whether a binary tree is complete?

问题描述

一个完整的二叉树被定义为一二进制树，其中每一个级别，可能除了最深，被完全填充。在最深层次，所有的节​​点都必须为最左。

A complete binary tree is defined as a binary tree in which every level, except possibly the deepest, is completely filled. At deepest level, all nodes must be as far left as possible.

我会想一个简单的递归算法将能够告诉给定二叉树是否是完整的，但我似乎无法弄清楚。

I'd think a simple recursive algorithm will be able to tell whether a given binary tree is complete, but I can't seem to figure it out.

推荐答案

类似的：

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
             }

其中完美（T）返回-1，如果叶子是不是都在同一深度，或任何节点只有一个孩子;否则，返回的高度。

Where perfect(t) returns -1 if the leaves aren't all at the same depth, or any node has only one child; otherwise, it returns the height.

编辑：这是完全=一个完美的二叉树是满二叉树中，所有叶子都在同一深度或同一水平[1]（这被含糊地也称为完全二叉树。）。 （维基百科）。

this is for "complete" = "A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.[1] (This is ambiguously also called a complete binary tree.)" (Wikipedia).

下面是一个递归的检查：一个完全二叉树是二叉树中，每个级别的，可能除了最后一个，是完全填满，所有的节​​点都尽量离开越好。。它返回（-1，FALSE）如果树是不完整的，否则（高度，全）如果是，以饱满的== true如果它是完美的。

Here's a recursive check for: "A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.". It returns (-1,false) if the tree isn't complete, otherwise (height,full) if it is, with full==true iff it's perfect.

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)
              }

这篇关于如何判断一个二叉树是否完成？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！