2023年广工数据结构实验报告平衡二叉树.docx

度劣与招实验报告课程名称数据结构实验学 院计算机学院专业班级计科9班学 号学生姓名指导教师爰庆2023 年7月 6 日c a se RH: T->bf= L H ； r d ->bf= EH； b r ea k ;case EH:T->b f =rd-> b f=EH； bre a k ；case L H： T-> b f= E H; r d >bf=RH； bre a k;)lc->bf=EH;RR o t a t e (T-> r c h ild);L _ R o tate( T )；bre a k;)/*平衡二叉树的插入操作* /Sta t us Inse r tAVL(BBSTrec &T, Red T ypc e, S t atu s &tallcr)i f (NULL=T) T = (BBS Tree)ma 1 1 oc ( s i zeo f (B BSTNod e )；T->data = e；T->bf= EH;T->lch i Id = NULL;T-> rchild = NUL L;Jelse if( e =T->d a ta)( 书中已存在和e相等的结点t al 1 e r = FALSE; return FALSE;e 1 se i f (e< T -> d ata) if(FALS E =InserlAV L (T->lchild, e, I a 1 ler) r elum FALS E ;if(TRUE= t allcr)swi t ch(T->bf)ca s e LH: Lef t Bala nee (T); tai I er = F A LSE； break;ca s e EH: T->bf = L H； tall e r = TRUE; break;c aseRH:T->b f = EH； ta Iler = FALSE; bre a k;)el s e if ( F ALSE= = Inser t AVL(T>rch i Id, e, t a 11 e r) re t urn FALSE;i f (TRUE=taller)swi t c h(T->bf) ca s e LH： T->bf = EH; t a Iler = F ALS E： brea k ;case E H: T->bf = R H; tai 1 er = T RU E; break;ca s c RH: R i ghtBalancc(T); t a 1 ler = F ALS E： br e a k ；return TRUE;)/*平衡二叉树的删除操作*/Status D e lctcAVL(BBS Tree &t, RcdTypc c, Stat u s &sho r tcr)当被删结点是有两个孩子，且其前驱结点是左孩子时,lag=ls t atic int t a g = 0;if( t =NULL)re t urn FALSE;/假如不存在元素，返回失败else i f (e=t->d a t a ) BBSTNode *q = NULL;/假如该结点只有一个孩子，则将日子树取代该结点if (t->lchild =NULL)q = t ；t = t>rch i I d ;f r e e (q);sho r te r = TRUE;1else if( t ->rch i Id = NULL)q = t;t = t->lc h il d ;f rcc (q);s ho r te r = TRUE;假如被删结点有两个孩子，则找到结点的前驱结点, 并将前驱结点的值赋给该结点，然后删除前驱结点els e q = t->lc h il d ;whil e (q->rchild)q = q->rc h il d ;It->data = q-> data;i f(t->lc h i 1 d -> d a t a=q-> d ata ) lag = 1；De 1 e t e A VL(t->lch i Id, q->d ata, s h orter);if(tag=l) B BS T re e r = t -> r c hi 1 d ;if(NULL=r) t->b f = 0;e 1 s esw i t c h(r-> b f) ca s e EH: t ->bf=-1 ； brea k ;def a u I t : Righ t Bal a n ce( t ) ; b reak;I) e Isc if(c< t ->da t a ) / /左子树中继续查找if(! DeleteAV L (t->l c hild, e , shorter) )re t u r n F ALSE；删除完结点之后，调整结点的平衡因子if (sh o rter& & (tag=0)sw i tch (t->b f )c ase L H ：t ->bf = EH;s h ort e r = T R UE;break;case EH:t->bf = RH；s h orter = FA L SE;bre a k;/假如本来就是右子树较高，删除之后就不平衡，需要做右平。衡操作case RH:R i g htBalan c e(t)；右平衡解决i f(t>rchil d -> b f = EH)sh o r t er = FALSE;e 1 ses h o r ter = TRU E ；b rea k;)else if (c> t ->d ata)右子树中继续查找if(!De 1 e t eAVL(t->rchild, e , sho rter) re t u r n FA L S E;)删除完结点之后，调整结点的平衡因子i f( s ho r te r && (t a g=0)s wit c h(t-> b f)case L H ：LeftBal a nc e (t);/左平衡解决if (t->lchi I d->bf = EH) / /注意这里，画图思考一下sh o r t er = F A LS E;e 1 seshone rshone rTRUE;b r eak;case E H ：t->bf=LH;sh o rt e r = F A LS E;br e ak;ca s e R H ：t ->bf = EH;shorte r = TRUE ;br e a k ;)if(ta g =!)i n t depth L e ft = BB S T r ccDcpth( t -> 1 child)；in t dep t hR i gh t = BBSTreeDep t h ( t ->rch i Id);t>bf = de p t hLcf t - dep t hRig h t;)retur n TRUE;)/*平衡二叉树的直找操作*/BBSTre e ScarchAV L (BBSTrce T, R c dT y pc c) i f (T=NULL) r e turn NULL；i f (e= T ->data)relur n T;Jelse i f( e >T->da t a)return S earchAVL(T->r c hil d , e)； else r etur n Searc h AVL(T->lchild, e );)/*获取输入存到数组a*/A r ray Ge t I n putToAr r a y() Arr a y head, p, q;char k;h cad = p = q = NU L L;i n t m;i f (k ! =' n')sea np =(Ar r a yNode*)m a 1 1 oc(si z e of(Arr ayNode)；h e ad = p ；p->data = m;k = g etchar()；)whilc( k ! ='n')scanf("%d",&m)；q = (Array N ode* )m a 1 1 o c( s izcof (Array No d c)；q->d a t a = m；p-> n ex tq；p -> n e x t ；k = g e tch a r ();i f (p!=NULL)p->n e xt = NU L L ；)r etur n head: 返回存放数据的头指针)/*根据输入的字符串建一棵平衡二叉树文/B B ST r ee M a keBBS Tree ( )i nt i=0;S ta t us ta 1 le r = T RUE;BBS Tree T = NULL;Ar r ay a;a = G etl n p u tT o A r ray ();while (a! = N ULL) tai 1 er = TRUE；InsertAVL (T, a ->da t a, t a Iler)；a = a ->nex t ；r etu r n T;/*递归先序遍历*/Status Pre 0 r d e r _ R e c T ra v e rs e (BBS T re e T)if(NULL=T) r et u rn OK;prin t f("% d ", T->data);P r eOrd e r_ R ecTra v er s e( T -> 1 c hi 1 d); PreOrder_Re c Tr a ver s e(T>rchild);)/*递归中序遍历*/St a t us I nOrder_RecTrav e rse(BBSTre e T) if(T->lchild)I nOrder_RecTraverse(T->| c hi 1 d)； printf("%d ",T-> d ata);if(T->rchild)I n 0 rd e r_R e c T raver s e (T> r c h i 1 d);)/*递归后序遍历*/Statu s LastOr d er_RecTr a ver s e( B B S Tree T) if(T->child)La s tO r der_RecTrave r se(T->l c h i Id);if( T ->rch i 1 d )L a stOr d er_RecTravers e (T->r c h i 1 d);pri n tf("%d ", T-Adata)；)/*找到最左结点* /BBST rce G o F a r L e f t(BBSTr e e T, LS tack&S) if(NULL=T) r eturn NU LL；wh i 1 e(T >lchild!= NULL) P u sh_LS(S, T);T = T->l c hil d :)return T;)/*非递归中序遍历*/void InO r d e r Tra v ers e _ I (B BSTr e e T)L Sta c k S;InitSta c k_L S ( S );BB STreep = NULL;p = GoFa r Le f t( T, S);w hile(p !=NULL)print f ("%d ”, p-> d a t a)；if(p-> r child!=NULL)p = GoFa r L eft( p -> r ch i 1 d, S);Ie 1 se if(St a ck E mpty_L S (S)!=TRU E) P o p_ L S (S, p)；e Is e p = N U L L;BBST r ee V i sitFarL e ft( B BSTr e e T,LSta ck&S) if(NULL=T) r et u rn NULL;假如 T 为空，则返回空prin t f("%d ",T->d a ta)；先序，先读取结点数据wh i le(T->lch i ld!=NULL)Push_LS(S, T);/入栈T = T-> 1 c h ild;/遍历下一个左子树print f("%d T->d a t a);下一个结点的读取数据)r ct u r n T;/*非递归先序遍历*/v o id PreOrderTr a veseI(BBSTre e T)L S tack S ；InitSt a ck_LS (S);BBSTre e p;p= VisitFarLeft(T, S) ;/先将左边的数据先序读取whil e(p! =NULL) if ( P ->rc h i 1 d! = NUL L)/假如最左下结点的右子树不为空p = V i s itFarLeft (p->r c h ild, S);/执行遍历该结点的左子树else i f (Sta c kEmp t y_LS!=TRU E ) Pop_LS(S,p)； /假如S不为空栈，出栈else p = NULL： /假如为空栈，p赋予空 ) )/*非递归后序遍历文/vo i d L a st 0 rder T rave s eI (BB STr e e r oot)BBS T ree p = root;BB S Tree s t ac k 30；i n t num=0;B BST r e e have_vis i ted = NULL;while(NULL!=p|num> 0 )while (NULL! =p)st a c k n u m+= p ；p=p->l c hild;)p = s tacknum-l；if( N ULL=p->rc h il d | I hav e _vi s ited=p-> r c h i 1 d) p r intf("% d " , p > d ata)；n u m;h av e _v i sited=p;p二NULL;)e 1 s e (p=p-> r c hil d ;)pr i ntf("n");)/*非递归层次遍历输出一棵二叉树*/voi d Leve 1 OrederTra v e rse_P r i n t ( B B STr e e T) jf(T=NULL)pri n t f("The tree is em p t y!");if (T!=NULL) LQ u eue Q;InitQue u e _LQ(Q);BBS Tree p = T;printf ("% d ",p-> d ata);EnQ u eue_LQ ( Q, p );w h i 1 e (D e Q ueue_LQ(Q, p ) i f (p->lchild !=NULL) p r i n tf(" %d ”, p-> 1 chi 1 d->data);EnQueu e _LQ( Q, p->l c h ild)；)if(p->rchild!=NULL)printf( " %d ", p->rc h i 1 d-> d ata);E nQueue_L Q (Q, p->r c hild);)/*括号表达法输出平衡二叉树*/void BraNota t io n P r int (BBS Tree T)if(NULL=T)prin t f(" 空!) e lscif(T!=NULL)if(T!=NULL)pr i n t f ( " % i ", T->data);if(T->lch i ld|T-> r child) printf(T)；)if(T->l child I I T->rchi 1 d )i f(T-> 1 child) BraNota t i o nPrint (T>lc h i 1 d )： e 1 s e if(T>rchild) printf( " #")；)printf ；if(T一)rc h i Id ) BraNo t a t i o n P rint (T->rc h i Id);)elseif(P> 1 ch i Id) prin t f ( " #");)pr i ntf (T)；)/*将一棵树转换为一个数组*/Array GetArrayF romTree( B BST r e e T) S t a lus f i r stT ime = TRU E;Ar r ay head = NULL；Array Node *b = NULL;A r rayNod e * q = N U L L;i f(T=NLJLL) pr i n t f(" T h e t r ee is e mpiy!");)if(T!=NULL)LQu e u e Q；I n itQue u e _LQ(Q);BBSTree p = T；q = (Arr a y)m a Hoc (s i zeof (Ar r a y Node);q->dat a = p->da(a；i f(fi rstTimc=TRUE)head = q;firstTime = F ALS E ；b = q；e 1 se b >nex t = q;b = b->next;)En Que u e _LQ(Q, p);vhilc(DcQucuc_LQ(Q» p )i f (p-> 1 child!=NULL)q = (Arr a y)mal 1 o c (s i z cof( Array No de);q->da t a = p->lc h il d ->dat a ;b->n e xlq；b = b>next：EnQueue.LQ (Q, p->l child);)if(p>rchil d ! =NULL)q =(Array)m a 1 loc(sizeo f ( Ar r a yNo d e);q->data = p>r c hild->data；b->ne x t = q;b = b->n e xt;E nQu e u e _LQ(Q, p-> r child);)if ( b ! =NULL)«b->ncxt = NULL;。)re t urn h ead；/*将两棵平衡二叉树合并成一颗平衡二叉树*/BBSTree C ombine2Tree(B B STreeTl, BBSTreeT2) S t atu s ( a ller= TRUE;Arra y a = NULL;a = Gel Array Fro mTree(T2)；while (a!=NULL) tai 1 e rtai 1 e rTRUE;I n s e r t A VL(T 1 , a>da t a, taller);a = a-> n ext;return T 1 ;)/*将一棵平衡二叉树分裂成两棵平衡二叉树刃/*参数1：要进行分裂的树参数2:分裂出来的小于等J- x的子树。参数3：分裂出来的 大于x的子树。参数4：关键字x*/Status S p litBB ST r cc(BBSTrc e Ttl, BBST r e e &T t 2, BBSTrec&Tt3 , int x ) Array a = N U LL;S (atus ta 1 1 e r;a = GctA r r a yFromTree(Tt 1 );i f (Ttl=NULL) retu r n FALSE;e 1 se(wh i I e(a !=NULL) if( a -> d ata<= x )t allc r = TRUE；In s e r lA VL(Tt 2 , a >d a ta, tall e r);a = a-> n e xt;tai 1 e r =TRUE；Ins e r t AVL (Tt3, a->da t a, ta 1 le r )； a = a->next;r e t u i n TRUE；4.测试(1)建树操作测试代码:BBSTree Tl = NULL;printf (”请输入树的结点数据，按T结束：”)； Tl = MakeBBSTreeO ;BraNotationPrint (Tl); /用括号表示法输出 return 0;测试数据：1 2 3 4 5 6测试结果:清输入树的结点数据，按-1结束：1 2 3 4 5 6 -14(2(1, 3),5(#, 6)T112 Gl(2)插入操作测试代码:printf (”n请输入要插入的数据：");scanf("%dnz &rc);getchar();taller = TRUE;InsertAVL(Tlr m, taller);BraNotationPrint (Tl) ; /用括号表示法输出测试数据：12 3 4 5 6 插入8测试结果：请输入要插入的数据：8 4(2(1, 3), 6(5, 8)T12向/ 、 / 、/Au1占Rsfol J测试结果：请输入要插入的数据：8 4(2(1, 3), 6(5, 8)T12向/ 、 / 、/Au1占Rsfol J测试数据：1 2 3 4 5 6插入4测试数据：1 2 3 4 5 6插入4测试结果:清输入要插入的数据：44(2(1, 3),5(#, 6)12 GlT1汨品1I 10 I |3)0|I 10 I |3)0|(3)删除操作测试代码:princf (”n请输入要删除的数据：”)；scanf ("%dn, &叫；getchar ();shorter = TRUE;DeleteAVL (Tl, ir, shorter);BraNocationPrint (Tl) ; /用括号表示法输出测试数据：1 2 3 4 5 6 删除6测试结果：清输入要删除的数据：64(2(1,3),5)T1测试数据：1 2 3 4 5 6 删除2测试结果：清输入要删除的数据：24(1(#, 3),5(#, 6)1.题目：平衡二叉树ADT BBSTree数据对象：D= ai I a iGllem S et, i=l, 2,n, nO 数据关系：Rl= <a i - 1 , a i > I ai-1, ai®, i =2, .,n )基本操作：BBST ree MakeBBST r ee ()操作结果:创建好一棵树返回:将创建好的树返回St a tus I n se r tAVL ( B BST r e e &T, Rc d Type e, S tatu s &ta 1 1 er)初始条件：树T已存在，e存在，ta 1 ler为真操作结果:将e插入到T中返回:成功TRUE,失败FALSEStatus D e le t eAVL (BBSTr e e &tz R c dTy p e e, S t atus &s h orte r )初始条件：树T已存在，e存在，shorter为真操作结果:将e从T中删除返回：成功TRUE,失败FALSEBBSTr e e Sea r chAV L ( B B S Tree Tz RcdTyp e e)初始条件:树T已存在，e存在 操作结果:从T中找到e 返回:以e为根节点的树void L_Rotate (BB S Tre e &p)初始条件:树p存在T1、测试数据：1 2 3 4 5 6 删除4测试结果：请输入要删除的数据：43(2(1,#), 5(#, 6)T1由/'W/lE/ Gi(4)查找操作测试代码:princf ("n请输入要查找的数据：;scanf ("%dM, &ir);getchar ();shorter = TRUE;T1 = SearchAVL(Tl,叫；BraNotationPrint (Tl) ; /用括号表示法输出测试数据：1 2 3 4 5 6查找5测试结果：请输入要查找的数据：55(#, 6)T1rAi(5)输出测试代码:BBSTree T = NULL;princf (R请输入数据：");T = MakeBBSTree();printf (nnTJ:n);BraNotationPrint(T);printf(nnn);printf (=n速归先序遍历输出：");PreOrder_RecTraverse(T);printf(nnn);printf (叭n菲递归先.序遍历输出：n);PreOrderTravese_I(T);printf(nnM);printf (”n速归中序遍历输出：”)； InOrde r_Re cTraverse(T);printf(nnn);print;£(Rn菲递归中序遍历输出：w);InOrderTraverse_I(T);printf(;princf (”n途归后序遍历输出：”)；LastOrder_RecTraverse(T);printf(nnn);prints(叭n菲递归后序遍历输出：");LastOrderTravese_I(T);printf(”n");测试数据：1 2 3 4 5 6测试结果:请输入数据：1 2 3 4 5 6 7 8 9T为：4<2<1,3，6<5,87,9）递归先序遍历输出：421 36 5879非递归先序遍历输出：42 13 6587 9递归中序遍历输出：123 45 6789非递归中序遍历输出：12 34 5678 9递归后序遍历输出：132 57 9864IE递归后序遍历输出：132 ;79 8 65 .思考与小结在完毕平衡二叉树实验的过程中，所碰到的最大问题就是如何实现平衡二叉树删除结点的接 口，由于课本没有涉及到这个知识点,所以自己只能通过阅读其他书籍和通过参考网上的资料 来对这个过程有了进一步的理解。另一方面自己想了一个树的括号表达法来将一棵树打印出 来，这对于一棵树的表达是挺有用的。总的来说,平衡二叉树这个知识点涉及到的算法大约 就是添加结点,删除结点，查找结点这三个方面，而其他的接口都是以这三个为基础,实现进 一步的拓展。6 .源代码/*(1 )根据输入字符串创建一棵平衡二叉树BBST r ee M a keBBST r ee ();(2)平衡二叉树插入元素操作Status Ins e r (A VL(BB STree &T, R c dTyp e e, S t a t u s &taller)；(3)层次遍历输出二叉树v oid L evelOred e r T raver s e _Pr i nt(B B STre e T);(4)括号表达法输出二叉树v oid BraNolationP r inl(BB ST r e eT);(5)平衡二叉树删除元素操作S tat u s De 1 e tcA V L (BBSTrc e &t, Rc d T y p e e, St a tu s &s h o r t er);(6)求平衡二叉树的深度1 n t BBST ree Depth(B BSTrce T);(7)互换所有结点的左右子树void E x c hangc S ubT r ee( B B S Tree &T)(8 )递归先序遍历St a t u s PreOr d e r _R e cTr a vers e (B BS T r eeT);(9 )递归中序遍历St a tu s InOrde r _RecTr a v erse(BBSTree T)；(10)递归后序遍历Stat u s L astOrd e r_R e cTra v erse( BBS T re e T);(1 1 )非递归先序遍历vo i d P r e O r d e rTraverse_I(BBSTree T);(12)非递归中序遍历v o id InO r d e r T rav e rse_ I (BBSTr e e T );(13)非递归后序遍历vo i d LaslOrderT r av e rseI(BB S T ree T);*/#include<stdio.h>#inc I ud e <malloc. h >#defineOVERF LOW-1#deflne O K 1#def i ne ERROROdefineTRUE 1# def i ne F ALSEOdefine LH+1 左高# d e fine EH 0 等高define RH-1/右高typedef i nt Rc d T y pe；type def i n t Sta t u s ;/*存放输入数据的数组结构体* /t y ped e f st r u c t Arra y Nod e R c d T ype data;Arra yNod e * n e x t；Arr a y Node, * Array;/*平衡二又树结构体*/type d ef s t r u c t B BSTNode!R cd Type da t a ;int bf;BBSTNodc * 1 chi 1 d , *r child;BBSTNode,*BBSTree；/*链队列结构体*/type d ef s tru c t L Q NodeBBS T ree elem；s t ruc t LQ N od e *n e x t ; L QNode, * Q u cu e Pt r ；/*队列结点结构体* /ty p edef stru c t Q u e u e Ptr f r ont;Q u e u ePtr r e ar； LQueu e ；/*栈结点结构体字/type def st r u c t L S NodeB BST r ee data;数据域struct LS Node * next; 指针域LSNod e , *LStac k ;结点和链栈类型/次初始化一个链栈*/St a t u s InitSta c k _LS(L S tack &S)S =NULL；)/文进校操作*/S t a tus Push_LS( LStack &S, BBS Tr e e e)LSN o de *t;t =( L S No d e*)m alloc (siz e o f ( L SNode);if(NULL= t ) re t urn OVERFLOW;t-> d a t a = e；t->nex t = S;S = t;r etu r n OK;)/*出栈操作*/Stat u s P op_LS (LS(a c k &S, B B STree &e)LSN o d e *t；if(S=N U LL) return ERRO R;t =s；e = t-> d ata;S = S-> n ext;r eturn OK;)/*获得栈顶元素力St a tus Ge t To p _LS(LSt a ck S, B B ST r e e &e) if (NULL=S) retu rn ERROR;els e e = S->d a t a;re t urn OK;)/*判断栈是否为空* /S t a t u s St a ckEm p ty_LS( L S t ack S)i f (NULL=S) retu r n TRUE;e 1 se r e tu r n FA L S E;)/*初始化链队列*/void I n i t Q ueu e _ L Q ( L Q ueue &Q) Q.fron t = NULL;Q. re a r= NULL;/ *链队列进栈操作* /S t a tus E n Q ueu e _LQ ( L Qu e ue &Q, B B STree e) L QNod e *p；p = ( L QNo d e *)mallo c (s i z eof (LQNode);i f (NULL=p) return OVERFLOW；p->el e m = e ;p>ne x t = NULL;i f (NULL =Q.fronl) Q. front = p； /e 插入空队列el s e Q. r e a r> n ex t= p; 插入非空队列Q.rear = p;队尾指针指向新的队尾r eturn O K ；)/*链队列出栈操作*/Stat u s D e Q u eue_L Q (LQ u eu e &Q, B B S T r ee &e)LQ N ode * p ;if(NUL L= Q .fro n t ) return ERROR;p = Q.fr o n t；e = p -> e 1 e m；Q.fron t = p->nex t ;i f (Q. r ear= p ) Q. r ear = NULL;fre e ( p );r c t urn O K：/*求平衡二叉树的深度*/inc BBS TreeDep t h (BBSTreeT) i n t de p t h L e f t, d e p thRight;i f (NU L L=T) return 0 ;els e (d e p t h Left = BBST reeD e pth(T->lc h il d )；depthRight = BBS T reeD e p th(T->rc h ild);r e tu r n 1 +(