多项式的设计报告数据结构课程设计

PAGE4目录1.多项式的设计报告…….………2a．概要设计…….………2b．详细设计…….………3c．调试分析…….………8数据结果…….………8时间复杂度分析……10问题和解决方法……10源程序代码展示…………102.二叉树的设计报告…….………18a．概要设计…….………18b．详细设计…….………19c．调试分析…….………21数据结果…….………21时间复杂度分析………22问题和解决方法………23源程序代码展示…………233.课程设计总结…………………26多项式的设计报告概要设计1.将该存储结构定义为链式结构的线性表存储结构的定义：structNode{floatcoef;//结点类型intexp;};typedefNodepolynomial;structLNode{polynomialdata;//链表类型LNode*next;};typedefLNode*Link;2．创建函数流程图开始开始分配空间第i个的系数ceof第i个的指数expexp>0？否是错误，重新输入JudgeIfExpSame=1？否是错误，重新输入1=>i注释：JudgeIfExpSame函数是判断输入的指数是否与多项式中已存在的某项的指数相同3.主程序流程图:4.多项式加法的算法分析将链表pa，pb分别复制到新建链表p1，p2中，再新建链表pc，然后分别依次对p1，p2链表中结点中的指数进行比较，将指数小的结点的值先赋值给pc中的结点，两个指数相同时，将系数相加后一起赋值给pc中的结点，最后将p1或者p2中多余的结点直接赋值给pc链表，pc链表就是通过加法后的多项式5.多项式减法的算法分析新建链表pt，将pb中的结点值赋给pt，然后将pt中所有结点的系数乘上（-1）后，再将pt和pa相加就得到相减后的多项式。6.多项式乘法的算法分析同样将链表pa，pb中的结点赋值给p1，p2，然后依次将p1中的每个结点的值分别与p2中每个结点的值相乘后赋值给pc，就得到相乘后的多项式。详细设计创建多项式的源程序voidCreateLink(Link&L,intn){if(L!=NULL)//首先判断是已经存在多项式，如果存在则销毁{DestroyLink(L);}Linkp,newp;L=newLNode;L->next=NULL;//分配结点空间，new相当于malloc函数(L->data).exp=-1;//创建头结点p=L;for(inti=1;i<=n;i++){newp=newLNode;cout<<"请输入第"<<i<<"项的系数和指数:"<<endl;cout<<"系数:";cin>>(newp->data).coef;cout<<"指数:";cin>>(newp->data).exp;if(newp->data.exp<0){cout<<"您输入有误，指数不允许为负值!"<<endl;deletenewp;i--;continue;//输入不符合要求则删除重新创建，delete相当于free函数}newp->next=NULL;p=L;if(newp->data.coef==0){cout<<"系数为零，重新输入!"<<endl;deletenewp;i--;continue;}while((p->next!=NULL)&&((p->next->data).exp<(newp->data).exp)){p=p->next;//p指向指数最小的那一个}if(!JudgeIfExpSame(L,newp)){newp->next=p->next;p->next=newp;}else{cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl;deletenewp;DestroyLink(L);CreateLink(L,n);//创建多项式没有成功，递归调用重新创建break;}}}二．多项式相加模块的源程序voidPolyAdd(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);//将链表pa，pb分别复制给p1，p2pc=newLNode;pc->next=NULL;p=pc;//创建新链表pc来存储相加后的值p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL){if(p1->data.exp<p2->data.exp)//将指数小的结点的值赋给pc链表中的结点{p->next=p1;p=p->next;p1=p1->next;}elseif(p1->data.exp>p2->data.exp){p->next=p2;p=p->next;p2=p2->next;}else//当指数相等时，将系数相加后再把指数和系数赋给pc{p1->data.coef=p1->data.coef+p2->data.coef;if(p1->data.coef!=0)//当相加后的系数不等于0，直接赋给pc{p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else//当相加后的系数等于0时不存储在pc中，将p1，p2分别指向下一个结点进行相加算法{pd=p1;p1=p1->next;p2=p2->next;deletepd;}}}if(p1!=NULL){p->next=p1;}if(p2!=NULL){p->next=p2;}}三．多项式相减模块的源程序voidPolySubstract(Link&pc,Linkpa,Linkpb){Linkp,pt;CopyLink(pt,pb);p=pt;//将链表pb赋给链表ptwhile(p!=NULL){(p->data).coef=(-(p->data).coef);p=p->next;//将pt中的系数都乘以（-1）}PolyAdd(pc,pa,pt);//再将pt与pa相加，就得到相减的结果DestroyLink(pt);}四．多项式相乘模块的源程序voidPolyMultiply(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd,newp,t;pc=newLNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL)//用循环的方式将p1的每个结点分别与p2中的每个结点相乘{pd=newLNode;pd->next=NULL;p=newLNode;p->next=NULL;t=p;while(p2){newp=newLNode;newp->next=NULL;newp->data.coef=p1->data.coef*p2->data.coef;newp->data.exp=p1->data.exp+p2->data.exp;t->next=newp;t=t->next;p2=p2->next;}PolyAdd(pd,pc,p);//将最新相乘算出来的多项式与已存在的多项式相加CopyLink(pc,pd);//再将相加的结果放到链表pc中去p1=p1->next;p2=pb->next;DestroyLink(p);DestroyLink(pd);}}五．主函数源程序voidmain()//主函数{intn;LinkL,La=NULL,Lb=NULL;//La,Lb分别为创建的两个多项式intchoose;Menu();//调用菜单函数while(1){cin>>choose;switch(choose){case1:cout<<"请输入需要运算的第一个一元多项式的项数:"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"输入有误，请重新输入……\n\t\t\t\t请选择:";break;}CreateLink(La,n);//创建链表Lacout<<"请输入需要运算的第二个一元多项式的项数:"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"输入有误，请重新输入……\n\t\t\t\t请选择:";break;}CreateLink(Lb,n);cout<<"\n\t\t\t\t请继续选择:";break;//创建链表Lbcase2:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;//如果多项式为空则重新输入}PolyAdd(L,La,Lb);cout<<""<<endl;//将多项式相加cout<<"待相加的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相加后的结果为：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t请继续选择:";break;case3:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}PolySubstract(L,La,Lb);//将多项式相减cout<<"相减的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相减后的结果为：";PrintList(L);cout<<"\n\t\t\t\t请继续选择:";DestroyLink(L);break;case4:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}PolyMultiply(L,La,Lb);//将多项式相乘cout<<"相乘的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相乘后的结果为：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t请继续选择:";break;case5:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}cout<<"一元多项式A为："<<endl;PrintList(La);cout<<""<<endl;//将多项式La输出cout<<"一元多项式B为："<<endl;PrintList(Lb);//将多项式Lb输出cout<<"\n\t\t\t\t请继续选择:";break;case6:if(La&&Lb){DestroyLink(La);DestroyLink(Lb);cout<<"多项式销毁成功！"<<endl;cout<<"\t\t\t\t请继续选择:";}else{cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";}break;case7:exit(0);//exit(0)强制终止程序，返回状态码0表示正常结束default:cout<<"输入错误，请重新选择操作……\n\t\t\t\t请选择:";break;}}}调试分析1.数据结果*************************一元多项式的运算*************************①新建多项式**②加法运算**③减法运算**④相乘运算**⑤输出**⑥清空**⑦退出******************************************************************请选择:9输入错误，请重新选择操作……请选择:4多项式不存在，请重新输入……请选择:1请输入需要运算的第一个一元多项式的项数:46项数太大，请重新输入……请选择:1请输入需要运算的第一个一元多项式的项数:5请输入第1项的系数和指数:系数:34指数:5请输入第2项的系数和指数:系数:47指数:2请输入第3项的系数和指数:系数:48指数:1请输入第4项的系数和指数:系数:49指数:3请输入第5项的系数和指数:系数:28指数:4请输入需要运算的第二个一元多项式的项数:4请输入第1项的系数和指数:系数:33指数:5请输入第2项的系数和指数:系数:39指数:1请输入第3项的系数和指数:系数:29指数:3请输入第4项的系数和指数:系数:88指数:2请继续选择:2待相加的两个一元多项式为：A的多项式为：48x+47x^2+49x^3+28x^4+34x^5B的多项式为：39x+88x^2+29x^3+33x^5相加后的结果为：87x+135x^2+78x^3+28x^4+67x^5请继续选择:3相减的两个一元多项式为：A的多项式为：48x+47x^2+49x^3+28x^4+34x^5B的多项式为：39x+88x^2+29x^3+33x^5相减后的结果为：9x-41x^2+20x^3+28x^4+x^5请继续选择:4相乘的两个一元多项式为：A的多项式为：48x+47x^2+49x^3+28x^4+34x^5B的多项式为：39x+88x^2+29x^3+33x^5相乘后的结果为：1872x^2+6057x^3+7439x^4+6767x^5+6795x^6+5355x^7+2603x^8+924x^9+1122x^10请继续选择:5一元多项式A为：48x+47x^2+49x^3+28x^4+34x^5一元多项式B为：39x+88x^2+29x^3+33x^5请继续选择:6多项式销毁成功！请继续选择:7Pressanykeytocontinue2．时间复杂度分析创建函数的复杂度为o（n），复制链表时为o（n），设链表a为n1个节点，链表b为n2个节点，加法运算时因为有复制过程所以如果是不理想状态复杂度为o（2（n1+n2）），减法运算时因为先将链表b复制然后又将其改成-pb，然后将-pb与pa相加，故复杂度为o（2（n1+2n2）），乘法时复杂度为o（n1*n2）3.问题和解决方法1.开始没有想到将链表复制，而是直接在链表上进行的操作，但是却因此改变了链表的值而影响了后面的操作使结果不如人意。解决方法是从网上看了一个程序后，重新分配空间后将其链表复制到其上，才达到效果，不影响原来多项式的数值。2.系数的表示方法，开始运行的时候，不是很到位，比如说当系数为1或-1时，可以省略1，还有指数1和0次方的表示比较特殊。所以解决的时候必须分别分情况讨论。但是又增加了程序的空间复杂度。还有一些其他细小的问题一般都会有的，只需注意一下，也比较容易改正。3.在课设过程中有遇到这样一个问题，就是对一个操作完成以后它不会进行下一个操作，分析之后发现switch语句中用到break，而没有循环故不进行下个选项直接跳出switch到主函数中去了，加入一个while以后就可以正常进行。4.改进改进的话就是需要尽量减少空间复杂度和时间复杂度。源程序代码展示#include<conio.h>#include<iostream>#include<stdlib.h>usingnamespacestd;structNode{floatcoef;//结点类型intexp;};typedefNodepolynomial;structLNode{polynomialdata;//链表类型LNode*next;};typedefLNode*Link;voidDestroyLink(Link&L)//销毁链表函数{Linkp;p=L->next;while(p){L->next=p->next;deletep;p=L->next;}deleteL;L=NULL;}/*判断指数是否与多项式中已存在的某项相同*/intJudgeIfExpSame(LinkL,Linke){Linkp;p=L->next;while(p!=NULL&&(e->data.exp!=p->data.exp))p=p->next;if(p==NULL)return0;elsereturn1;}//用头插入法创建含有n个链表类型结点的项，即创建一个n项多项式的算法voidCreateLink(Link&L,intn){if(L!=NULL){DestroyLink(L);}Linkp,newp;L=newLNode;L->next=NULL;(L->data).exp=-1;//创建头结点p=L;for(inti=1;i<=n;i++){newp=newLNode;cout<<"请输入第"<<i<<"项的系数和指数:"<<endl;cout<<"系数:";cin>>(newp->data).coef;cout<<"指数:";cin>>(newp->data).exp;if(newp->data.exp<0){cout<<"您输入有误，指数不允许为负值!"<<endl;deletenewp;i--;continue;}newp->next=NULL;p=L;if(newp->data.coef==0){cout<<"系数为零，重新输入!"<<endl;deletenewp;i--;continue;}while((p->next!=NULL)&&((p->next->data).exp<(newp->data).exp)){p=p->next;//p指向指数最小的那一个}if(!JudgeIfExpSame(L,newp)){newp->next=p->next;p->next=newp;}else{cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl;deletenewp;DestroyLink(L);CreateLink(L,n);//创建多项式没有成功，递归调用重新创建break;}}}/*输出链表算法*/voidPrintList(LinkL){Linkp;if(L==NULL||L->next==NULL)cout<<"该一元多项式为空！"<<endl;else{p=L->next;//项的系数大于0的5种情况if((p->data).coef>0){if((p->data).exp==0)cout<<(p->data).coef;elseif((p->data).coef==1&&(p->data).exp==1)cout<<"x";elseif((p->data).coef==1&&(p->data).exp!=1)cout<<"x^"<<(p->data).exp;elseif((p->data).exp==1&&(p->data).coef!=1)cout<<(p->data).coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}//项的系数小于0的5种情况if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;elseif(p->data.coef==-1&&p->data.exp==1)cout<<"-x";elseif(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;elseif(p->data.exp==1)cout<<p->data.coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}p=p->next;while(p!=NULL){if((p->data).coef>0){if((p->data).exp==0)cout<<"+"<<(p->data).coef;elseif((p->data).exp==1&&(p->data).coef!=1)cout<<"+"<<(p->data).coef<<"x";elseif((p->data).exp==1&&(p->data).coef==1)cout<<"+"<<"x";elseif((p->data).coef==1&&(p->data).exp!=1)cout<<"+"<<"x^"<<(p->data).exp;elsecout<<"+"<<(p->data).coef<<"x^"<<(p->data).exp;}if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;elseif(p->data.coef==-1&&p->data.exp==1)cout<<"-x";elseif(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;elseif(p->data.exp==1)cout<<p->data.coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}p=p->next;}}cout<<endl;}/*把一个链表的内容复制给另一个链表算法*/voidCopyLink(Link&pc,Linkpa){Linkp,q,r;pc=newLNode;pc->next=NULL;r=pc;p=pa;while(p->next!=NULL){q=newLNode;q->data.coef=p->next->data.coef;q->data.exp=p->next->data.exp;r->next=q;q->next=NULL;r=q;p=p->next;}}/*将两个一元多项式相加算法*/voidPolyAdd(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);pc=newLNode;pc->next=NULL;p=pc;p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL){if(p1->data.exp<p2->data.exp){p->next=p1;p=p->next;p1=p1->next;}elseif(p1->data.exp>p2->data.exp){p->next=p2;p=p->next;p2=p2->next;}else{p1->data.coef=p1->data.coef+p2->data.coef;if(p1->data.coef!=0){p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else{pd=p1;p1=p1->next;p2=p2->next;deletepd;}}}if(p1!=NULL){p->next=p1;}if(p2!=NULL){p->next=p2;}}/*将两个多项式相减算法*/voidPolySubstract(Link&pc,Linkpa,Linkpb){Linkp,pt;CopyLink(pt,pb);p=pt;while(p!=NULL){(p->data).coef=(-(p->data).coef);p=p->next;}PolyAdd(pc,pa,pt);DestroyLink(pt);}/*将两个一元多项式相乘算法*/voidPolyMultiply(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd,newp,t;pc=newLNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL){pd=newLNode;pd->next=NULL;p=newLNode;p->next=NULL;t=p;while(p2){newp=newLNode;newp->next=NULL;newp->data.coef=p1->data.coef*p2->data.coef;newp->data.exp=p1->data.exp+p2->data.exp;t->next=newp;t=t->next;p2=p2->next;}PolyAdd(pd,pc,p);CopyLink(pc,pd);p1=p1->next;p2=pb->next;DestroyLink(p);DestroyLink(pd);}}//菜单函数voidMenu(){cout<<endl<<endl;cout<<"\t*************************一元多项式的运算**********************"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t*\t\t\t①新建多项式\t\t\t*"<<endl;cout<<"\t*\t\t\t②加法运算\t\t\t*"<<endl;cout<<"\t*\t\t\t③减法运算\t\t\t*"<<endl;cout<<"\t*\t\t\t④相乘运算\t\t\t*"<<endl;cout<<"\t*\t\t\t⑤输出\t\t\t*"<<endl;cout<<"\t*\t\t\t⑥清空\t\t\t*"<<endl;cout<<"\t*\t\t\t⑦退出\t\t\t*"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t***************************************************************"<<endl;cout<<"\t\t\t\t请选择:";}//判断输入的整数是不是为1到20的数字算法，限定多项式的项数，使项数不要太多intCompareIfNum(inti){if(i>0&&i<20)return0;elsereturn1;}voidmain()//主函数{intn;LinkL,La=NULL,Lb=NULL;//La,Lb分别为创建的两个多项式intchoose;Menu();//调用菜单函数while(1){cin>>choose;switch(choose){case1:cout<<"请输入需要运算的第一个一元多项式的项数:"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"输入有误，请重新输入……\n\t\t\t\t请选择:";break;}CreateLink(La,n);cout<<"请输入需要运算的第二个一元多项式的项数:"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"输入有误，请重新输入……\n\t\t\t\t请选择:";break;}CreateLink(Lb,n);cout<<"\n\t\t\t\t请继续选择:";break;case2:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}PolyAdd(L,La,Lb);cout<<""<<endl;cout<<"待相加的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相加后的结果为：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t请继续选择:";break;case3:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}PolySubstract(L,La,Lb);cout<<"相减的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相减后的结果为：";PrintList(L);cout<<"\n\t\t\t\t请继续选择:";DestroyLink(L);break;case4:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}PolyMultiply(L,La,Lb);cout<<"相乘的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相乘后的结果为：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t请继续选择:";break;case5:if(La==NULL||Lb==NULL){cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";break;}cout<<"一元多项式A为："<<endl;PrintList(La);cout<<""<<endl;cout<<"一元多项式B为："<<endl;PrintList(Lb);cout<<"\n\t\t\t\t请继续选择:";break;case6:if(La&&Lb){DestroyLink(La);DestroyLink(Lb);cout<<"多项式销毁成功！"<<endl;cout<<"\t\t\t\t请继续选择:";}else{cout<<"多项式不存在，请重新输入……\n\t\t\t\t请选择:";}break;case7:exit(0);//exit(0)强制终止程序，返回状态码0表示正常结束default:cout<<"输入错误，请重新选择操作……\n\t\t\t\t请选择:";break;}}}二叉树的设计报告概要设计主要是递归函数的使用比较重要，还有非递归遍历时用栈来操作。主函数是基本的switch语句可以省略创建函数的递归流程图开始递归函数开始递归函数CreatBiTree（T）Ch=Null？是否T=NullCh=>T—>dataT—>lchild=>TT—>rchild=>T输入Ch先序递归遍历流程图4.存储结构主要用了链表二叉树定义typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;在层序遍历中还使用了队列来存储。b.详细设计一．二叉树的创建算法的源程序voidCreateBiTree(BiTree&T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空节点charch;ch=getchar();//从键盘输入结点的值if(ch=='')T=NULL;//如果为空格号就为空结点else{if(!(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);//递归调用创建左结点CreateBiTree(T->rchild);//递归调用创建右结点}}二．二叉树的递归先序遍历算法的源程序voidPreOrderTraverse(BiTreeT){//递归先序遍历if(T){cout<<""<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}三．二叉树的递归中序遍历算法的源程序voidInOrderTraverse(BiTreeT){//递归中序遍历if(T){InOrderTraverse(T->lchild);cout<<""<<T->data;InOrderTraverse(T->rchild);}}四．二叉树的递归后序遍历算法的源程序voidPostOrderTraverse(BiTreeT)//递归后序遍历{if(T){ PreOrderTraverse(T->lchild);//后序遍历左子树 PreOrderTraverse(T->rchild);//后序遍历右子树 cout<<""<<T->data;//访问结点}}五．二叉树的递归层序遍历算法的源程序voidLevelOrderTraverse(BiTreeT){//层序遍历，用队列来存储BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T){//根结点入队Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//队头元素出队front=(front+1)%MaxLength;cout<<""<<p->data;if(p->lchild){//左孩子不为空，入队Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}if(p->rchild){//右孩子不为空，入队Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}六．主函数源程序voidmain(){BiTreeT;T=NULL;cout<<endl;cout<<"\t**********************************************************";cout<<"\n\n\t********************二叉树的递归操作:*********************\n";cout<<"\t********\t1.新建二叉树\t********\n";cout<<"\t********\t2.二叉树的层次遍历算法\t********\n";cout<<"\t********\t3.二叉树的递归先序遍历算法\t********\n";cout<<"\t********\t4.二叉树的递归中序遍历算法\t********\n";cout<<"\t********\t5.二叉树的递归后序遍历算法\t********\n";cout<<"\t********\t0.退出\t********\n";cout<<"\t**********************************************************\n";cout<<"\n\t**********************************************************\n";cout<<"\t\t\t\t请选择";while(1){intselect;cin>>select;switch(select){case0:return;//选0退出case1:cout<<"请按先序次序输入各结点的值，以空格表示空节点:"<<endl;CreateBiTree(T);//以空格表示空节点创建二叉树cout<<"\t\t\t\t请选择";break;case2:if(!T)cout<<"未建立树，请先建树！\n\t\t\t\t请重新选择";//如果树不存在则重新选择创建树else{cout<<"\n层序遍历:\n";//递归层序遍历LevelOrderTraverse(T);cout<<"\n\t\t\t\t请再选择";}break;case3:if(!T)cout<<"未建立树，请先建树！\n\t\t\t\t请重新选择";else{cout<<"\n先序遍历:\n";//递归先序遍历PreOrderTraverse(T);cout<<"\n\t\t\t\t请再选择"<<endl;}break;case4:if(!T)cout<<"未建立树，请先建树！\n\t\t\t\t请重新选择"; else{cout<<"\n中序遍历:\n";//递归中序遍历InOrderTraverse(T);cout<<"\n\t\t\t\t请再选择"<<endl;}break;case5:if(!T)cout<<"未建立树，请先建树！\n\t\t\t\t请重新选择";else{cout<<"\n后序遍历:\n";//递归后序遍历PostOrderTraverse(T);cout<<"\n\t\t\t\t请再选择"<<endl;}break;default:cout<<"请确认选择项:\n\t\t\t\t请重新选择";}//endswitch}//endwhile}c.调试分析1.数据结果2．时间复杂度分析很显然递归树的每种遍历的时间复杂度都是o（n），但是非递归遍历因为有进栈和出栈的操作，因此时间复杂度为O（2n）。3.问题和解决方法在主函数中因为调用的函数中我还是带有参数类型，导致编译过程中出错，当时还没认真的发现，后来经过查阅书籍后才看到这个明显的错误，将类型去掉后，错误消失。在运行的时候，总觉得输出不是很贴近人的表达，比如说，我还没有建立树，但我选择4来遍历，结果会出现中序遍历但是后面没内容，会让初次接触的人不明白为什么，因此在输出语句前加了一句if语句，判断树是否为空，若空则输出“未建立树”告知。然后主要问题是在运行时多次修改使之美观化和一目了然化。当然还有一些其他的小问题以后会多加注意。源程序代码展示#include"iostream.h"#include"stdlib.h"#include"stdio.h"typedefcharElemType;//定义二叉树结点值的类型为字符型constintMaxLength=20;//结点个数不超过20个typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;voidCreateBiTree(BiTree&T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空节点charch;ch=getchar();if(ch=='')T=NULL;else{if(!(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidPreOrderTraverse(BiTreeT){//先序遍历if(T){cout<<""<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}voidInOrderTraverse(BiTreeT){//中序遍历if(T){InOrderTraverse(T->lchild);cout<<""<<T->data;InOrderTraverse(T->rchild);}}voidPostOrderTraverse(BiTreeT){if(T){ PreOrderTraverse(T->lchild);//后序遍历左子树 PreOrderTraverse(T->rchild);//后序遍历右子树 cout<<""<<T->data;//访问结点}}voidLevelOrderTraverse(BiTreeT){//层序遍历BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T){//根结点入队Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//队头元素出队front=(front+1)%MaxLength;cout<<""<<p->data;if(p->lchild){//左孩子不为空，入队Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}if(p->rchild){//右孩子不为空，入队Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}voidmain(){BiTr