一棵深度为k且有
根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。 [2]
完全二叉树 [2]1、具有n个结点的完全二叉树的深度
- 如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点[i/2]. [2]
- 如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i; [2]
- 如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1. [2]
完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。 [1]
判断一棵树是否是完全二叉树的思路 [3]
1>如果树为空，则直接返回错
2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树； [3]
#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();
/*test2();*/
/*test3();*/
/*test4();*/
/*test5();*/
return 0;
}
