[互联网面试笔试汇总C/C++-15] 判断一棵二叉树是否是完全搜索树-微策略 - c语言编程

首先，看一下完全二叉树的定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

思路：可以采用广度优先的遍历方法，从根节点开始将所有的节点按层添加到队列里面，当遇到第一个没有左儿子或者右儿子的节点时，设置标志位，继续遍历，如果后面遇到了有子节点的节点，则不是完全二叉树。

代码：

//二叉树结点定义  
typedef struct Node  
{  
    int data;  
    struct Node* left;  
    struct Node* right;  
}Node;  
  
  
//实现广度遍历需要队列  
Queue queue;  
  
  
//第n层最右节点标志  
bool leftMost = false;  
  
  
bool ProcessChild(Node* child)  
{  
    if (child)  
    {  
        if (!leftMost)  
            queue.push(child);  
        else  
            return false;  
    }  
    else  
    {  
        leftMost = true;  
    }  
    return true;  
}  
  
  
bool IsCompleteBinaryTree(Node* root)  
{  
    //空树也是完全二叉树  
    if (!root)  
        return true;  
  
  
    //首先根节点入队列  
    queue.push(root);  
  
    while(!queue.empty())  
    {  
        Node* node = queue.pop();  
  
        //处理左节点  
        if (!ProcessChild(node->




left))  
            return false;  
  
        //处理右节点  
        if (!ProcessChild(node->right))  
            return false;  
    }  
  
    //广度优先遍历完毕，此乃完全二叉树  
    return true;  
}