借助了队列来实现二叉树的层序遍历,但是运行不出来
#define OK 1
#define ERROR 0
#define MaxSize 100
#define MAXQSIZE 100
typedef char TElemType;
typedef int Status;
typedef BiTNode QElemType;
typedef struct {
QElemType *base;
//存放队中元素
int front, rear;
//队头和队尾指针
} SqQueue;
//顺序循环队列类型
Status InitQueue(SqQueue &Q) {//构造一个空队列Q
Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间
if (!Q.base)
exit(OVERFLOW); //存储分配失败
Q.front = Q.rear = 0; //头指针和尾指针置为零,队列为空
return OK;
}
Status EnQueue(SqQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
if ((Q.rear + 1) % MAXQSIZE == Q.front) //尾指针在循环意义上加1后等于头指针,表明队满
return ERROR;
Q.base[Q.rear] = e; //新元素插入队尾
Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1
return OK;
}
Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的队头元素,用e返回其值
if (Q.front == Q.rear)
return ERROR; //队空
e = Q.base[Q.front]; //保存队头元素
Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
return OK;
}
int QueueEmpty(SqQueue &Q) { //判断队列是否为空
if (Q.rear == Q.front)
return 1;
else
return 0;
}
void LevelOrder(BiTree T) {
SqQueue *qu;
InitQueue(*qu);//初始化队列
EnQueue(*qu,*T);
//根结点指针进入队列
while (!QueueEmpty(*qu)) {
//队不为空,则循环
DeQueue(*qu,*T); //出队结点p
printf("%C", T->data);
//访问结点p
if (T-> lchild!=NULL) EnQueue(*qu,*(T-> lchild));
//有左孩子时将其进队
if (T-> rchild!=NULL) EnQueue(*qu,*(T-> rchild));
}
//有右孩子时将其进队
}
int main() {
BiTree BT=NULL;
int x=0,y=0;
cout<<"先序创建二叉树:";
cout<<"\n先序输入二叉树节点:";
CreateBiTree(BT);
cout<<"\n先序遍历序列是:";
Preorder (BT);
cout<<"\n中序遍历序列是:";
Inorder (BT);
cout<<"\n后序遍历序列是:";
Postorder (BT);
cout<<"\n带#的先序遍历序列是:";
Preorders (BT);
cout<<"\n层序遍历序列是:";
LevelOrder(BT);
cout<<"\n后序遍历求二叉树深度是:"<<Depth(BT);
cout<<"\n先序遍历求结点个数是:"<<Nodes(BT);
cout<<"\n先序遍历求叶结点个数是:"<<LeafNodes(BT);
cout<<"\n先序求结点个数和叶结点个数,";
count(BT,x,y);
printf("\n结点总数为:%d,叶结点总数为:%d",x,y);
cout<<"\n先序交换二叉树,";
exchange(BT);
cout<<"\n交换后二叉树的先序遍历序列为:";
Preorder (BT);
cout<<"\n后序销毁二叉树:";
Destroy(BT);
cout<<"\n二叉树被销毁了!";
return 0;
}