二叉树:完全二叉树判断c++

判断一棵二叉树是否为完全二叉树可以通过遍历节点并进行判断，以下是一个基于BFS（广度优先搜索）的C++代码实现：

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

bool isCompleteBT(Node* root) {
    if (root == nullptr) return true;
    queue<Node*> q;
    q.push(root);
    bool flag = false; // 标识是否出现过NULL节点
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        if (cur == nullptr) {
            flag = true;
        } else {
            if (flag) return false;
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    if (isCompleteBT(root)) {
        cout << "This is a complete binary tree" << endl;
    } else {
        cout << "This is not a complete binary tree" << endl;
    }
    return 0;
}

在上述代码中，我们使用了一个队列来存储待遍历的节点，遍历过程中，如果遇到了一个NULL节点，则将标识flag设为true，如果之后还遇到了非NULL节点，就说明这棵树不是完全二叉树，直接返回false即可。如果遍历完成后仍然没有返回false，则说明这棵树是完全二叉树，返回true即可。