二叉树的前序-中序-后序-层序遍历

#includeiostreamusingnamespacestd;#definequeuesize100#defineERROR0#defineOK1typedefstructBiTNode//二叉树{chardata;structBiTNode*lchild,*rchild;}BinNode;typedefBinNode*BiTree;//定义二叉链表指针类型typedefstruct{intfront,rear;BiTreedata[queuesize];//循环队列元素类型为二叉链表结点指针intcount;}cirqueue;//循环队列结构定义voidleverorder(BiTreet){cirqueue*q;BiTreep;q=newcirqueue;//申请循环队列空间q-rear=q-front=q-count=0;//将循环队列初始化为空q-data[q-rear]=t;q-count++;q-rear=(q-rear+1)%queuesize;//将根结点入队while(q-count)//若队列不为空，做以下操作if(q-data[q-front])//当队首元素不为空指针，做以下操作{p=q-data[q-front];//取队首元素*pcoutp-data;q-front=(q-front+1)%queuesize;q-count--;//队首元素出队if(q-count==queuesize)//若队列为队满，则打印队满信息，退出程序的执行couterror,队列满了！;else{//若队列不满，将*p结点的左孩子指针入队q-count++;q-data[q-rear]=p-lchild;q-rear=(q-rear+1)%queuesize;}if(q-count==queuesize)//若队列为队满，则打印队满信息，退出程序的执行couterror;else{//若队列不满，将*p结点的右孩子指针入队q-count++;q-data[q-rear]=p-rchild;q-rear=(q-rear+1)%queuesize;}}else{q-front=(q-front+1)%queuesize;q-count--;}//当队首元素为空指针，将空指针出队}intCreatBiTree(BiTree&root){charch;BiTreep;BiTreeq[100];intfront=1,rear=0;intjj=0;ch=getchar();while(ch!='#'){p=NULL;if(ch!=','){p=(BiTNode*)malloc(sizeof(BiTNode));if(NULL==p)returnERROR;jj++;p-data=ch;p-lchild=p-rchild=NULL;}rear++;q[rear]=p;if(1==rear)root=p;else{if(p&&q[front]){if(0==(rear%2))q[front]-lchild=p;elseq[front]-rchild=p;}if(p&&(NULL==q[front])){free(p);returnERROR;}if(1==rear%2)front++;}ch=getchar();}returnOK;}voidPreOrder(BiTreeroot)//先序遍历{if(root!=NULL){coutroot-data;//根PreOrder(root-lchild);//左PreOrder(root-rchild);//右}}voidInOrder(BiTreeroot)//中序遍历{if(root!=NULL){InOrder(root-lchild);//左coutroot-data;//根InOrder(root-rchild);//右}}voidPostOrder(BiTreeroot)//后序遍历{if(root!=NULL){PostOrder(root-lchild);//左PostOrder(root-rchild);//右coutroot-data;//根}}intshuru(){cout输入二叉树(,表示空)安#结束输入：\n;}intmain(){shuru();BiTreess;inti=CreatBiTree(ss);coutendl先序遍历二叉树：;PreOrder(ss);coutendl中序遍历二叉树：;InOrder(ss);coutendl后序遍历二叉树：;PostOrder(ss);coutendl层序遍历二叉树：;leverorder(ss);coutendl;return0;}程序结果：