判别二叉树是否为完全二叉树算法

可以使用广度优先搜索（BFS）来判别二叉树是否为完全二叉树。

具体步骤如下：
1. 从根节点开始，按照层次顺序依次将二叉树中的节点加入队列。
2. 如果当前节点有左子节点但没有右子节点，那么该二叉树不是完全二叉树。
3. 如果当前节点没有左子节点但有右子节点，那么该二叉树不是完全二叉树，并且后续所有节点都应该是叶子节点。
4. 如果当前节点既有左子节点又有右子节点，那么将左子节点和右子节点加入队列。
5. 重复以上步骤，直到队列为空或者发现非完全二叉树。

如果二叉树经过以上步骤后没有发现非完全二叉树，那么该二叉树是完全二叉树。

相关问题

编写算法判别给定二叉树是否为完全二叉树。

### 回答1：
判断一棵二叉树是否为完全二叉树的算法如下：

1. 如果二叉树为空，则是完全二叉树。

2. 如果二叉树不为空，但是左子树为空，右子树不为空，则不是完全二叉树。

3. 如果二叉树不为空，但是左子树不为空，右子树为空，则只有当左子树为叶子节点或者是满二叉树时，才是完全二叉树。

4. 如果二叉树不为空，左右子树都不为空，则需要递归判断左右子树是否为完全二叉树。

5. 如果左右子树都是完全二叉树，且左子树的高度等于右子树的高度或者左子树的高度比右子树的高度小1，则该二叉树是完全二叉树，否则不是完全二叉树。

以上就是判断一棵二叉树是否为完全二叉树的算法。

### 回答2：
一棵完全二叉树的特点有：

1. 如果树的深度为d，除了第d层，其他各层的节点数都达到了最大个数，第d层所有的节点都连续集中在最左边；

2. 如果该树的右子树不为空，那么右子树的每个节点都必须具有两个子节点，否则该树不是完全二叉树。

基于这两个特点，我们可以设计算法来判定一棵二叉树是否为完全二叉树。

首先，我们需要用广度优先搜索(BFS)来遍历这棵二叉树。从根节点出发，按照从上到下、从左到右的顺序，依次访问每个节点。如果当前节点有左子节点但没有右子节点，那么该树不是完全二叉树。因为在完全二叉树中，如果一个节点有左子节点却没有右子节点，那么该节点的右边所有节点都必须不存在。

如果当前节点有右子节点但没有左子节点，或者左右子节点都不存在，那么它以后的所有节点都必须是叶子节点，否则该树也不是完全二叉树。因为在完全二叉树中，如果一个节点存在右子节点却不存在左子节点，或者左右子节点都不存在，那么该节点的左边节点应该达到最大个数，而其右边节点都不存在。

最后，如果BFS遍历完整棵树，都没有遇到以上两种情况，那么该树是完全二叉树。

算法的核心是用BFS遍历整个树，时间复杂度为O(n)，其中n为节点数目。因此，该算法是高效的，可以在不占用过多空间的情况下(空间复杂度为O(n))快速判定一棵树是否为完全二叉树。

### 回答3：
什么是完全二叉树

在二叉树中，如果所有的叶子节点都出现在最后一层或者倒数第二层，并且最后一层的叶子节点都集中在左边，那么这棵二叉树就是完全二叉树。

如何判断一棵二叉树是否为完全二叉树

在判断完全二叉树时，我们可以使用以下的算法：

1.首先，我们需要计算出树的总结点数。

2.接着，我们需要遍历二叉树的每个节点，逐一进行如下的判断：

• 如果一个节点的序号等于n，那么它的左节点的序号为2n，右节点的序号为2n+1。

• 如果当前节点的序号等于n，但是它的左节点或右节点的序号大于总结点数，那么它就不是完全二叉树。

• 如果当前节点的左节点为null，但是右节点不为null，那么它也不是完全二叉树。

3.如果二叉树中的所有节点都满足以上条件，则这棵二叉树为完全二叉树。

代码实现

