algorithm - 如何判断二叉树是否完整？

Question

完全二叉树被定义为一棵二叉树，其中除了可能最深的层外，每一层都被完全填满。在最深处，所有节点都必须尽可能地靠左。

我认为一个简单的递归算法将能够判断给定的二叉树是否完整，但我似乎无法弄清楚。

score 5 · Accepted Answer

如同：

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)，否则返回 (height,full)，如果它是完美的，则返回 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)
              }

score 4 · Accepted Answer

最简单的程序是：

查找树的深度（简单算法）。
计算树中的节点数（通过遍历并在访问任何节点时将计数器加一）。
对于d级的完全二叉树，节点数等于pow(2,d+1)-1。

如果条件满足树，则为完全二叉树，否则不满足。

这是一个简单的算法，如果你的编码能力足够好，将其转换为工作代码应该不是问题。

score 2 · Accepted Answer

//Helper function

int depth (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return 0;

   ld=depth(n->left);
   ld=depth(n->right);

   if (ld>rd)
      return (1+ld);
   else
      return (1+rd);

}


//Core function

int isComplete (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return TRUE;

   ld=depth(n->left);
   rd=depth(n->right);

   return(ld==rd && isComplete(n->left) && isComplete(n->right));

}

score 1 · Accepted Answer

为了一棵完整的树

高度（左）== 高度（右）或高度（左）== 1+高度（右）

    bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

score 0 · Accepted Answer

您也可以通过使用级别顺序遍历来解决此问题。程序如下：

将遇到的节点的数据元素存储在向量中
如果节点为NULL，则存储一个特殊的数字（INT_MIN）
跟踪最后访问的非空节点 - lastentry
现在遍历向量直到最后一个条目。如果您遇到过 INT_MIN，那么树是不完整的。否则它是一个完全二叉树。

这是一个C++代码：

我的树节点是：

struct node{
    int data;
    node *left, *right;
};

void checkcomplete(){//checks whether a tree is complete or not by performing level order traversal
    node *curr = root;
    queue<node *> Q;
    vector<int> arr;
    int lastentry = 0;
    Q.push(curr);
    int currlevel = 1, nextlevel = 0;
    while( currlevel){
        node *temp = Q.front();
        Q.pop();
        currlevel--;
        if(temp){
            arr.push_back(temp->data);
            lastentry = arr.size();
            Q.push(temp->left);
            Q.push(temp->right);
            nextlevel += 2;
        }else
            arr.push_back(INT_MIN);
        if(!currlevel){
            currlevel = nextlevel;
            nextlevel = 0;
        }
    }
    int flag = 0;
    for( int i = 0; i<lastentry && !flag; i++){
        if( arr[i] == INT_MIN){
            cout<<"Not a complete binary tree"<<endl;
            flag = 1;
        }
    }
    if( !flag )
        cout<<"Complete binary tree\n";
}

score 0 · Accepted Answer

private static boolean isCompleteBinaryTree(TreeNode root) {

if (root == null) {
    return false;
} else {
    boolean completeFlag = false;
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(root);
    while (!list.isEmpty()) {
        TreeNode element = list.remove(0);
        if (element.left != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.left);
        } else {
            completeFlag = true;
        }
        if (element.right != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.right);
        } else {
            completeFlag = true;
        }
    }
        return true;
    }
}

参考：查看以下链接以获取详细说明 http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

score 0 · Accepted Answer

您可以组合子树中的三条信息：

子树是否完整
最大高度
最小高度（等于最大高度或最大高度 - 1）

score 0 · Accepted Answer

我觉得可能有一种可能的算法可以解决这个问题。考虑树：

Level 0:    a  
Level 1:  b   c  
Level 2: d e f g

我们采用广度优先遍历。
对于队列中的每个入队元素，我们必须按顺序进行三项检查：
1. 如果有一个孩子或没有孩子终止；否则，请检查 2。
2. 如果两个孩子都存在，则设置全局标志 = true。
  1. 将队列中每个节点的标志设置为 true：flag[b] = flag[c] = true。
  2. 检查每个条目是否有左 n 个右子 n 然后设置标志或将它们重置为 false。
  3. (出队) if(queue_empty())
    比较所有节点标志[]...如果所有为真 global_flag = true 否则 global_flag = false。
  4. 如果 global_flag = true 继续进行下一级的广度优先遍历，否则终止

