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

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

1、才 J j一 f/度 一 课 程 名 称.学 院 专 业 班 级 学 T学 生 姓 名.指 导 教 师 实 验 报 告 数 据 结 构 实 验 计 算 机 学 院 计 科 9 班 3 _苏 庆 2023 年 7 月 6 日1.题 目：平 衡 二 叉 树 AD T BBSTree数 据 对 象：D=a i I a iff ile m S e t,i=l,2.,n,nO 数 据 关 系：R l=|a i-1,a i,i=2,.,n 基 本 操 作：BBST r e e M akeB B ST r e e()操 作 结 果:创 建 好 一 棵 树 返 回:将 创 建 好 的 树 返 回 S t a

2、t u s I n s e r tAVL(BBST r e e&T,Rc d Type e,S t a t us&ta 1 1 e r)初 始 条 件：树 T 已 存 在，e 存 在，ta 1 l e r 为 真 操 作 结 果:将 e 插 入 到 T 中 返 回：成 功 TRUE,失 败 FALSES t a t u s D e l e t eAVL(BBSTr e e&t,R c dTy p e e,S ta t u s&s h o r t e r)初 始 条 件：树 T 已 存 在，e 存 在，s h o r te r为 真 操 作 结 果:将 e 从 T 中 删 除 返 回：成 功 T

3、RUE,失 败 FALSEBBSTr e e Sea r chAV L(B B S T r e e T,RcdTyp e e)初 始 条 件:树 T 已 存 在，e 存 在 操 作 结 果:从 T 中 找 到 e返 回:以 e 为 根 节 点 的 树 v o i d L _ R o ta te(BB S T re e&p)初 始 条 件:树 p 存 在操 作 结 果:对 P 左 旋 操 作 v oid R_RO t ate(B B S T r e e&p)初 始 条 件：树 p 存 在 操 作 结 果:对 p 右 旋 操 作 void L e ft B a lance(BBSTree&T)初

4、始 条 件：树 T 存 在 操 作 结 果:对 T 左 平 衡 操 作 v o i d RightBalance(BBSTre e&T)初 始 条 件：树 T 存 在 操 作 结 果:对 T 右 平 衡 操 作 void Ex c hange S ubT r ee(BB S T r ee&T)初 始 条 件：树 T 存 在 操 作 结 果:对 T 所 有 左 右 孩 子 互 换 int BBSTr e eDe p t h(B BSTr e e T)初 始 条 件:树 T 已 存 在 操 作 结 果:求 树 T 的 深 度 返 回：树 的 深 度 BBSTree Combi ne 2 T r e

5、 e(BBsT r ee T 1,BBST r e e T2)初 始 条 件:树 T 1 和 T2已 存 在 操 作 结 果:将 T1和 T2合 并 返 回:合 并 后 的 树 Statu s Spl i tBBS T r ee(B B S T ree Ttl,B B ST r e e&Tt2,o o oBBSTre e&T t 3,int x)初 始 条 件:树 Tt 1,T t 2,Tt 3 己 存 在,x 存 在 操 作 结 果：将 Tt 1分 裂 成 Tt2和 Tt3返 回：以 e 为 根 节 点 的 树 St a tus P r eOrder_ RecTra v e r se(BBS

6、Tree T)初 始 条 件:树 T 已 存 在 操 作 结 果：对 树 T 进 行 递 归 先 序 遍 历 输 出 返 回:成 功 T R U E 失 败 F A L S EStat u s InOrd e r_ Re c Traverse(BBSTr e e T)初 始 条 件：树 T 已 存 在 操 作 结 果：对 树 T 进 行 递 归 中 序 遍 历 输 出 返 回：成 功 TRUE 失 败 FALSES t atu s Las t Order_Re c Tr a verse(BBSTree T)初 始 条 件：树 T 已 存 在 操 作 结 果：对 树 T 进 行 递 归 后 序

7、遍 历 输 出 返 回：成 功 T R U E 失 败 FA L SEvoid Pr e 0 r d e r Tra v ese_I(BBSTree T)初 始 条 件:树 T 已 存 在 操 作 结 果:对 树 T 进 行 非 递 归 先 序 遍 历 输 出 v oi d In O rderTr a ve r se_ I(BB S T r e e T)初 始 条 件:树 T 已 存 在 操 作 结 果：对 树 T 进 行 非 递 归 中 序 遍 历 输 出 v o id LastOrd e rTra v es e _l(BBSTre e T)初 始 条 件：树 T 已 存 在 操 作 结 果