以下是一个Java实现的示例代码：

public boolean isComplete(TreeNode root) {
if (root == null) {
return true;
}
int nodes = DFS(root, 1);
return DFS2(root, nodes, 1);
}

private int DFS(TreeNode node, int index) {
if (node == null) {
return index - 1;
}
int left = DFS(node.left, 2 * index);
int right = DFS(node.right, 2 * index + 1);
return left > right ? left : right;
}

private boolean DFS2(TreeNode node, int nodes, int index) {
if (node == null) {
return true;
}
if (index > nodes) {
return false;
}
return DFS2(node.left, nodes, 2 * index) && DFS2(node.right, nodes, 2 * index + 1);
}

其中，DFS函数用于计算树的总结点数，DFS2用于判断二叉树是否为完全二叉树。这个算法的时间复杂度为O(N)，其中N为二叉树节点的数量。

编写一算法，判别给定二叉树是否为完全二叉树

### 回答1：
要判断一个二叉树是否为完全二叉树，可以按照层次遍历的顺序，从上到下、从左到右进行遍历，遍历到某个节点时，如果该节点有右子树但没有左子树，则不是完全二叉树。如果遍历到某个节点时，该节点不是左右子树都存在或者只有左子树不存在，则该二叉树也不是完全二叉树。只有在上述情况都不存在时，才是完全二叉树。

### 回答2：
二叉树是一种特殊的数据结构，由根节点、左子树和右子树组成。完全二叉树是一种特殊的二叉树，其中除了最后一层外，每个节点都有左右子树，最后一层节点从左到右连续排列。编写一种算法，可以用于检查给定的二叉树是否为完全二叉树。该算法的思路如下：

确定二叉树的深度和节点数。使用递归算法遍历二叉树，计算出二叉树的深度和节点数。由于完全二叉树的节点数是2的深度次方减一，因此如果节点数不等于2的深度次方减一，则该二叉树不是完全二叉树。

检查层序遍历顺序。对于完全二叉树，它的最后一层节点必须从左到右按顺序排列，因此可以使用层序遍历算法遍历整个二叉树，检查最后一层节点的排列是否正确。如果某个节点只有左子树或者没有子树，则它必须是最后一层节点的最后一个。

根据以上算法，我们可以编写一个判别给定二叉树是否为完全二叉树的函数。函数的伪代码如下：

def is_complete_binary_tree(root):
depth = 0
count = 0
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not queue:
depth += 1
if count != 2**depth - 1:
return False
queue.clear()
queue.append(root)
last_level = False
while queue:
node = queue.pop(0)
if last_level and (node.left or node.right):
return False
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not node.left or not node.right:
last_level = True
return True

最后，我们可以通过实例化一些二叉树节点，调用上述函数来测试是否是完全二叉树。

### 回答3：
完全二叉树是指除了最后一层节点可能不满之外，其他每层节点都必须达到最大数量的二叉树。判断给定二叉树是否为完全二叉树需要按照如下步骤：

1. 从根节点开始，进行层次遍历，遍历每个节点；
2. 对于每个节点，判断是否有右子节点但无左子节点，如果是，则说明不是完全二叉树；
3. 如果节点没有左右子节点，或仅有左子节点，则后续节点必须全部为叶子节点；
4. 如果以上情况都不符合，则说明该二叉树为完全二叉树。

简单来说，完全二叉树的定义很特殊，需要遍历整棵树进行判断。具体实现可以使用队列完成，每次将节点的左右子节点加入队列，并比较当前节点是否满足完全二叉树的性质，如果不满足则直接返回false，如果遍历完整棵树则说明该二叉树为完全二叉树，返回true。

针对C++语言，可以参考代码如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isCompleteTree(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q{{root}};
    bool end = false;
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            auto t = q.front(); q.pop();
            if (t->left) {
                if (end) return false;
                q.push(t->left);
            } else {
                end = true;
            }
            if (t->right) {
                if (end) return false;
                q.push(t->right);
            } else {
                end = true;
            }
        }
    }
    return true;
}