判断一棵二叉树是否为完全二叉树算法

#include "stdafx.h"
#include "iostream"
#define Max 100
using namespace std;

typedef struct Node
{ char data;
struct Node * LChild,*RChild;}BiTNode,*BiTree;

void CreateBiTree(BiTree * bt)
{
char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
* bt=(BiTree)malloc(sizeof(BiTNode));
(* bt)->data=ch;
CreateBiTree(&((* bt)->LChild));
CreateBiTree(&((* bt)->RChild));
}
}

int fullBiTree(BiTree b)
{ //complete binary tree：完全二叉树
//full：满
BiTree queue[Max],p;
int first=0,rear=0,bj=1,cm=1;
if(b!=NULL)
{
rear++;
queue[rear]=b;
while(first!=rear)
{
first++;
p=queue[first];
if(p->LChild==NULL)
{
bj=0;
if(p->RChild!=NULL) cm=0;
}
else
{
cm=bj;
rear++;queue[rear]=p->LChild;
if(p->RChild==NULL) bj=0;
else
{
rear++;
queue[rear]=p->RChild;
}
}
}
return cm;
}
return 1;
}

int main(int argc, char* argv[])
{
cout<<"请依次输入字符ABCO..UMJKL.EDC....."<BiTree b;
CreateBiTree(&b);
int cm=fullBiTree(b);
if(cm)cout<<"此二叉树为完全二叉树"<else cout<<"此二叉树不是完全二叉树"<
return 0;
}

假设为完全二叉树
找到第一个非叶子结点，判断其是否是只有左孩子或左右孩子都有。
此后判断其前面的结点是否都有左右孩子。

根据深度进行判断,进行bfs,根节点的深度为1,则除了最深的节点外,其他节点的数量为2^(深度-1)