8、：对 树 T 进 行 非 递 归 后 序 遍 历 输 出 void Le v e lOrederTra v erse_Pri n t(BBSTree T)初 始 条 件:树 T 已 存 在 操 作 结 果:对 树 T 进 行 非 递 归 层 次 遍 历 输 出 void B r aNo t a t io n Prin t(BBST r e e T)初 始 条 件:树 T 已 存 在 操 作 结 果：对 树 T 用 括 号 表 达 法 输 出 ADT BBST r e e2.存 储 结 构 定 义#i n c 1 u d e#i n c 1 ude#d e f i n e O V ERFLOW-

9、1#define OK 1#de f ine ER ROR 0#define TRUE 1#d e f i n e FALSE 0#defineLH+1 左 高#defin e EH 0/等 高#d e f i n e RH-1/右 高 typede f int Rc d Type;t y p edef i n t S t a t u s;/*平 衡 二 叉 树 结 构 体*/ty p edef struct BBSTNode R c d Ty p e da t a;i nt b f；BBSTNode*1 c hild,*rchild;JB B ST N odeB B ST ree;3.算 法

10、 设 计/*求 平 衡 二 义 树 的 深 度*/i n t BBST r e e De p th(BB S T r e e T)i nt depth L eft,d epth R ig h t;if(N U LL=T)r e turn 0;elsedep t hLe f t=BBST r e e D e p th(T-lc h i 1 d);d e pthRi g ht=BBSTr e eDept h(T-r chi 1 d)；retur n 1+(dept h Left d epthRi g ht?d e pt h Lef t:dep thRight);)/*互 换 二 叉 树 所 有 结

11、 点 的 左 右 子 树 刃 void Ex c h a ng e S u bTree(BBS Tre e&T)BB S Tr e e temp;if(NU L L!=T)Ex c h a ng e Sub Tree(T-1 child)；/使 用 递 归 互 换 左 子 树 Exch a ngeSub T r e e(T r c h i 1 d);/使 用 递 归 互 换 右 子 树 i f(T-1 ch i Id!=N ULL)|(T-r c hild!=NULL)假 如 T的 子 树 有 一 个 不 为 空，则 互 换 左 右 子 树 t e mp=T lc h ild;T-lchild

12、=T-rch i 1 d;T-rc h ild=temp；/*左 旋 调 整*/v o id L_R o tate(BB STre e&p)BBST ree rc=p-r c hild;p-rc h i Id=r c-1 chi 1 d;r c-lch i Id=p;p=rc;/*右 旋 调 整*/v o i d R_R o tate(BBST r ee&p)B B S Tree 1 c=p-lc h ild;plchild=lc-r chil d;lc-rchild=p;p=1 c;)/*左 平 衡 解 决 操 作 刃 vo i d Lef t Ba 1 an c e(BBSTre e&T)

13、BBST r e e 1 c,rd;1c=T-lch i Id；sw i tch(lc-b f)case LH:T-bf=1 c bf=EH；R_Rotate(T);b r eak;case R H：rd=1 c-r chil d；s wit c h(rd-bf)case LH:T-bf=RH;1 c-bf=EH;b r eak;ca s e EH：T-bf=1cb f=EH;bre a k;c a se R H:T-b f=EH;1 c-b f=L H;bre a k;)rd-b f=EH;L_R otat e(T-lchi 1 d);R_Ro t a te(T)；b reak；/*右 平

14、衡 解 决 操 作*/void RightBa l a n c e(BBST r ee&T)B B S Tr e e rd,lc;r d=T-r c h i 1 d;sw i t c h(r d-bf)(case R H：T b f=rd bf=EH;L_Rotate(T);b r eak;cas e L H：lc=rd-lchild;s witch(lc-bf)c a s e R H:T-b f=L H；r d-b f=E H；b r ea k;c a s e EH:T-b f=rd-b f=E H；bre a k；case L H：T-b f=E H;r d bf=R H；bre a k;

15、lc-b f=E H;R_ R o t a t e(T-r c h ild);L _ R o tate(T);b r e a k;)/*平 衡 二 叉 树 的 插 入 操 作*/Sta t us Inse r tAVL(BBSTree&T,RcdT ype e,S t atu s&taller)i f(NULL=T)T=(BBSTree)ma 1 1 oc(s i zeo f(BBSTNode);T-data=e；T-bf=EH;T-lc h i Id=NULL;T-r child=NUL L;else if(e=Td a ta)书 中 已 存 在 和 e 相 等 的 结 点 t al 1 e

16、 r=F A LSE;return FALSE;e 1 se i f(e d ata)if(FALS E=InsertAV L(T-lchild,e,t a 1 ler)r etum FALS E;if(TRUE=t aller)sw i t ch(T-bf)ca s e LH:Lef t Bala n e e(T);tai 1 er=FA LSE；break;ca s e EH:T-bf=L H;tall e r=TRUE;break;c a se RH:T b f=E H；t a l l e r=FALSE;bre a k;el s e if(F ALSE=Inser t AVL(T rc

17、 h i Id,e,t a 1 1 e r)re t urnFALSE;i f(TRUE=taller)sw i t c h(T-bf)ca s e LH：T-bf=E H;t a Iler=F AL S E；brea k;c a s e E H:T-b f=RH;tal 1 er=T R U E;break;ca s e RH:R i ghtBalance(T);t a 1 ler=F A L S E；bre a k；return TRUE;)/*平 衡 二 叉 树 的 删 除 操 作*/Status D e leteAVL(BBS T r e e&t,RcdType e,Stat u s&

18、sho r ter)当 被 删 结 点 是 有 两 个 孩 子，且 其 前 驱 结 点 是 左 孩 子 时,tag=ls t atic int t a g=0;if(t=NULL)re t urn FALSE;/假 如 不 存 在 元 素，返 回 失 败 else i f(e=t-d a t a)BBS TN ode*q=NULL;/假 如 该 结 点 只 有 一 个 孩 子，则 将 自 子 树 取 代 该 结 点 if(t-lchil d=NULL)q=t；t=trch i 1 d;f r e e(q);sho r te r=TRUE;)e 1 s e if(t-rch i Id=NULL)

19、q=t;t=t-lc h il d;f ree(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;t-data=q-d a t a;i f(t-lc h i 1 d-d a t a=q-d ata)t a g=1；De 1 e t e A VL(t-lch i Id,q-d a t a,s h orter);if(tag=l)BBS T

20、re e r=t-r c hi 1 d;if(NULL=r)t-b f=0;e I s esw i t c h(r-b f)ca s e EH:t-b f=-1；brea k;def a u I t:Righ t Bal a n ce(t);b reak;)e Ise if(eda t a)(/左 子 树 中 继 续 查 找 if(!D eleteAV 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-

21、bf=EH;s h ort e r=T R UE;break;case EH:t-b f=RH：s h orter=FA L SE;bre a k;/假 如 本 来 就 是 右 子 树 较 高，删 除 之 后 就 不 平 衡，需 要 做 右 平。衡 操 作 c a s e 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(e t-d a t a)右 子 树 中 继 续 查 找 if(!De 1 e t eAVL(trch

22、ild,e,s h o rter)re t u r n FAL SE;)删 除 完 结 点 之 后，调 整 结 点 的 平 衡 因 子 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 1 d-bf=EH)/注 意 这 里，画 图 思 考 一 下 sh o r t e r=F A LS E;e 1 seshorte r TR U E;b r eak;case E H：t-bf=LH;sh o rt e r=F A LS E;br e ak;ca s e RH:t-b

23、f=EH;shorte r=T R U E;br e a k;)if(t a g=1)i n t d印 thL e ft=BB S T r eeDepth(t-1 child)；in t dep t hR i gh t=BBSTreeDep t h(t-rch i I d);t b f=de p t hLef t-dep t hRig h t;)retur n TRUE;)/*平 衡 二 叉 树 的 查 找 操 作 列 BB S Tr e e SearchAVL(BBSTree T,R c dT y pe e)i f(T=N U LL)r e turn NULL；i f(e=T-data)re

24、tur n T;else i f(e T-da t a)return S earch AV L(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 ead=p=q=NU L L;i n t m;i f(k!=n)sea n f(”d”,&m);p=(Ar r a yNode*)m a 1 1 oc(si z e of(Arr a y N o d e)；h e ad=p；p-data=

25、m;k=g etchar()；while(k!=,n,)scanf(n%d,&m)；q=(Array Node*)m a 1 1 o c(s izeof(ArrayNo d e)；q-d a t a=m；p-n ex t=q;p=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 k eBB S T ree()i nt i=0;S ta t us ta 1 le r=

26、T RUE;B B STree T=NULL;Ar r ay a;a=G etl n p u tT o A r ray();while(a!=N ULL)tai 1 e r=TRUE；I ns e rt A VL(T,a-da t a,t a Iler)；a=a-nex t；)r etu r n T;)/*递 归 先 序 遍 历*/Status P r e O r d e r _ R e c T ra v e rs e(BBS Tre e T)if(NULL=T)r e tu r n OK;p r in t ff%d”,T-data);P r eOrd e r_R ecTra v er s e