优点：可能不会遍历整个树
开销：维护标志条目

score 0 · Accepted Answer

以下代码简单地处理了所有可能的情况。沿途获得树高以避免再次递归。

enum CompleteType
{
    kNotComplete = 0,
    kComplete = 1, // Complete but not full
    kFull = 2,
    kEmpty = 3
};

CompleteType isTreeComplete(Node* node, int* height)
{
    if (node == NULL)
    {
        *height = 0;
        return kEmpty;
    }

    int leftHeight, rightHeight;

    CompleteType leftCompleteType = isTreeComplete(node->left, &leftHeight);
    CompleteType rightCompleteType = isTreeComplete(node->right, &rightHeight);

    *height = max(leftHeight, rightHeight) + 1;

    // Straight forwardly treat all possible cases
    if (leftCompleteType == kComplete && 
        rightCompleteType == kEmpty &&
        leftHeight == rightHeight + 1)
        return kComplete;

    if (leftCompleteType == Full)
    {
        if (rightCompleteType == kEmpty && leftHeight == rightHeight + 1)
            return kComplete;
        if (leftHeight == rightHeight)
        {
            if (rightCompleteType == kComplete)
                return kComplete;
            if (rightCompleteType == kFull)
                return kFull;
        }
    }

    if (leftCompleteType == kEmpty && rightCompleteType == kEmpty)
        return kFull;

    return kNotComplete;
}

bool isTreeComplete(Node* node)
{
    int height;
    return (isTreeComplete(node, &height) != kNotComplete);
}

score 0 · Accepted Answer

您可以通过比较每个节点的子节点的高度来递归地执行此操作。最多可能有一个节点，其中左孩子的高度正好比右孩子大一；所有其他节点必须完全平衡。

score 0 · Accepted Answer

感谢@Jonathan Graehl 的伪代码。我已经用Java实现了它。我已经针对迭代版本对其进行了测试。它就像一个魅力！

public static boolean isCompleteBinaryTreeRec(TreeNode root){
//      Pair notComplete = new Pair(-1, false);
//      return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);
    return isCompleteBinaryTreeSubRec(root).height != -1;
}

public static boolean isPerfectBinaryTreeRec(TreeNode root){
    return isCompleteBinaryTreeSubRec(root).isFull;
}

public static Pair isCompleteBinaryTreeSubRec(TreeNode root){
    if(root == null){
        return new Pair(0, true);
    }

    Pair left = isCompleteBinaryTreeSubRec(root.left);
    Pair right = isCompleteBinaryTreeSubRec(root.right);

    if(left.isFull && left.height==right.height){
        return new Pair(1+left.height, right.isFull);
    }

    if(right.isFull && left.height==right.height+1){
        return new Pair(1+left.height, false);
    }

    return new Pair(-1, false);
}

private static class Pair{
    int height;         
    boolean isFull;     

    public Pair(int height, boolean isFull) {
        this.height = height;
        this.isFull = isFull;
    }

    public boolean equalsTo(Pair obj){
        return this.height==obj.height && this.isFull==obj.isFull;
    }
}

score 0 · Accepted Answer

首先，计算二叉树中的节点数。写一个递归函数。如果接收到的节点为空，则返回真。如果节点的索引大于或等于节点数，则树不是二叉树。如果这两个都没有发生，请检查左右子树。导入 java.util.LinkedList；导入 java.util.Queue；

public class FBCompleteTree {

