二叉树遍历 数据结构 课程设计

//要求：头文件一 #include<iostream.h> #include<stdio.h> #include<stdlib.h> struct BiTnode {char data; BiTnode *lchild,*rchild; }; struct Queue {BiTnode* *data0; int max; int front,rear,size; }; void SetQueue(Queue *Q,int n) {Q->data0=(BiTnode**)malloc(n*sizeof(BiTnode*)); if(Q->data0==NULL) {cout<<"overfilow.";exit(1); } Q->max=n;Q->front=0; Q->rear=0;Q->size=0; } void FreeQueue(Queue *Q) {free(Q->data0);} void QInsert(Queue *Q,BiTnode* item) {if(Q->size==Q->max){cout<<"Queue is full."<<endl;exit(1);} Q->data0[Q->rear]=item; Q->rear=(Q->rear+1)%Q->max; Q->size++; } BiTnode* QDelete(Queue *Q) {BiTnode* item; if(Q->size==0) {cout<<"Deleting from an empty queue!"<<endl;exit(1);} item=Q->data0 [Q->front]; Q->front=(Q->front+1)%Q->max; Q->size--; return item; } int QEmpty(Queue *Q) {if(Q->size==0)return(1);return(0); } void CreateBitree(BiTnode *&T) {char ch; cin>>ch; if(ch=='/')T=NULL; else { if(!(T=(BiTnode*)malloc(sizeof(BiTnode)))) {cout<<"Allocation failed."<<endl;exit(1);} T->data=ch; CreateBitree(T->lchild); CreateBitree(T->rchild); } } void PreOrder(BiTnode*T) { if(T!=NULL) {cout<<T->data<<"->"; PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTnode*T) { if(T!=NULL) { InOrder(T->lchild); cout<<T->data<<"->"; InOrder(T->rchild); } } void PostOrder(BiTnode*T) { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); cout<<T->data<<"->"; } } void LevelOrder(BiTnode *T) {BiTnode *ptr; Queue Q; if(T==NULL)return; SetQueue(&Q,50); QInsert(&Q,T); while(!QEmpty(&Q)) {ptr=QDelete(&Q); cout<<ptr->data<<"->"; if(ptr->lchild!=NULL) QInsert(&Q,ptr->lchild); if(ptr->rchild!=NULL) QInsert(&Q,ptr->rchild ); } FreeQueue(&Q); } void BiTreeTraverse() { BiTnode * T; char j; int flag=1; cout<<" ***************本程序实现二叉树遍历的操作*************** "<<endl; cout<<endl; cout<<"按先序遍历来构造二叉树："<<endl; printf("例如:a/b/c/d//(回车)\n"); CreateBitree(T); //初始化队列 while(flag) { cout<<endl; cout <<" 请选择: "<<endl <<" ┌──────────┐"<<endl <<" │ 1.递归先序遍历 │"<<endl <<" │ 2.递归中序遍历 │"<<endl <<" │ 3.递归后序遍历 │"<<endl <<" │ 4.非递归层序遍历 │"<<endl <<" │ 0.退出程序 │"<<endl <<" └──────────┘"<<endl; cin>>j; switch(j) { case '1':if(T) { cout<<"递归先序遍历二叉树:"<<endl; PreOrder(T); cout<<endl; } else cout<<"二叉树为空!"<<endl; break; case '2':if(T) { cout<<"递归中序遍历二叉树:"<<endl; InOrder(T); cout<<endl; } else cout<<"二叉树为空!"<<endl; break; case '3':if(T) { cout<<"递归后序遍历二叉树:"<<endl; PostOrder(T); cout<<endl; } else cout<<"二叉树为空!"<<endl; break; case '4':if(T) { cout<<"非递归层序遍历二叉树:"<<endl; LevelOrder(T); cout<<endl; } else cout<<"二叉树为空!"<<endl; break; default:flag=0;cout<<"程序运行结束，按任意键退出!"<<endl; } } } //主函数 #include<iostream.h> #include<stdio.h> #include<stdlib.h> //#include<fstream.h> void main () { char j; int flag=1; cout<<"**************** 欢迎进入本系统***************"<<endl; cout<<endl; while(flag) { cout<<endl; cout <<" 请按1回车开始: "<<endl <<" ┌──────────┐"<<endl <<" │ │"<<endl <<" │ │"<<endl <<" │ 1.二叉树遍历 │"<<endl <<" │ │"<<endl <<" │ │"<<endl <<" └──────────┘"<<endl; cin>>j; switch(j) { // case '1':Monkeyking(); break; case '1':BiTreeTraverse();break; // case '3':wenzbianji();break; default:flag=0;cout<<"程序系统就要退出了，按任意键退出!"<<endl; } } }