编写算法判别给定二叉树是否为完全二叉树

1、名称：6. 49/功能：编写算法判别给定二又树是否为完全二又树/作者：薛小超日期：2012.10.26f /甘include using namespace std;typedef char TElemType;typedef struct BiTNode/定义声明结构体 BiTNode(TElemType data;BiTNode *lchild, *rchild;*BiTree;typedef struct QNode/定义声明结构体 QNode(BiTree data;QNode *next;*LQueuePtr;struct LQueue(LQueuePtr front, rear;；

2、void LQueuelnit (LQueue&Q) /初始化队列 (Q. front=Q. rear=new QNode;Q. front-next=NULL:void Enqueue (LQueue&Q, BiTree e)/入队(LQueuePtr p;p=new QNode;p-data=e;Q.rear-next=p;Q.rear=p;p-next=NULL;bool Dequeue (LQueue&Q, BiTree &e)出队 (LQueuePtr p;if (Q. front=Q. rear)return false;p=Q front;Q.front=p-next:e=Q.

3、front-data;delete p;return true;void visit (TElemType z)(coutz;void CreateBiTree(BiTree &T,char S,int &i)(i+；if(Si= tf)(T二NULL;return;)T=new BiTNode;T-data=Si;CreateBiTree(T-lchild,S, i);CreateBiTree(T-rchild,S, i);void CreateBiTree(BiTree &T, char S)/创建二叉树(int i=-l;CreateBiTree (T,S,i);void preorde

4、rlists (BiTree T, void visit (TElemType)/广义表输出二义树(if(!T)(return;)visit(Tdata);if(T-lchild!=NULL|T-rchild!=NULL)(cout，(;preorderlists(T-lchild, visit);cout，,;preorderlists(T-rchild, visit);cout，);bool Complete (BiTree T)/层次遍历二义树是否为完全二又树 (bool f二false;BiTree p=T;LQueue Q;LQueuelnit (Q);if(!T)return false;Enqueue(Q, p);while(Dequeue(Q, p)(if(!p)f=true;else if (f)return false;else(Enqueue(Q,p-lchild);Enqueue(Q, p-rchild);)return true;主函数int main ()(BiTree T1;/char a = ABttD#G#FmT;char =CreateBiTree (Tl, a);创建二义树cout*又树为:，zendl:preorderlists (Tl, visit) ;/广义表输出二又树coutendl