27、(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 nOrder_RecTraverse(T-1 c hi 1 d)；printf(M%d n,T-d ata);if(T-rchild)I nOrd e r_R e cTraver s e(T r c h i 1 d);)/*递 归 后 序 遍 历*/Statu s LastOr d er_RecTr a ver s e(B B STreeT)if(

28、T-lchild)L a 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);p rin tf(n%d,T-d a ta)；/*找 到 最 左 结 点*/B B ST r e e G o F a r L e f t(BBSTr e e T,LS t a c k&S)if(N U LL=T)r e t u r n NU L L；wh i 1 e(T lchild!=N U L L)P u sh_LS(S,T);T=T-1 c hil d；)return T;

29、)/*非 递 归 中 序 遍 历*/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 h ile(p!=NULL)print f(%d”,p-d a t a)；if(p-r chi!d!=NULL)p=GoFa r L eft(p-r ch i 1 d,S);)e 1 se if(StackE m pty_L S(S)!=T R U E)P op_L S(S,p)；e Is e p=NU LL;)BBST r e e

30、 V i sitFarL e ft(B BSTr e e T,L S t a c k&S)if(N U L L=T)r e tu r n NULL;假 如 T 为 空，则 返 回 空 prin t f(”d,T-d a ta)；/先 序，先 读 取 结 点 数 据 w h i le(T-lc h i ld!=NULL)Push_LS(S,T);/入 栈T=T 1 c h ild;/遍 历 下 一 个 左 子 树 p r i n t f(%d,T-d a t a);下 一 个 结 点 的 读 取 数 据)r et u r n T;)/*非 递 归 先 序 遍 历*/v o id P r e O

