二叉搜索树

二叉搜索树一元多项式加减乘实现二〇一四年六月软件综合课程设计《课程设计》报告一、二叉搜索树：各种搜索树效率比较1．问题陈述：本题目要求对普通的二叉排序树、AVL树分别实现制定操作，并分析比较这两种不同数据结构对应的一系列插入和删除操作的效率。要求测试对N个不同整数进行下列操作的效率：（1）按递增顺序插入N个整数，并按同样顺序删除；（2）按递增顺序插入N个整数，并按相反顺序删除；（3）按随机顺序插入N个整数，并按随机顺序删除；要求N从1000到10000取值，并以数据规模N为横轴，运行时间为纵轴，画出3种不同数据结构对应的操作效率比较图。2．程序代码：#includeiostream.h#includestdio.h#includemalloc.h#defineMAXNODE100#defineTRUE1#defineFALSE0#defineOVERFLOW1#defineLH+1#defineEH0#defineRH-1typedefintStatus;typedefcharTElemType;typedefstruct{Statuskey;}ElemType;typedefstructBSTNode{ElemTypedata;Statusbf;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;StatusSearchBST(BSTreeT,Statuskey,BSTreef,BSTree&p){if(!T){p=f;returnFALSE;}//查找不成功elseif(key==T-data.key){p=T;returnTRUE;}//查找成功elseif(keyT-data.key)returnSearchBST(T-lchild,key,T,p);//在左子树中继续查找elsereturnSearchBST(T-rchild,key,T,p);//在右子树中继续查找}//SearchBSTStatusInsertBST(BSTree&T,ElemTypee){BSTreep,s;if(!SearchBST(T,e.key,NULL,p)){//查找不成功s=(BSTree)malloc(sizeof(BSTNode));s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;//插入s为新的根结点elseif(e.keyp-data.key)p-lchild=s;//插入s为左孩子elsep-rchild=s;//插入s为右孩子returnTRUE;}elsereturnFALSE;//树中已有关键字相同的结点，不再插入}//InsertBSTStatusCreateBST(BSTree&T)//将输入的一组数据，创建为二叉排序树{Statusnum;ElemTypee;cout请输入二叉排序树结点数:endl;cinnum;while(num!=0){cout请输入结点值:endl;cine.key;InsertBST(T,e);//按二叉排序树插入方法；num--;}return0;}Statusmax(Statuslchild,Statusrchild)//取较大的值返回{if(lchildrchild)returnlchild;elsereturnrchild;}StatusDepth_bt(BSTreeT)//求二叉树深度{if(T==NULL)return0;return1+max(Depth_bt(T-lchild),Depth_bt(T-rchild));}StatusBalance(BSTreeT)//递归判断是不是平衡二叉树{Statusbl,br;if(T==NULL)return1;//空树输出是平衡二叉树bl=Depth_bt(T-lchild);//将左子树的深度赋值给blbr=Depth_bt(T-rchild);//将右子树的深度赋值给brif(bl-br1||br-bl1)return0;//如果不满足平衡二叉树的定义返回错误信息returnBalance(T-lchild)&&Balance(T-rchild);//递归调用}Statusn=0;voidN_PreOrderAVL(BSTreeT)//先序遍历（根，左，右）{if(T){coutT-data.key;n++;N_PreOrderAVL(T-lchild);N_PreOrderAVL(T-rchild);}}Statusk_ey[40],k=0;voidKey_PreOrderAVL(BSTreeT)//先序遍历（根，左，右）{if(T){if(kn){k_ey[k]=T-data.key;k++;}Key_PreOrderAVL(T-lchild);Key_PreOrderAVL(T-rchild);}}intPreorderAVL(BSTreeT){if(T){coutT-data.key;PreorderAVL(T-lchild);PreorderAVL(T-rchild);}return1;}voidR_Rotate(BSTree&p){BSTreelc;lc=p-lchild;//lc指向*p的左子树根结点p-lchild=lc-rchild;//lc的右子树挂接为*p的左子树lc-rchild=p;p=lc;//p指向新的根结点}//R_RotatevoidL_Rotate(BSTree&p){BSTreerc;rc=p-rchild;//rc指向*p的右子树根结点p-rchild=rc-lchild;//rc的左子树挂接为*p的右子树rc-lchild=p;p=rc;//p指向新的根结点}//L_RotatevoidLeftBalance(BSTree&T){BSTreelc,rd;lc=T-lchild;//lc指向*T的左子树根结点switch(lc-bf){//检查*T的左子树的平衡度，并作相应平衡处理caseLH://新结点插入在*T的左孩子的左子树上，要作单右旋处理T-bf=lc-bf=EH;R_Rotate(T);break;caseRH://新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc-rchild;//rd指向*T的左孩子的右子树根switch(rd-bf){//修改*T及其左孩子的平衡因子caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;}//switch(rd-bf)rd-bf=EH;L_Rotate(T-lchild);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T作右旋平衡处理}//switch(lc-bf)}//LeftBalancevoidRightBalance(BSTree&T){BSTreerc,ld;rc=T-rchild;//rc指向*T的右子树根结点switch(rc-bf){//检查*T的右子树的平衡度，并作相应平衡处理caseRH://新结点插入在*T的右孩子的右子树上，要作单右旋处理T-bf=rc-bf=EH;L_Rotate(T);break;caseLH://新结点插入在*T的右孩子的左子树上，要作双旋处理ld=rc-lchild;//ld指向*T的右孩子的左子树根switch(ld-bf){//修改*T及其右孩子的平衡因子caseLH:T-bf=EH;rc-bf=RH;break;caseEH:T-bf=rc-bf=EH;break;caseRH:T-bf=LH;rc-bf=EH;break;}//switch(rd-bf)ld-bf=EH;R_Rotate(T-rchild);//对*T的右子树作右旋平衡处理L_Rotate(T);//对*T作左旋平衡处理}//switch(lc-bf)}//LeftBalanceStatusInsertAVL(BSTree&T,ElemTypee,Status&taller){if(!T){//插入新结点，树长高，置taller为TRUET=(BSTree)malloc(sizeof(BSTNode));T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=TRUE;}else{if(e.key==T-data.key)//树中已存在和e有相同关键字的结点{taller=FALSE;return0;}//则不再插入if((e.keyT-data.key)){//应继续在*T的左子树中进行搜索if(InsertAVL(T-lchild,e,taller)==0)return0;//未插入if(taller)//已插入到*T的左子树中且左子树长高switch(T-bf){//检查*T的平衡度caseLH://原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller=FALSE;break;caseEH://原本左、右子树等高，现因左子树增高而使树增高T-bf=LH;taller=TRUE;break;caseRH://原本右子树比左子树高，现左、右子树等高T-bf=EH;taller=FALSE;break;}//switch(T-bf)}//ifelse{//应继续在T↑的右子树中进行搜索if(InsertAVL(T-rchild,e,taller)==0)return0;if(taller)//已插入到*T的右子树且右子树长高switch(T-bf){//检查*T的平衡度caseLH://原本左子树比右子树高，现左、右子树等高T-bf=EH;taller=FALSE;break;caseEH://原本左、右子树等高，现因右子树增高而使树增高T-bf=RH;taller=TRUE;break;caseRH://原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=FALSE;break;}//switch(T-bf)}//else}//elsereturn1;}//InsertAVLStatusDelete(BSTree&p){BSTreeq,s;if(!p-rchild){//右子树空则只需重接它的左子树q=p;p=p-lchild;free(q);}elseif(!p-lchild){//只需重接它的右子树q=p;p=p-rchild;free(q);}else{//左右子树均不空q=p;s=p-lchild;while(s-rchild)//转左，然后向右到尽头{q=s;s=s-rchild;}p-data=s-data;//s指向被删结点的后继if(q!=p)q-rchild=s-lchild;//重接*q的右子树elseq-lchild=s-lchild;//重接*q的左子树free(s);}returnTRUE;}//DeleteStatusDeleteBST(BSTree&T,Statuskey){if(!T)returnFALSE;//不存在关键字等于key的数据元素else{if(key==T-data.key)//找到关键字等于key的数据元素returnDelete(T);elseif(keyT-data.key)returnDeleteBST(T-lchild,key);elsereturnDeleteBST(T-rchild,key);}}//DeleteBST#includestdio.hintmain(){Statusi,j,t,r=0,e,num;ElemTypeavl;//TElemType;St