一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
一棵深度为k且有
个结点的二叉树称为满二叉树。根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有
个结点 (i≥1) 。如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。
1、具有n个结点的完全二叉树的深度
（注：表示向下取整）2、如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有:
如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点.如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i;如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1.完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
判断一棵树是否是完全二叉树的思路
1>如果树为空，则直接返回错
2>如果树不为空：层序遍历二叉树
2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；
#include <iostream>#include <queue>using namespace std;template <class T>struct TreeNode{ T data; TreeNode<T> *left; TreeNode<T> *right; TreeNode(const T &x) : data(x), left(NULL), right(NULL) {}};template <class T>bool IsComplete(TreeNode<T> *root){ //1.树为空，返回错误 if (root == NULL) { return false; } //2.树不为空 queue<TreeNode<T> *> q; q.push(root); while (!q.empty()) { TreeNode<T> *top = q.front(); //2.1如果该节点两个孩子都有，则直接pop if (top->left && top->right) { q.pop(); q.push(top->left); q.push(top->right); } //2.2如果该节点左孩子为空，右孩子不为空，则一定不是完全二叉树 if (top->left == NULL && top->right) { return false; } //2.3如果该节点左孩子不为空，右孩子为空或者该节点为叶子节点，则该节点之后的所有结点都是叶子节点 if ((top->left && top->right == NULL) || (top->left == NULL && top->right == NULL)) { if (NULL != top->left && NULL == top->right) { q.push(top->left); } q.pop(); //则该节点之后的所有结点都是叶子节点 while (!q.empty()) { top = q.front(); if (top->left == NULL && top->right == NULL) { q.pop(); } else { return false; } } return true; } } return true;}//满二叉树void test1(){ // 1 // 2 3 // 4 5 6 7 TreeNode<int> *node1 = new TreeNode<int>(1); TreeNode<int> *node2 = new TreeNode<int>(2); TreeNode<int> *node3 = new TreeNode<int>(3); TreeNode<int> *node4 = new TreeNode<int>(4); TreeNode<int> *node5 = new TreeNode<int>(5); TreeNode<int> *node6 = new TreeNode<int>(6); TreeNode<int> *node7 = new TreeNode<int>(7); node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->left = node6; node3->right = node7; cout << IsComplete<int>(node1) << endl;}//二叉树为空void test2(){ cout << IsComplete<int>(NULL) << endl;}//3.二叉树不为空，也不是满二叉树，遇到一个结点左孩子为空，右孩子不为空void test3(){ // 1 // 2 3 // 4 5 7 TreeNode<int> *node1 = new TreeNode<int>(1); TreeNode<int> *node2 = new TreeNode<int>(2); TreeNode<int> *node3 = new TreeNode<int>(3); TreeNode<int> *node4 = new TreeNode<int>(4); TreeNode<int> *node5 = new TreeNode<int>(5); TreeNode<int> *node7 = new TreeNode<int>(7); node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->right = node7; cout << IsComplete<int>(node1) << endl;}//4.二叉树不为空，也不是满二叉树，遇到叶子节点,则该叶子节点之后的所有结点都为叶子节点void test4(){ // 1 // 2 3 // 4 5 TreeNode<int> *node1 = new TreeNode<int>(1); TreeNode<int> *node2 = new TreeNode<int>(2); TreeNode<int> *node3 = new TreeNode<int>(3); TreeNode<int> *node4 = new TreeNode<int>(4); TreeNode<int> *node5 = new TreeNode<int>(5); node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; cout << IsComplete<int>(node1) << endl;}//4.二叉树不为空，也不是满二叉树，遇到左孩子不为空，右孩子为空的结点，则该节点之后的所有结点都为叶子节点void test5(){ // 1 // 2 3 // 4 5 6 TreeNode<int> *node1 = new TreeNode<int>(1); TreeNode<int> *node2 = new TreeNode<int>(2); TreeNode<int> *node3 = new TreeNode<int>(3); TreeNode<int> *node4 = new TreeNode<int>(4); TreeNode<int> *node5 = new TreeNode<int>(5); TreeNode<int> *node6 = new TreeNode<int>(6); node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->left = node6; cout << IsComplete<int>(node1) << endl;}int main(){ test1(); return 0;}
温馨提示：