完全二叉树：一棵具有N个节点的二叉树的结构与满二叉树的前N个节点的结构相同

如何判断一个树是完全二叉树

可以使用层序遍历，只需2个步骤

第一步：如果遍历到一个节点只有右子树没有左子树，则不是完全二叉树

第二部：如果遍历到一个节点只有左子树，那么后面遍历到的节点必须是叶子节点，否则也不是完全二叉树

排除以上两种情况，则树是完全二叉树

核心代码：

//层序遍历
int LayerOrder(BiTreeNode *head)
{
	bool flag=0;
	LQueue Q;
	Initiate_Queue(&Q);
	BiTreeNode *p;
	if(head!=NULL) AppendQueue(&Q,head);
	while(QueueNotEmpty(&Q))
	{
		if(flag)
		{
			if(p->LChild!=NULL || p->RChild!=NULL) 
				return 0;
		}
		p=QueueDelete(&Q);
		if(p->LChild!=NULL) AppendQueue(&Q,p->LChild);
		if(p->RChild!=NULL) AppendQueue(&Q,p->RChild);	
		if((p->LChild==NULL) && (p->RChild!=NULL)) return 0;  //如果左子树为空，右子树存在，则不是完全2叉树
        //如果左子树存在，右子树为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
		if(p->LChild!=NULL &&p->RChild==NULL) flag=1; 
		//如果左子树，右子树都为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
		if(p->LChild==NULL && p->RChild==NULL) flag=1;
		
	}
	return 1;
}

完整代码如下：

#include<iostream>
using namespace std;

typedef struct biTreeNode
{
	char data;
	struct biTreeNode *LChild;
	struct biTreeNode *RChild;
}BiTreeNode;


void Initiate_Tree(BiTreeNode **head)
{
	(*head)=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	(*head)->LChild=NULL;
	(*head)->RChild=NULL;
}

 BiTreeNode *InsertLChild(BiTreeNode *head,char x)
{
	if(head==NULL) return NULL;
	else
	{
	BiTreeNode *p1,*p2;
	p1=head->LChild;
	p2=(BiTreeNode*)malloc(sizeof(BiTreeNode));
	p2->data=http://www.mamicode.com/x;>

编程判断一个树是完全二叉树（使用层次遍历实现）