数据结构之判断一棵树是不是完全二叉树

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,  

 

上一篇:Codeforces 834D The Bakery【dp+线段树维护+lazy】


下一篇:Java NIO 之 Buffer(缓冲区)