利用c++代码编写算法判别给定二叉树是否为完全二叉树并在主函数测试输出

在C++中，判断一个给定的二叉树是否为完全二叉树，可以采用递归的方式来实现。完全二叉树是一种特殊的二叉树，除最后一层外，每一层都是满的，并且所有叶子节点都集中在最底层。

首先，我们需要定义一个简单的二叉树节点结构：

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

然后，我们可以创建一个辅助函数`isCompleteTree`来进行检查：

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) {
        return true; // 空树视为完全二叉树
    }
    bool isLastLevelFull = false;
    int lastNonEmptyLevel = -1;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left != nullptr || node->right != nullptr) {
                if (lastNonEmptyLevel != -1 && levelSize > lastNonEmptyLevel + 1) {
                    return false; // 找到非满层，且当前层比前一层大，不是完全二叉树
                }

                if (levelSize == 1) { // 如果这是一层并且只有一个节点，说明它可能是最后一层
                    isLastLevelFull = true;
                } else {
                    isLastLevelFull |= !node->left && !node->right;
                }
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        lastNonEmptyLevel++;
    }
    return isLastLevelFull; // 如果所有非空层都是满的，返回true
}

在主函数中，你可以构建一个示例二叉树并调用这个函数进行检测：

int main() {
    // 创建一个二叉树实例并填充数据...
    TreeNode* root = buildYourBinaryTree(); // 自行实现二叉树构造函数

    if (isCompleteTree(root)) {
        cout << "Given binary tree is a complete binary tree." << endl;
    } else {
        cout << "Given binary tree is not a complete binary tree." << endl;
    }

    delete root; // 清理内存
    return 0;
}