//主函数 int main() { BiTree T1; //char a[]={"AB#D##G#F##"}; char a[]={"ABC####"}; CreateBiTree(T1,a);//创建二叉树 cout<<"二叉树为:"<<endl; preorderlists(T1,visit);//广义表输出二叉树 cout<<endl; cout<<"上面二叉树:"; if(Complete(T1)) cout<<"是完全二叉树"; else cout<<"是非完全二叉树"; cout<<endl; return 0; }
bool Dequeue(LQueue&Q,BiTree &e)//出队 { LQueuePtr p; if(Q.front==Q.rear) return false; p=Q.front; Q.front=p->next; e=Q.front->data; delete p; return trபைடு நூலகம்e; } void visit(TElemType z) { cout<<z; } void CreateBiTree(BiTree &T,char S[],int &i) { i++; if(S[i]=='#') { T=NULL; return; } 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); } void preorderlists(BiTree T,void visit(TElemType))//广义表输出 二叉树 { if(!T)
//名称：6.49 //功能：编写算法判别给定二叉树是否为完全二叉树 //作者：薛小超 //日期：2012.10.26 //*************************************************************** #include <iostream> 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; }; void LQueueInit(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; }
{ cout<<"#"; return; } visit(T->data); 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; LQueueInit(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; }