二叉树 ,你是完整的吗?
1、使用队列
2、遍历到任何一个节点,有右孩子没有左孩子直接返回false.
3、不违反2的情况下,当前节点左右两个孩子不全,标记为flag=1,从当前节点开始所有的节点均为叶子节点,即不能有孩子。若有返回false。
图片说明
1.输入
ABD###CE##F##
输出
层次遍历为:
A第1层
BC第2层
DEF第3层
不是完全二叉树
2.输入
ABD##E##C#F##
输出
层次遍历为:
A第1层
BC第2层
DEF第3层
不是完全二叉树
3.输入
ABD##E##CF##G##
输出
层次遍历为:
A第1层
BC第2层
DEFG第3层
是完全二叉树
4.输入
ABCE####D##
输出
ABCE####D##
层次遍历为:
A第1层
BD第2层
C第3层
E第4层
不是完全二叉树
typedef char TElemType;
using namespace std;
typedef struct BiTNode
{
TElemType data;//数据元素
struct BiTNode *lchild,*rchild;//左、右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,TElemType definition)
{
cin>>definition;
if(definition == '#')
{
T=NULL;
}
else
{
T=(BiTNode*)malloc(sizeof(BiTNode));
T->data=definition;
CreateBiTree(T->lchild,definition);
CreateBiTree(T->rchild,definition);
}
}
void visit(BiTNode *T)
{
cout<<T->data<<"";
}
//队列用于层次遍历
typedef struct Queue
{
BiTNode *front;//队列头指针
BiTNode *tail;//队列尾指针
int size;//队列空间大小
}Queue;
//创建队列
int InitQueue(Queue &Q)
{
Q.front = (BiTNode*)malloc(INITQUEUE * sizeof(BiTNode));
if(!Q.front)
{
return 0;
}
Q.tail = Q.front;
Q.size = INITQUEUE;
return 1;
}
//判断队列是否为空
bool EmptyQueue(Queue Q)
{
if(Q.tail == Q.front)
{
return true;
}
else
{
return false;
}
}
//入队列
int EnQueue(Queue &Q,BiTNode e)
{
if((Q.tail - Q.front + INITQUEUE) % INITQUEUE == INITQUEUE - 1)
{
return 0;
}
*Q.tail = e;
Q.tail++;
return 1;
}
//出队列
int DeQueue(Queue &Q,BiTNode &e)//用e返回元素
{
if(Q.front == Q.tail)
{
return 0;
}
e = *Q.front;
Q.front++;
return 1;
}
//判断是否为完全二叉树
bool IfCompBinTree(BiTree T)//1是完全二叉树,0不是完全二叉树
{
if(T==NULL)
{
return true;
}
Queue Q1;
InitQueue(Q1);
BiTNode *ch;
ch = new BiTNode;
EnQueue(Q1,*T);
int flag=0; //标记 没有孩子或右孩子为空
while(!EmptyQueue(Q1))
{
DeQueue(Q1,*ch);
if(ch->lchild==NULL&&ch->rchild!=NULL)//左孩子空
{
return false;
}
if(flag==1&&(ch->lchild!=NULL||ch->rchild!=NULL))//前面的兄弟是叶子或没有右孩子,自己有孩子
{
return false;
}
if(ch->lchild==NULL||ch->rchild==NULL)//叶子或右孩子为空,后面的兄弟不能有孩子
{
flag=1;
}
if(ch->lchild!=NULL)//把孩子拉进来
{
EnQueue(Q1,*ch->lchild);
}
if(ch->rchild!=NULL)
{
EnQueue(Q1,*ch->rchild);
}
}
return true;
}
//层次遍历
void LevelOrderTraverse(BiTree T)
{
if(T==NULL)
{
cout<<"LevelOrderTraverse NULL"<<endl;
}
else
{
BiTNode *e;
e = new BiTNode;
Queue Q;
InitQueue(Q);
EnQueue(Q,*T);
int dep=0;//计数
int curcount=1;//本层未访问节点数量
int nextcount=0;//下一层节点数量
while(!EmptyQueue(Q))//队列不为空
{
DeQueue(Q,*e);
visit(e);
curcount--;
if(e->lchild!=NULL)
{
EnQueue(Q,*e->lchild);
nextcount++;
}
if(e->rchild!=NULL)
{
EnQueue(Q,*e->rchild);
nextcount++;
}
if(curcount==0)
{
dep++;
cout<<"第"<<dep<<"层"<<endl;
curcount=nextcount;//下一层
nextcount=0;
}
}
}
}
int main()
{
BiTree T=NULL;
TElemType d,c;
cout<<"请输入树的元素:"<<endl;
CreateBiTree(T,d);
cout<<"层次遍历为:"<<endl;//输出检查
LevelOrderTraverse(T);
cout<<endl;
if(IfCompBinTree(T))
{
cout<<"是完全二叉树"<<endl;
}
else
{
cout<<"不是完全二叉树"<<endl;
}
system("pause");
}
时间复杂度为O(n)