31、r d e r T r a vese_ I(BBSTre e T)L S tack S；InitSt a ck_LS(S);BBSTre e p;p=Vi s itFa r L e f t(T,S);/先 将 左 边 的 数 据 先 序 读 取 whil e(p!=NULL)if(p-rc h i 1 d!=N U L L)/假 如 最 左 下 结 点 的 右 子 树 不 为 空 p=V i s itFarLeft(p-r c h ild,S);/执 行 遍 历 该 结 点 的 左 子 树 e l s e i f(Sta c kEmp t y_LS!=TRU E)P op_L S(S,p)；/

32、假 如 S 不 为 空 栈，出 栈 else p=NULL；/假 如 为 空 栈，p 赋 予 空/*非 递 归 后 序 遍 历*/vo i d L a st 0 rder T rave s e_ I(BB STr e e r oot)BBS T ree p r o o t;BB S Tree s t ac k 30；i n t num=0;B B S T r e e have_vis i ted=NULL;while(NULL!=p|num 0)while(N ULL1=p)st a c k n u m+=p；p=p-l c hild;)p=s tacknum-l；if(NULL=p-rc h

33、 il d|I hav e _vi s ited=p-r c h i 1 d)p r intf(H%d u,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(Hn,r);)/*非 递 归 层 次 遍 历 输 出 一 棵 二 叉 树*/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!u);if(T!=NULL)LQ u eue Q;InitQue u e

