vlambda博客
学习文章列表

#include<iostream>#include<string.h>#include<stdlib.h>typedef char TElemType;#define STACKINITSIZE 256//初次分配空间大小#define STACKINCREMENT 128//空间分配增量大小#define INITQUEUE 20//队列空间大小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");}