C++ 数据结构完全二叉树的判断

关于 C++ 数据结构完全二叉树的判断，具体的步骤如下：

1. 引言

存储结构一般有顺序存储和链式存储两种方式，但是对于完全二叉树来说，最适合的存储结构就是顺序存储结构，因为完全二叉树的空节点数是比较容易计算出来的，可以通过计算来避免节省内存空间，并且完全二叉树还可以通过下标来计算某个节点的父节点和子节点的下标。

完全二叉树的性质就是：除最后一层节点外，其它各层的节点数都达到最大个数，且最后一层从左到右均有节点。

本文将深入讲解 C++ 中如何判断一棵二叉树是不是完全二叉树。

2. 判断完全二叉树的方法

2.1 遍历方法

遍历一棵二叉树的时候，按照从左到右、从上到下的顺序遍历每个节点，对于任意一个节点，如果它有右儿子但是没有左儿子，那么它一定不是完全二叉树。

示例代码如下：

bool isComplete(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool flag = false;
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if (flag) {
            if (node->left || node->right) return false;
        } else {
            if (node->left && node->right) {
                q.push(node->left);
                q.push(node->right);
            } else if (node->right) { // 右儿子非空而左儿子为空，不是完全二叉树
                return false;
            } else { // 左右儿子均为空或者左儿子非空右儿子为空，则后面遍历的节点均为叶子节点
                flag = true;
                if (node->left) {
                    q.push(node->left);
                }
            }
        }
    }
    return true;
}

2.2 层次遍历 + 标记法

类似广度优先搜索一样的做法，将节点依次压入队列，如果该节点有左儿子或右儿子，则将其左右儿子依次放入队列，如果后续的节点中出现空节点或者缺失右节点的情况，则说明这棵树不是完全二叉树，否则就是完全二叉树。

示例代码如下：

bool isComplete(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool leaf = false; // 标记是否遇到过叶子节点
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if (node->left) {
            if (leaf) return false; // 如果已经遇到过叶子节点，则左儿子非空则不是完全二叉树
            q.push(node->left);
        } else { // 如果左儿子为空，则右儿子必须为空，否则不是完全二叉树
            leaf = true;
        }
        if (node->right) {
            if (leaf) return false; // 如果已经遇到过叶子节点，则右儿子非空则不是完全二叉树
            q.push(node->right);
        } else { // 如果右儿子为空，则后面的节点必须全是叶子节点，否则不是完全二叉树
            leaf = true;
        }
    }
    return true;
}

3. 示例说明

下面一段代码可以用来构造一棵普通的二叉树，而非完全二叉树：

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right = new TreeNode(3);

这颗树用第一个方法判断的结果是 false，用第二个方法判断的结果也是 false。

下面再举一个完全二叉树的例子，这颗树每个节点都至多拥有两个子节点：

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);

这颗树用第一个方法判断的结果是 true，用第二个方法判断的结果也是 true。

以上是关于 C++ 中数据结构完全二叉树的判断的详细攻略，希望能够对大家有所帮助。