34、 _LQ(Q);BB STree p=T;printf(%d n,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(M%d p-1 chi 1 d-data);EnQueu e _LQ(Q,p-l c h ild)；)if(p-rchild!=NULL)printf(n%d,p-rchi 1 d-d ata);EnQueue_L Q(Q,p-r c hild);)/*括 号 表 达 法 输 出 平 衡 二 叉 树*/void BraNota t io n P r int(B

35、B S Tree T)if(NULL=T)prin t f(n 空!)e lseif(T!=NULL)if(T!=NULL)pr i n t f(%i,T-data);if(T-lch i ld|T-r child)printf(C)；)if(T-l child|T-rchi I d)i f(T-1 child)BraNota t i o nPrint(T lc h i I d)；)e 1 s e if(T-rchild)printf(#)；p rintf;if(T-rc h i Id)BraNo t a t i o n P rint(T-rc h i Id);e Ise if(T-1 c h

36、 i Id)p ri n t f(#);)pr i nt f()；/*将 一 棵 树 转 换 为 一 个 数 组*/Array Ge t A r r a y F romTree(B BST r e e T)S t a tus f i r stTim e=TRU E;Ar r ay h e a d=N U LL；Array Node*b=NULL;A r rayNod e*q=NU LL;i f(T=NULL)pr i n t f(n T h e t r ee is e m pty!”)；)if(T!=NULL)LQu e u e Q;I n itQue u e _LQ(Q);BBSTree p

37、=T；q=(Arr a y)m a Hoc(s i zeof(Ar r a y N o d e);q-dat a=p-data；i f(f i rstTime=TRUE)head=q;firstTime=F ALS E；b=q；e 1 se b-nex t=q;b=b-next;)E nQ ueu e _ LQ(Q,p);while(DeQueue_ L Q(Q,p)i f(p-l child!=NULL)q=(Arr a y)mal 1 o c(s i z eof(A r r a y No d e);q-da t a=p-lc h il d-dat a;b-n e xtq;b=b-next；

38、En Q ue u e_ L Q(Q,p-1 c hild);)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!=N U LL)b-next=NULL;。)re t urn h ead；/*将 两 棵 平 衡 二 叉 树 合 并 成 一 颗 平 衡 二 叉 树*/BBSTree Combine2Tree(B B S Tree T l,BBS Tree T2)S

39、t atu s t a Iler=T RU E;Arra y a=NULL;a=G etArray F r o m Tree(T2)；w h i l e(a!=NULL)tai 1 e r TRUE;I n s e r t A VL(T 1,a d a t a,ta lle r);a=a-n ext;)return T 1;)/*将 一 棵 平 衡 二 叉 树 分 裂 成 两 棵 平 衡 二 叉 树*/*参 数 1：要 进 行 分 裂 的 树 参 数 2:分 裂 出 来 的 小 于 等 于 x 的 子 树。参 数 3：分 裂 出 来 的 大 于 x 的 子 树。参 数 4：关 键 字 x*/S

