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

《2023年广工数据结构实验报告平衡二叉树.docx》由会员分享，可在线阅读，更多相关《2023年广工数据结构实验报告平衡二叉树.docx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、度劣与招实验报告课程名称数据结构实验学 院计算机学院专业班级计科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

2、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 d ata) if(FALS E =InserlAV L (T-lchild, e, I a 1 ler) r elum FALS E ;if

3、(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(Trch 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-b

4、f = 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

5、 t urn FALSE;/假如不存在元素，返回失败else i f (e=t-d a t a ) BBSTNode *q = NULL;/假如该结点只有一个孩子，则将日子树取代该结点if (t-lchild =NULL)q = t ；t = trch 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 =

6、 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

7、Bal a n ce( t ) ; b reak;I) e Isc if(cda 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;/假如本来就是右子树较高，删除之后就不平衡，需要做右平。

8、衡操作case RH:R i g htBalan c e(t)；右平衡解决i f(trchil 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);/

9、左平衡解决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

10、( t -rch i Id);tbf = 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

11、 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

12、- 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

13、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(Trchild);)/*递归中序遍历*/St a t us I nOrder_RecTrav e rse(BBSTre e T) if(T-lchild)I

14、 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(

15、%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(

16、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)；先序

17、，先读取结点数据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)/假如最左下结点

18、的右子树不为空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;whil

19、e(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 (

20、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

21、)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 nPrin

22、t (Tlc h i 1 d )： e 1 s e if(Trchild) 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 ray

23、Nod 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)

24、;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 = bnext：EnQueue.LQ (Q, p-l child);)if(prchil d ! =NULL)q =(Array)m a 1 loc(sizeo f ( Ar r a yNo d e);q-data = pr c hild-data；b-ne x t = q;b = b-n e xt;E nQu e u e _

25、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 , ada t a, taller);a = a- n ext;return

26、 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 -

27、d atad 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(

28、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

29、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

30、测试结果：清输入要删除的数据：24(1(#, 3),5(#, 6)1.题目：平衡二叉树ADT BBSTree数据对象：D= ai I a iGllem S et, i=l, 2,n, nO 数据关系：Rl= 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,

31、失败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(

32、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);

33、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);prin

34、ts(叭n菲递归后序遍历输出：);LastOrderTravese_I(T);printf(”n);测试数据：1 2 3 4 5 6测试结果:请输入数据：1 2 3 4 5 6 7 8 9T为：421,3，65,87,9）递归先序遍历输出：421 36 5879非递归先序遍历输出：42 13 6587 9递归中序遍历输出：123 45 6789非递归中序遍历输出：12 34 5678 9递归后序遍历输出：132 57 9864IE递归后序遍历输出：132 ;79 8 65 .思考与小结在完毕平衡二叉树实验的过程中，所碰到的最大问题就是如何实现平衡二叉树删除结点的接 口，由于课本没有涉及到这个知

35、识点,所以自己只能通过阅读其他书籍和通过参考网上的资料 来对这个过程有了进一步的理解。另一方面自己想了一个树的括号表达法来将一棵树打印出 来，这对于一棵树的表达是挺有用的。总的来说,平衡二叉树这个知识点涉及到的算法大约 就是添加结点,删除结点，查找结点这三个方面，而其他的接口都是以这三个为基础,实现进 一步的拓展。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

36、)层次遍历输出二叉树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(

37、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

38、 (BBSTr e e T );(13)非递归后序遍历vo i d LaslOrderT r av e rseI(BB S T ree T);*/#include#inc I ud e #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

39、 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 c

40、u 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,

41、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 t

42、us 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;/

43、 *链队列进栈操作* /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 ;pne 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 ；)/*链队列

44、出栈操作*/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 +(