数据结构与算法----2.5 判断二叉树是否为完全二叉树

[c++]代码库

#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
	BiTNode *lc,*rc;
}*BiTree;
typedef BiTree QElemType;
typedef struct QNode
{
	QElemType data;	QNode *next;
}*LQueuePtr;
struct LQueue{ LQueuePtr front,rear;};

void CreateBiTree(BiTree &T,char s[]);//带有空子树信息的先序建立二叉树
void CreateBiTree(BiTree &T,char s[],int &i);
void BiTreeLists(BiTree &T);//广义表形式
bool SheerBiTree(BiTree T);//判断二叉树是否为完全二叉树
void QueueInit(LQueue &Q);//队初始化
void Enqueue(LQueue &Q,QElemType e);//入队
bool Dequeue(LQueue &Q,QElemType &e);//出队

int main()
{
	BiTree T1,T2;char s1[]="ABXE##F##D##CXH##X##G##";char s2[]="X##";
	CreateBiTree(T1,s1);CreateBiTree(T2,s2);
	cout<<"二叉树(广义表形式)为：";
	BiTreeLists(T1);
	cout<<endl;
	if(SheerBiTree(T1))
		cout<<"此二叉树是完全二叉树!"<<endl;
	else
		cout<<"此二叉树不是完全二叉树!"<<endl;
	cout<<"二叉树(广义表形式)为：";
	BiTreeLists(T2);
	cout<<endl;
	if(SheerBiTree(T2))
		cout<<"该二叉树是完全二叉树!"<<endl;
	else
		cout<<"该二叉树不是完全二叉树!"<<endl;
	return 0;
}
void CreateBiTree(BiTree &T,char s[],int &i)
{
	i++;
	if(s[i]=='#'){T=NULL;return;}
	T=new BiTNode; T->data=s[i];
	CreateBiTree(T->lc,s,i);
	CreateBiTree(T->rc,s,i);
}
void CreateBiTree(BiTree &T,char s[])
{
	int i=-1;
	CreateBiTree(T,s,i);
}
void BiTreeLists(BiTree &T)
{
	if(!T) {cout<<'#';return;}
	cout<<T->data;
	if(T->lc ||T->rc)
	{
		cout<<'(';
		BiTreeLists(T->lc);
		cout<<',';
		BiTreeLists(T->rc);
		cout<<')';
	}
}
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 SheerBiTree(BiTree T)
{
	LQueue q;BiTree p;
	if(!T)return true;
	QueueInit(q);Enqueue(q,T);
	bool SHEER=false;
	while(Dequeue(q,p))
	{
		if(!p){SHEER=true;}
		else if(SHEER){return false;}
		else{
			Enqueue(q,p->lc);
			Enqueue(q,p->rc);
		}
	}
	return true;	
}