40、tatus S p litBB S T r ee(BBSTre e T il,BBST r e e&T t 2,B B S T r e e&Tt3,int x)A r r a y a=N U LL;S tatus ta 1 1 e r;a=GetA r r a yFromTree(Tt 1);i f(T tl=N U L L)r e tu r n FALSE;e 1 sew h i 1 e(a!=NULL)if(a-d ata d a ta,tall e r);a=a-n e xt;el s e tai 1 e r=T R U E：Ins e r t A V L(Tt3,a-da t a,ta

41、 1 le r);a=a-next;r e t u rn T R U E；4.测 试(1)建 树 操 作 测 试 代 码：BBSTree T1=NULL;printf(”请 输 入 树 的 结 点 数 据，按-1结 束：”)；Tl=MakeBBSTree();BraNotationPrint(Tl);/用 括 号 表 示 法 输 出 return 0;测 试 数 据：1 2 3 4 5 6测 试 结 果：清 输 入 树 的 结 点 数 据，按-1结 束：1 2 3 4 5 6-14(2(1,3),5(#,6)T 1I j 011 2 向%IH(2)插 入 操 作 测 试 代 码:princf(

42、”n请 输 入 要 插 入 的 数 据：”);scanf(电 d”,&加);getchar();taller=TRUE;InsertAVL(Tlr m,taller);BraNotationPrint(Tl);/用 括 号 表 示 法 输 出 测 试 数 据：1 2 3 4 5 6 插 入 8测 试 结 果：请 输 入 要 插 入 的 数 据：84(2(1,3),6(5,8)T1r o iHA6 0IE E测 试 数 据：1 2 3 4 5 6 插 入 4测 试 结 果：请 输 入 要 插 入 的 数 据：44(2(1,3),5(#,6)T1前 11 G i f H(3)删 除 操 作 测 试

43、 代 码：p r i n t f(n请 输 入 要 删 除 的 数 据：”)；s c a n f(n%dr&ir);g e t c h a r();s h o r t e r=TRUE;D eleteA V L(T lr ir,s h o r t e r);B r a N o ta ti o n P r i n t(T l);/用 括 号 表 示 法 输 出 测 试 数 据：1 2 3 4 5 6 删 除 6测 试 结 果：请 输 入 要 删 除 的 数 据：64(2(1,3),5)T 1H L IA.测 试 数 据：1 2 3 4 5 6 删 除 2测 试 结 果：清 输 入 要 删 除 的

44、 数 据：21 4(1(#,3),5(#,6)T 1 A1E tm测 试 数 据：1 2 3 4 5 6 删 除 4测 试 结 果：清 输 久 要 删 除 的 数 据：43(2(1,#),5(#,6)T 1j o|AI C LB(4)查 找 操 作 测 试 代 码:prints(”n请 输 入 要 查 找 的 数 据：”)；scanf(n%dwr&口);getchar();shorter=TRUE;T1=SearchAVL(Tlr ro);BraNotationPrint(Tl);用 括 号 表 示 法 输 出 测 试 数 据：1 2 3 4 5 6 查 找 5测 试 结 果：清 输 久 要

45、查 找 的 数 据：515 熊 6)T1I J-1 I H(5)输 出 测 试 代 码:BBSTree T=NULL;p r m t f(W：)；T=MakeBBSTree();p r in t f(”nT为:n);BraNotationPrint(T);p r in t f(nn);printf(二 途 归 先 序 遍 历 输 出：”)；PreOrder_RecTraverse(T);p r in t f(”n”)；p rin tf L n菲 递 三 失 二 与 历 输 出：”)；PreOrderTravese_I(T);p r in t f(nn);printf(”n速 归 中 子 退,输

46、 出：r,);InOrder_RecTraverse(T);p r in t f(nn);printf(,r 三 二=与 方 输 出：”)；InOrderTraverse_I(T);p r in t f(nn);printf(,rr.：5 三 三 子 名 用 输 出：)；LastOrder_RecTraverse(T);p r in t f(wnn);prin七 一”n菲 递 归 后 序 遍 历 输 出：n);LastOrderTravese_I(T);p r in t f(”n);测 试 数 据：1 2 3 4 5 6测 试 结 果:请 输 入 数 据：1 2 3 4 5 6 7 8 9T为

47、：421.3）.65.87.9）递 归 先 序 遍 历 输 出：4 2 1 3 6 5 8 7 9非 递 归 先 序 遍 历 输 出：4 2 1 3 6 5 8 7 9递 归 中 序 遍 历 输 出：1 2 3 4 5 6 7 8 9非 递 归 中 序 遍 历 输 出：1 2 3 4 5 6 7 8 9递 归 后 序 遍 历 输 出：1 3 2 5 7 9 8 6 4HE递 归 后 序 遍 历 输 出：1 3 2 5 7 9 8 6 45.思 考 与 小 结 在 完 毕 平 衡 二 叉 树 实 验 的 过 程 中，所 碰 到 的 最 大 问 题 就 是 如 何 实 现 平 衡 二 叉 树 删

48、除 结 点 的 接 口.由 于 课 本 没 有 涉 及 到 这 个 知 识 点，所 以 自 己 只 能 通 过 阅 读 其 他 书 籍 和 通 过 参 考 网 上 的 资 料 来 对 这 个 过 程 有 了 进 一 步 的 理 解。另 一 方 面 自 己 想 了 一 个 树 的 括 号 表 达 法 来 将 一 棵 树 打 印 出 来，这 对 于 一 棵 树 的 表 达 是 挺 有 用 的。总 的 来 说,平 衡 二 叉 树 这 个 知 识 点 涉 及 到 的 算 法 大 约 就 是 添 加 结 点，删 除 结 点，查 找 结 点 这 三 个 方 面，而 其 他 的 接 口 都 是 以 这 三

49、个 为 基 础，实 现 进 一 步 的 拓 展。6.源 代 码/*(1)根 据 输 入 字 符 串 创 建 一 棵 平 衡 二 叉 树 BBST r ee M a keBBST r ee();(2)平 衡 二 叉 树 插 入 元 素 操 作 Status Ins e r tA VL(BB S Tree&T,R c dTyp e e,S t a t u s&taller)；(3)层 次 遍 历 输 出 二 叉 树 v oid LevelOred e rTraver s e _Pr i nt(B B STre e T);(4)括 号 表 达 法 输 出 二 叉 树 v oid BraNotatio

50、nP r int(BB S T r e eT);(5)平 衡 二 叉 树 删 除 元 素 操 作 S tat u s De 1 e teA V L(BBSTre e&t,Rc d T y p e e,St a tu s&s h o r t e r);(6)求 平 衡 二 叉 树 的 深 度 i n t BBST r e e D e p th(B BSTree T);(7)互 换 所 有 结 点 的 左 右 子 树 void E x c hange S ubT r ee(B B S Tree&T)(8)递 归 先 序 遍 历 St a t u s PreOr d e r _R e cTr a v