【数据结构】判断一棵树是否为完全二叉树

雨点打透心脏的1/2处 2022-06-11 03:51 187阅读 0赞

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

判断一棵树是否为完全二叉树，有以下几种情况：

（1），倒数第二层不是满二叉树；

（2），最后一层从左往右不是连续的有节点；

（3），最后一层从左到右一次又节点。

使用队列的方法来进行判断一棵树是否为完全二叉树：

用代码实现：

#include<iostream>
    using namespace std;
    #include<queue>
    struct TreeNode
    {
    	int _value;
    	TreeNode* _left;
    	TreeNode* _right;
    };
    bool IsCompleeTree(TreeNode* _root)
    {
    	if (_root == NULL)
    	{
    		return false;
    	}
    	queue<TreeNode*> q;
    	q.push(_root);
    	bool flag = false;//用来标志是否为满结点，也就是完全二叉树
    	while (!q.empty())//当队列不为空的时候
    	{
    		TreeNode* cur = q.front();
    		q.pop();
    		if (flag)//flag==true，即已经出现过满结点的时候
    		{
    			//cur结点的左子树或者右子树不为空，一定不是完全二叉树
    			if (cur->_left != NULL || cur->_right != NULL)
    			{
    				return false;
    			}
    		}
    		//没有出现过满结点
    		else
    		{
    			if (cur->_left != NULL&&cur->_right != NULL)
    			{
    				q.push(cur->_left);
    				q.push(cur->_right);
    			}
    			//左子树为空，右子树不为空。一定不是完全二叉树
    			else if (cur->_left == NULL&&cur->_right != NULL)
    			{
    				return false;
    			}
    			//左子树不为空，右子树为空
    			else if (cur->_left != NULL&&cur->_right == NULL)
    			{
    				q.push(cur->_left);
    				flag = true;
    			}
    			//左子树和右子树都为空，则为完全二叉树
    			else
    			{
    				flag = true;
    			}
    		}
    	}
    	return true;
    }