    /*
    public class TreeNode {

        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(Integer x) {
            val = x;
        }

    }
     */

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        FBCompleteTree completeTree = new FBCompleteTree();
        System.out.println(completeTree.isCompleteTree(node1));
    }

    public boolean isCompleteTree(TreeNode root) {
        int nodeCount = countNodes(root);
        // The index of the root is always zero.
        return isComplete(root, nodeCount, 0);
    }

    /**
     * Tells us if a binary tree is complete or not.
     *
     * @param node      The current node
     * @param nodeCount The node counts of the tree
     * @param index     The index of the node
     * @return If a binary tree is complete or not
     */
    private boolean isComplete(TreeNode node, int nodeCount, int index) {
    // Null is a complete binary tree
    if (node == null)
        return true;
    // In a complete binary tree, index of all the nodes should be less than nodes count.
    if (index >= nodeCount)
        return false;
    /*
    The index of the left child is 2*i+1 and the right child is 2*i+2 in a binary tree.
     */
    return isComplete(node.left, nodeCount, 2 * index + 1)
            &&
            isComplete(node.right, nodeCount, 2 * index + 2);
}

    /**
     * Counts the number of nodes.
     *
     * @param root The root of the tree
     * @return The number of nodes in the tree
     */
    private int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int counter = 0;
        while (!q.isEmpty()) {
            TreeNode currentNode = q.poll();
            counter++;
            TreeNode l = currentNode.left;
            if (l != null) {
                q.add(l);
            }
            TreeNode r = currentNode.right;
            if (r != null) {
                q.add(r);
            }
        }
        return counter;
    }

}

我希望它有所帮助。

score 0 · Accepted Answer

这是用于检查二叉树是否完整的 C 代码：

struct node
{
    int data;
    struct node * left;
    struct node * right;
};
int flag;
int isComplete(struct node *root, int depth)
{
    int ld, rd;
    if (root==NULL) return depth;
    else
    {
        ld =  isComplete(root->left,depth+1);
        rd = isComplete(root->right, depth+1);
        if (ld==-1 || rd==-1) return -1;
        else if (ld==rd) return ld;
        else if (ld==rd-1 && flag==0)
        {
            flag=1;
            return rd;
        }
        else return -1;
    }
}

它的工作方式是：

如果左子树的深度与右子树的深度相同，则返回层次结构的深度。
如果左子树的深度比右子树的深度大 1，则它返回右子树的深度向上层级并启用标志。
如果它发现左子树和右子树的深度和标志已经设置，则返回层次结构的-1。
最后，如果函数返回-1，它不是完整的子树，否则返回的值是树的最小深度。

score 0 · Accepted Answer

bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

如果您觉得有用，请考虑作为正确答案。

score -1 · Accepted Answer

您可以通过确保每个具有右孩子的节点也有一个左孩子来判断给定的二叉树是否是左完全二叉树 - 更好地称为二叉堆。见下文

bool IsLeftComplete(tree)
{

  if (!tree.Right.IsEmpty && tree.Left.IsEmpty)
    //tree has a right child but no left child, therefore is not a heap
    return false;    

  if (tree.Right.IsEmpty && tree.Left.IsEmpty)  
    //no sub-trees, thus is leaf node. All leaves are complete
    return true;

  //this level is left complete, check levels below
  return IsLeftComplete(tree.Left) && IsLeftComplete(tree.Right);
}

score -1 · Accepted Answer

int height (node* tree, int *max, int *min) {

  int lh = 0 , rh = 0 ;
  if ( tree == NULL )
    return 0;
  lh = height (tree->left,max,min) ;
  rh = height (tree->right,max,min) ;
  *max = ((lh>rh) ? lh : rh) + 1 ;
  *min = ((lh>rh) ? rh : lh) + 1 ;
  return *max ;
}

void isCompleteUtil (node* tree, int height, int* finish, int *complete) {
  int lh, rh ;
  if ( tree == NULL )
    return ;
  if ( height == 2 ) {
    if ( *finish ) {
      if ( !*complete )
        return;
      if ( tree->left || tree->right )
        *complete = 0 ;
      return ;
    }
    if ( tree->left == NULL && tree->right != NULL ) {
      *complete = 0 ;
      *finish = 1 ;
    }
    else if ( tree->left == NULL && tree->right == NULL )
      *finish = 1 ;
    return ;
  }
  isCompleteUtil ( tree->left, height-1, finish, complete ) ;
  isCompleteUtil ( tree->right, height-1, finish, complete ) ;
}

int isComplete (node* tree) {
  int max, min, finish=0, complete = 1 ;
  height (tree, &max, &min) ;
  if ( (max-min) >= 2 )
    return 0 ;
  isCompleteUtil (tree, max, &finish, &complete) ;
  return complete ;
}

algorithm - 如何判断二叉树是否完整？

16 回答 16

Related

Reference