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

判断二叉树是否为完全二叉树的算法可以通过层次遍历的方式实现。具体操作是从根节点开始进行层次遍历，当遇到一个节点的左子节点为空时，如果它的右子节点不为空，那么这棵二叉树就不是完全二叉树。如果遇到一个节点的左子节点或右子节点为空，那么它之后的所有节点都必须是叶子节点，否则这棵二叉树就不是完全二叉树。如果整个遍历过程都没有发现异常，那么这棵二叉树就是完全二叉树。

相关问题

判断二叉树是否为完全二叉树算法代码

好的，下面是用 Python 语言实现的判断二叉树是否为完全二叉树的算法代码：

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_complete_tree(root):
    if not root:
        return True
    queue = [root]
    flag = False
    while queue:
        node = queue.pop(0)
        if node.left:
            if flag:
                return False
            queue.append(node.left)
        else:
            flag = True
        if node.right:
            if flag:
                return False
            queue.append(node.right)
        else:
            flag = True
    return True

这个算法基于 BFS（宽度优先搜索）遍历二叉树的思想，判断每个节点是否合法。这里的关键在于如何判断某个节点是否合法，即是否满足完全二叉树的条件。具体来说，在遍历每个节点的时候，如果该节点有左子树或右子树，而且在前面的遍历中有某个节点没有左子树或右子树，则该节点不合法，不满足完全二叉树的条件。

希望这个算法能够解决您的问题。如果您还有其他问题，欢迎继续询问！

判断二叉树是否为完全二叉树算法c语言代码

好的，我会保密的。下面是判断二叉树是否为完全二叉树的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 检查二叉树是否为完全二叉树
bool isCompleteTree(TreeNode* root) {
    if (!root) {
        return true;
    }
    
    // 定义一个队列
    struct Queue {
        TreeNode* node;
        int idx;
    }* q = NULL;
    int front = 0, rear = 0;
    
    // 先把根节点入队
    q = (struct Queue*) malloc(sizeof(struct Queue));
    q[rear++] = (struct Queue) {root, 1};
    
    while (front < rear) {
        // 队首节点出队
        struct Queue cur = q[front++];
        TreeNode* node = cur.node;
        int idx = cur.idx;
        
        // 如果队首节点的编号不等于当前二叉树节点数，说明不是完全二叉树
        if (idx != front) {
            return false;
        }
        
        // 如果有左子节点，则把左子节点入队
        if (node->left) {
            q = (struct Queue*) realloc(q, sizeof(struct Queue) * (rear + 1));
            q[rear++] = (struct Queue) {node->left, idx * 2};
        }
        
        // 如果有右子节点，则把右子节点入队
        if (node->right) {
            q = (struct Queue*) realloc(q, sizeof(struct Queue) * (rear + 1));
            q[rear++] = (struct Queue) {node->right, idx * 2 + 1};
        }
    }
    
    // 遍历完整棵树后没有问题，说明是完全二叉树
    return true;
}

// 测试
int main() {
    TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*) malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = (TreeNode*) malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->right = (TreeNode*) malloc(sizeof(TreeNode));
    root->left->right->val = 5;
    root->right = (TreeNode*) malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*) malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    //root->right->right = (TreeNode*) malloc(sizeof(TreeNode));
    //root->right->right->val = 7;
    bool res = isCompleteTree(root);
    printf("%d", res);
    return 0;
}

该算法使用队列进行广度优先搜索，遍历整个二叉树，同时用一个编号变量 `idx` 记录每个节点在二叉树中的位置编号。遍历完整棵树后如果没有问题，说明这是一棵完全二叉树。