202649.cpp

数据结构（清华版）

#include<iostream.h>
typedef char TElemtype;

//创建结构体==================================================================
typedef struct BiTNode
{
	TElemtype data;
	BiTNode *lchild,*rchild,*parent;
} *BiTree;

//先序序列创建二叉数==========================================================
void CreateBiTree(BiTree &T,char s[],int &i)
{
	i++;
	if(s[i]=='#') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=s[i];
		CreateBiTree(T->lchild,s,i);
		CreateBiTree(T->rchild,s,i);
	}
}
//用于调用的创建二叉树函数======================================================
void CreateBiTree(BiTree &T,char s[])
{
	int i=-1;
	CreateBiTree(T,s,i);
}



//创建链队列结构体===================================================================
typedef BiTree QElemtype;
typedef struct QNode
{
	QElemtype data;QNode *next;
} *LQueuePtr;
struct LQueue
{
	LQueuePtr front,rear;
};
void QueueInit(LQueue &Q)
{
	Q.front=new QNode;
	Q.front->next=NULL;
	Q.rear=Q.front;
}
//创建入列函数======================================================================
void Enqueue(LQueue &Q,QElemtype e)
{
    LQueuePtr p;
	p=new QNode;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
//创建出队函数======================================================================
bool Dequeue(LQueue &Q,QElemtype &e)
{
	LQueuePtr p;
	if (Q.front==Q.rear) return false;
	p=Q.front;
	Q.front=p->next;
	e=Q.front->data;
	delete p;
	return true;
}
//创建函数判断是否为完全二叉树======================================================
bool LookBiTree(BiTree T)
{
	LQueue q;
	if(!T) return true; 
	bool x;
	QueueInit(q);
	Enqueue(q,T);
	while(Dequeue(q,T))
	{
		if(!x&&(T->lchild||T->rchild))	return false;
		if(T->rchild)Enqueue(q,T->rchild);
		else x=false;
		if(T->lchild)Enqueue(q,T->lchild);
		else x=false; 
	}
	return true;


}
//主函数===========================================================================
void  main()
{
	BiTree T;
	TElemtype s[]={'A','B','D','#','#','#','C','E','#','F','#','#','#'};
	CreateBiTree(T,s);
	if (LookBiTree(T)) cout<<"此二叉树是完全二叉树"<<endl;
	else cout<<"此二叉树不是完全二叉树"<<endl;
}