实现平衡二叉排序树的各种算法代码

/*¡¶ÊµÏÖƽºâ¶þ²æÅÅÐòÊ÷µÄ¸÷ÖÖËã·¨¡·Ò»¡¢·ÖÎöÌâÄ¿ÒªÇóÓú¯ÊýʵÏÖÈçÏÂƽºâ¶þ²æÅÅÐòÊ÷Ëã·¨,:£¨1£©²åÈëнáµã£¨2£©Ç°Ðò¡¢ÖÐÐò¡¢ºóÐò±éÀú¶þ²æÊ÷£¨µÝ¹é£©£¨3£©Ç°Ðò¡¢ÖÐÐò¡¢ºóÐò±éÀúµÄ·ÇµÝ¹éËã·¨£¨4£©²ã´Î±éÀú¶þ²æÊ÷£¨5£©ÔÚ¶þ²æÊ÷ÖвéÕÒ¸ø¶¨¹Ø¼ü×Ö(º¯Êý·µ»ØֵΪ³É¹¦1,ʧ°Ü0)£¨6£©½»»»¸÷½áµãµÄ×óÓÒ×ÓÊ÷£¨7£©Çó¶þ²æÊ÷µÄÉî¶È£¨8£©Ò¶×Ó½áµãÊý£¨9£©É¾³ýij½áµãΪÁËÍê³ÉÒÔÉϵĸ÷Ïî²Ù×÷£¬Ê×ÏÈÓ¦¸ÃÓú¯Êý½¨Ò»¿Ãƽºâ¶þ²æÅÅÐòÊ÷£¬ÊäÈëÐÎʽÊÇÊ×ÏÈÊäÈëÒª½¨µÄ¶þ²æÊ÷µÄ½áµãÊý£¬È»ºóÒÀ´ÎÊäÈë¸÷¸ö½áµãµÄÖµ¡£ÔÚʵÏÖ²åÈëнáµãµÄº¯Êýʱ£¬ÐèÒªÒ»¸öÏòÒ»¿Ã¶þ²æÊ÷²åÈëнáµãµÄº¯Êý¡£¿ÉÓõݹéË㷨д³öƽºâ¶þ²æÊ÷µÄÇ°Ðò£¬ÖÐÐò£¬ºóÐò±éÀúµÄº¯Êý¡£ÔÚдƽºâ¶þ²æÊ÷µÄÇ°£¬ÖУ¬ºóÐò±éÀúµÄ·ÇµÝ¹éË㷨ʱҪÓõ½Õ»½á¹¹µÄ֪ʶ£¬ÔËÓÃÕ»½á¹¹À´´æ´¢Æ½ºâ¶þ²æÊ÷½áµãµÄÖ¸Õë¡£ÔÚ²ã´Î±éÀú¶þ²æÊ÷ʱÐèÒªÓõ½¶ÓÁнṹ£¬ÔËÓöÓÁнṹµÄÏȽøÏȳöÀ´´æ´¢¶þ²æÊ÷µÄ½áµãÖ¸Õë¡£ÔÚ±éÀú¶þ²æÊ÷µÄ½áµãʱÐèÒªÒ»¸ö·ÃÎʽáµãÊý¾ÝµÄº¯Êý¡£¶þ²æÊ÷ÊÇÒ»¿ÃÅÅÐòÊ÷£¬ËùÒÔ¶þ²æÊ÷µÄ²éÕÒ¿ÉÒÔÔËÓÃÆäÓÐÐòµÄÐÔÖÊ£¬²éÕҵķ½Ê½ºÍ½¨Ê÷µÄ·½Ê½ÏàËÆ¡£½»»»¶þ²æÊ÷¸÷½áµãµÄ×óÓÒ×ÓÊ÷ʱ£¬¿ÉÒÔÓÃÏÈÐò±éÀúµÝ¹éµÄ·½Ê½´Ó¸ù½áµãÏòϵݹ飬ÿ´Î·ÃÎʽáµãʱ¾ÍÐ轫¸÷½áµãµÄ×óÓÒº¢×ÓµÄÖ¸Õëµ÷»»£¬²¢¶Ô¸Ã½áµãµÄƽºâÒò×Ó×÷ÏàÓ¦µÄ´¦Àí¡£Ê¾¶þ²æÊ÷µÄÉî¶Èʱ£¬¿ÉÓõݹéµÄ·½Ê½·ÃÎʽáµãµÄ×óÓÒ×ÓÊ÷£¬²¢¼Ç¼ÏÂ×óÓÒ×ÓÊ÷µÄÉî¶È£¬×îºó·µ»Ø×óÓÒ×ÓÊ÷ÖнÏÉîµÄÉî¶ÈµÄÖµ¼´¿É¡£¿ÉÒÔÓÃÒ»´Î±éÀúµÄ·½Ê½±éÀú¶þ²æÊ÷£¬¼Ç¼ÿһ¸ö¾­¹ýµÄ½áµã£¬Èô½áµã´æÔÚÇÒ×óÓÒº¢×Ó¶¼Îª¿Õ£¬Ôò¸Ã½áµãΪҶ×Ó½áµã¡£É¾³ý¶þ²æÊ÷µÄij¸ö½áµãʱ£¬Ê×ÏÈҪдһ¸öº¯Êý£¬Óõݹé²éÕҵķ½Ê½ÕÒµ½ÏàÓ¦µÄ½áµã£¬¸Ãº¯Êý»¹ÒªÓе÷Õû¶þ²æÊ÷ƽºâµÄ×÷Óã¬ÒòΪÈôɾ³ý½áµãʹµÃ¶þ²æÊ÷Éî¶È¼õÉÙ¶ø²»Æ½ºâ£¬ÐèÒªµ÷Õû¶þ²æÊ÷µÄƽºâ£¬Èô¸Ã½áµã²»´æÔÚÔò·µ»ØERROR,£¬Èô´æÔڸýáµã£¬ÔòÓ¦¸ÃÔÙдһ¸öº¯ÊýÀ´É¾³ý¸Ã½áµã£¬ÔÚɾ³ý֮ǰ»¹ÒªÅжϸýáµãÊÇÖ»ÓÐ×ó×ÓÊ÷»¹ÊÇÖ»ÓÐÓÒ×ÓÊ÷»¹ÊÇ×óÓÒ×ÓÊ÷¶¼ÓеÄÇé¿ö£ºÈôÖ»ÓÐ×ó»òÊÇÖ»ÓÐÓÒ×ÓÊ÷£¬ÔòÖ»Ðèɾ³ý¸Ã½áµã£¬²¢»ØËݵ÷Õû¶þ²æÊ÷µÄƽºâ£»Èô¸Ã½áµãµÄ×óÓÒ×ÓÊ÷¶¼ÓУ¬ÔòÓ¦¸ÃÓÃÁíÒ»¸öº¯ÊýµÝ¹éÕÒµ½¸Ã½áµãµÄÖ±½Ó¡°ºó¼Ì¡±£¬²¢´Ó¸Ã¡°ºó¼Ì¡±¿ªÊ¼»ØËݵ÷Õû¶þ²æÊ÷µÄƽºâ¡£*/#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0#defineLH1#defineEH0#defineRH-1#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))#defineSTACK_INIT_SIZE100//Õ»#defineSTACKINCREMENT10//Õ»#defineMAXQSIZE100//¶ÓÁÐ#defineElemTypeint#defineStatusint#defineTRUE1#defineFALSE0#defineBooleanbool//-----------------------------------------½á¹¹ÌåtypedefstructBSTNode//ƽºâ¶þ²æÊ÷½á¹¹{ElemTypedata;intbf;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;typedefBSTreeSElemType;//Õ»typedefBSTreeQElemType;//¶ÓÁÐtypedefstruct//¶ÓÁеĽṹÌå{QElemType*base;intfront;intrear;}SqQueue;typedefstructSqStack//Õ»µÄ½á¹¹Ìå{SElemType*base;SElemType*top;intstacksize;}SqStack;//-------------------------------------º¯ÊýÁбí//¶ÓÁÐStatusInitQueue(SqQueue&Q);//³õʼ»¯¶ÓÁÐStatusEnQueue(SqQueue&Q,QElemTypee);//½ø¶ÓÁÐStatusDeQueue(SqQueue&Q,QElemType&e);//³ö¶ÓÁÐStatusGetHead(SqQueueQ,QElemType&e);//»ñ¶ÓÁÐÊ×intQueueLength(SqQueueQ);//¶ÓÁ㤶ÈStatusQueueTraverse(SqQueueQ);//±éÀú¶ÓÁÐ//Õ»StatusInitStack(SqStack&S);//³õʼ»¯Õ»StatusPush(SqStack&S,SElemTypee);//½øÕ»StatusPop(SqStack&S,SElemType&e);//³öÕ»StatusGetTop(SqStackS,SElemType&e);//»ñÕ»¶¥intStackLength(SqStackS);//Õ»µÄ³¤¶ÈStatusStackEmpty(SqStackS);//ÅÐÕ»¿ÕStatusStackTraverse(SqStackS);//Õ»µÄ±éÀú//ƽºâ¶þ²æÊ÷voidR_Rotate(BSTree&p);//ÓÒ”èvoidL_Rotate(BSTree&p);//×ó”èStatusInsertAVL(BSTree&T,ElemTypee,Boolean&taller);//ƽºâ¶þ²æÊ÷½áµã²åvoidLeftBalance(BSTree&T);//×óƽºâvoidRigthBalance(BSTree&T);//ÓÒƽºâStatusCreateBST(BSTree&T,intn);//½¨Ê÷StatusVisit(ElemTypee);//·ÃÎÊStatusPreOrderTraverse(BSTreeT);//Ç°Ðò±éÀúStatusInOrderTraverse(BSTreeT);//ÖÐÐò±éÀúStatusPostOrderTraverse(BSTreeT);//ºóÐò±éÀúStatuspreOrderIter(BSTreeT);//Ç°Ðò·ÇµÝ¹é±éÀúStatusinOrderIter(BSTreeT);//ÖÐÐò·ÇµÝ¹é±éÀúStatuspostOrderIter(BSTreeT);//ºóÐò·ÇµÝ¹é±éÀúStatusFindBST(BSTreeT,ElemTypekey,int&n);//ÔÚ¶þ²æÊ÷ÖвéÕҹؼü´ÊStatusOverTraverse(BSTree&T);//²ã´Î±éÀúStatusOverChang(BSTree&T);//½»»»×óÓÒ×ÓÊ÷intBSTDeep(BSTreeT);//ÇóÊ÷µÄÉî¶ÈStatusSum(BSTreeT,int&n);//ÇóÒ¶×Ó½áµãÊýStatusDeleteBST(BSTree&T,intkey,bool&taller);//ɾ³ý½áµãStatusDelete(BSTree&p,bool&taller);StatusDelete2(BSTree&p,booltaller,ElemType&f);voidMU();//Ñ¡Ôñ²Ëµ¥//-------------------------------------//-------------------------------------³õʼ»¯¶ÓÁÐStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)returnERROR;Q.front=Q.rear=0;returnOK;}//-------------------------------------½ø¶ÓÁÐStatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}//-------------------------------------³ö¶ÓÁÐStatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}//-------------------------------------»ñ¶ÓÁÐÊ×StatusGetHead(SqQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];returnOK;}//-------------------------------------¶ÓÁ㤶ÈintQueueLength(SqQueueQ){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}//-------------------------------------±éÀú¶ÓÁÐStatusQueueTraverse(SqQueueQ){inti;i=Q.front;if(Q.front==Q.rear)printf(TheQueueisEmpty!);else{printf(TheQueueis:);while(i!=Q.rear){printf(%d,Q.base[i]);i=i+1;}}printf(\n);returnOK;}//-------------------