利用c++实现判别给定二叉树是否为完全二叉树并在主函数测试输出

在C++中，我们可以使用递归的方式来判断一个二叉树是否为完全二叉树。完全二叉树是一种特殊的二叉树，除了最后一层外，每一层都尽可能地填满，且最后一层的所有节点都在左边。

首先，我们需要定义一个二叉树结点的数据结构：

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

然后，我们可以编写一个辅助函数`isFullBinaryTreeHelper`来进行深度优先搜索（DFS），并判断当前节点是否满足完全二叉树的条件：

bool isFullBinaryTreeHelper(TreeNode* root, int level) {
    if (root == nullptr) {
        return true; // 空树或者到达最后一层都是完全二叉树
    }
    
    // 如果当前节点不是左孩子，并且它的右孩子存在，说明不符合完全二叉树规则
    if (level > 0 && root->left != nullptr && root->right == nullptr) {
        return false;
    }
    
    // 检查左右孩子的高度差是否大于1，如果不是，则继续递归检查下一层
    bool leftIsFull = (root->left == nullptr || isFullBinaryTreeHelper(root->left, level + 1));
    bool rightIsFull = (root->right == nullptr || isFullBinaryTreeHelper(root->right, level + 1));
    
    return leftIsFull && rightIsFull;
}

最后，在主函数`main`中创建一个示例二叉树，然后调用这个函数判断它是否为完全二叉树：

int main() {
    // 创建一个二叉树实例...
    TreeNode* root = ...;

    // 判断是否为完全二叉树
    bool isFull = isFullBinaryTreeHelper(root, 0);
    std::cout << "The binary tree is a complete binary tree: " << (isFull ? "Yes" : "No") << std::endl;

    return 0;
}

在`main`中你需要根据实际的二叉树构建情况填充`root`变量。如果需要创建特定的二叉树用于测试，你可以自己构造，比如使用数组模拟层次遍历。完成上述代码后，运行程序，它将输出该二叉树是否为完全二叉树的结果。