数据结构之判断一棵树是不是完全二叉树
1 完全二叉树
完全二叉树是由 满二叉树 而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
如下就是完全二叉树
-
1
-
2 3
-
4 5 6 7
如下就是完全二叉树
-
1
-
2 3
-
4 5
如下不是完全二叉树
-
1
-
2 3
-
4 5 7
2 分析
判断一颗二叉树是不是完全二叉树，我们用层遍历数（这里需要用到队列）
1）如果根节点为NULL, 返回false，不是的话，我们queue把根节点push到里面去，然后在放到queue大小不为空的循环里面，进行queue.front()操作得到节点。
2）如果节点的左叶子是空，右叶子节点不是空，直接返回false。
3）如果节点的左叶子不是空，右叶子节点不是空，我们分别把左右叶子节点压去queue,同时pop出最前面的元素。
4）如果遇到一个结点，左叶子不为空，右叶子为空；或者左右叶子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树
3 代码实现
-
#include <iostream>
-
#include <queue>
-
-
using namespace std;
-
-
typedef struct Tree
-
{
-
int value;
-
struct Tree* left;
-
struct Tree* right;
-
Tree(int value):value(value), left(NULL), right(NULL){}
-
} Tree;
-
-
-
bool isCompleteTree(Tree* node)
-
{
-
if (node == NULL)
-
return false;
-
queue<Tree *> queue;
-
queue.push(node);
-
while (!queue.empty())
-
{
-
Tree *pNode = queue.front();
-
//左叶子是空，右叶子节点不是空
-
if (pNode->left == NULL && pNode->right != NULL)
-
return false;
-
//左叶子不是是空，右叶子节点不是空
-
if (pNode->left != NULL && pNode->right != NULL)
-
{
-
queue.pop();
-
queue.push(pNode->left);
-
queue.push(pNode->right);
-
}
-
//左叶子不为空，右叶子为空；或者左右叶子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树
-
if ((pNode->left == NULL && pNode->right == NULL) || (pNode->left != NULL && pNode->right == NULL))
-
{
-
if (pNode->left != NULL && pNode->right == NULL)
-
{
-
queue.push(pNode->left);
-
}
-
queue.pop();
-
while (!queue.empty())
-
{
-
Tree* node = queue.front();
-
if (node->left == NULL && node->right == NULL)
-
{
-
queue.pop();
-
}
-
else
-
{
-
std::cout << "false...." << std::endl;
-
return false;
-
}
-
}
-
return true;
-
}
-
}
-
return true;
-
}
-
-
-
int main()
-
{
-
Tree node1(1);
-
Tree node2(2);
-
Tree node3(3);
-
Tree node4(4);
-
Tree node5(5);
-
Tree node6(6);
-
Tree node7(7);
-
node1.left = &node2;
-
node1.right = &node3;
-
node2.left = &node4;
-
node2.right = &node5;
-
node3.left = &node6;
-
node3.right = &node7;
-
std::string res = "";
-
res = (isCompleteTree(&node1) == 1) ? "true" : "false";
-
std::cout << "Tree isFullTree is " << res << std::endl;
-
return 0;
-
}
4 运行结果
Tree isFullTree is true
5 总结
完全二叉树如果遇到一个结点，左叶子不为空，右叶子为空；或者左右叶子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树
完全二叉树还有这个性质，比如这个树有n个节点，那么这个树的有左右孩子节点的父节点有n / 2个，如果我们堆顶是从下标0开始的，那么n / 2个数就对于于下标0~ (n / 2 - 1),而且如果当前节点是下标i的话（有左右子节点情况），那么它的左孩子节点的下标是2*i + 1，右孩子节点下标是2 * i + 2, 如果我们堆顶是从下标1开始的，那么n / 2个数就对于于下标0~ (n / 2),而且如果当前节点是下标i的话（有左右子节点情况），那么它的左孩子节点的下标是2*i ，右孩子节点下标是2 * i + 1,
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/102774285
- 点赞
- 收藏
- 关注作者
评论（0）