2023年全线索二叉链表实验报告.pdf

《2023年全线索二叉链表实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年全线索二叉链表实验报告.pdf（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全线索链表应用报告提交人:郭超峰班级：计算机1 4 0 4学号：2 0 2 3 3 6 7 8一：问题定义及需求分析二:概要设计三:具体设计四：调试分析五:使用说明六:测试结果（截屏）七：组内个人设计部分八：附录（带源代码）一:问题定义及需求分析课题:全线索链表应用课题描述:对二叉树的二叉链表结点增长两个指针域，前驱指针p ri o r和后继指。针n e x t。通过该结点构造全线索二叉链表。课题规定：设计一个全线索二叉链表的应用程序。1）创建全线索二叉树。2）完毕全线索二叉树的重要基本操作。3）给出简朴应用实例。输入输出形式：本实验中全线索二叉树元素均为整形（i nt）o程序功能：1：创建二

2、叉树。2：对二叉树中序遍历进行全线索化。3：求树中任意元素的前驱、后继、左孩子、右孩子。4:对二叉树进行元素的插入和删除。5：对二叉树的清空操作。测试数据:测试的二叉树为如下二：概要设计typ e de f struct Bi T hrN o d e int data;struct B iThrN o d e *I c hild,*r c h i 1 d/prior/ne x t;B i ThrNode,*BiThrTree;/抽象数据类型B i Thr No d et ype d e f s t ructEI e m Type dat a 10 0；int Sta c ksize;S q S

3、 t ack；/抽象数据类型SqSt ackvoid*lni t Sta c k(S q S t a c k*p)；初始化栈int St a c k Empty(S q S ta c k*S);判断栈空int Push(SqStac k*S,日 e mType e)；/入栈E lemT y p e P o p(SqSta c k*S，日emTyp e e)；出栈B i Th r Tr e e C r ea t BiTree(Bi T hrTr e e p)；二叉树的构建BiThrTree I n 0 rd e r T hre a d i ng(BiThrTree p)；中序线索化i nt 1

4、n 0 r d e r(BiT h r T ree p);求中序序列i n t q ian q u(B iT h rTr e e p);求前驱int houji(BiThrTr e e p)；/求后继i n t zuoh a i(BiTh r T ree p);求左孩子int yo u h ai(BiTh r Tree p);求右孩子int In s ert(BiThrTree p);/插入元素int D e lete(B i T h r Tree p);删除元素int Clear(BiTh r T re e p)；/将二叉树清空I nt ma i n()解相应问题三:具体设计各模块的算法如下

5、：Status lnitStack(SqStac k*p)初始化栈p.Sta c ksize=1;return OK;)S tat u s St a c k Em p t y(SqSt a ck*S)/判断栈空if(p S t a ck s i z e=-1)ret u r n TURE；else r e t u rn F A LSE;主函数调用上述函数求)Status P ush(SqStac k*S,ElemType e)/入栈P-S t a c k s ize=p S t a cksiz e+1;P-dat a p-Stacks i ze=e;r e turn 0 K;)Stat u s

6、 Po p(SqStack*S,E 1 emTyp e e)出栈e=p-datap Stacksize；P-S tac k si z e=p-Stacksize-1;r e tu r n e;)S t atu s C reat B i T r ee(BiTh r Tre e p)/二叉树的构建s ca n f (&m)；if(m=0)p=N U LL;e 1 sei f (!(p=(BiThrT r ee)mall o c(si z eo f(BiThrNo d e)ex i t(OVERF L OW);/存储分派失败e I s e p-d a ta=m；p-p rior=N U L L；p

7、next=N ULL;p-lchi 1 d=NULL;p-r c h ild=NULL;p-l c h i 1 d=Cr e a tB i Tr e e(p-1 ch i I d);/递归构建左子树p-rc h ild=C r e a tB i T r e e(p rchild);递归构建右子树)ret u r n p;返回头节点)S t a tus InOrd e r T h reading(B i ThrTree p)中序线索化In i tSt a ck(&S)；if(!(Th r=(B iTh r T re e)ma 1 1 oc(sizeof(B iThrNo d e)exit(OVE

8、RFLOW)；存储分派失败T h r-d ata=O;Thrlch i 1 d=p;/T h r 为头节点Thr-r child=NULL；p 1 =p;p r e=Thr;/p r e 为全局变量，指 向 pl的前一个节点wh i 1 e(pl I|!StackEmpty(&S)i f(p l)P u s h(&S,p l)；p 1 =p l lchild;/进栈)else(pl=P o p(&S,pl);出栈p re-n e x t=p l;P l-prior=pre;中序线索化pre=pl;pl=p 1 -r c h i 1 d;)pr e-nex t=T h r;最后一个节点线索化Th

9、r-p r ior=p r e;r eturn T h r；返回头节点)Sta t us I nOrder(B i ThrTree p)求中序序列for(pl=pnext；pl!=p;p 1 =pl-nex t)p ri ntf(pl-dat a);输出节点值求前驱、后继、左孩子、右孩子思绪差距不大，下面以求前驱为例：S tatus q i anqu(BiThrTree p)/求前驱s canf(&e);输入要查找元素fo r (p2=p n e xt;p2-data!=0;p2=p2-nex t)逐个检查树中元素if(p 2 d a ta=e)p3=p 2 prior;if(p3-da t

10、a=0)P r i ntf(该点不存在中序前驱！”)；b reak;elseprin t f（“该点的中序前驱为：）;printf(p3-data);brea k；)S tat u s In s e rt(B iT h rT r eep)/插入元素p2=(BiTh rTree)malloc(sizeof(B i T h r Nod e);P rintf(输入所要 插 入 的 节 点s ca n f(&a);P ri n t f(输入所要查找的节点的；scan f(&b)；fo r(pl=p-nex t；pl!=p;p 1 =p 1 -n e xt)i f(pl-data=b)brea k；)i

11、 f(P 1 =P)输出e的前驱/逐个检查树中元素P r in tf（该节点不存在！n ）;elsesw i tch(j)c a se 1:/插入元素作为左孩子p2 d a ta=a;p2-lch i ld=NU L L；p 2-rchild=N U LL;p2 n e x t=p 1;p2-prio r=p l p rio r；p l-p ri o rn e xt=p 2;pl p r ior=p2；p llc h ild=p 2;break;)c ase 2:/插入元素作为右孩子p2 d ata=a;p 2 lchil d=NULL;p2rchild=N ULL；p2-prio r=pl；

12、p2-ne x t=pl-n e x t;p 1 -ne x t-p rio r=p 2;pl-n ex t=p 2;p 1 -r c hild=p2;b r eak;)d e f a u 1 t:e x i t(0)；)/s witch/e 1 s eS t atu s Dele te (B iT h rT ree p)/删除元素s can f(&a);输入要删除的元素f o r(p l=p-n ext;pl!=p;p 1 =pl-ne x t)/逐个检查树中是否有此元素if(plda t a=a)b re a k;)if(P 1=p)printf(“该树中无此节点!“);elseif(p

13、1=p l-p r ior-rch i I d)/元素作为右孩子p lprio r-n e x t=pl-n ext;pl-n ext-p rior=pl-p rior;pl-p rior-r c hil d=NULL;fre e(pl);释放 Pli f(pl=p 1 -n e xt-l c hi 1 d)/元素作为左孩子p lprior-nex t=pl next;p 1 n ext-p r i o r=plprior;pl-n e xt-l c hi 1 d=NULL；fr e e(pl);/释放pl)/el s e/De 1 eteStatu s Clea r(BiTh r T re

14、e p)/将二叉树清空for(p 1=p-n e x t；p 2!=p；)p2=pl-next;fre e(p 1)；释放节点 p lP 1=p2;)f r e e(p);释放头节点四:调试分析1:对所碰到问题的解决方法及分析1）建立二叉树时碰到问题：输入时未使用。来表白无左右孩子，导致递归无法结束，因素是为理解递归建立二叉树的过程。2）建立二叉树后进行相应问题的求解后,无法进行多次求解，经分析后采用子函数互相调用的方法顺利解决。3）其余一些程序语法及逻辑错误，经组内成员严谨排查顺利解决2；算法的时空分析及改善设想1）算法时空分析湘应算法的时间复杂度均为0（n）2）改善设想：1）可以使用函数指

15、针来使用求前驱、后继、左孩子、右孩子等子函数。2）或许可以使用一子函数代替程序中实现多次求解的代码,简化程序。五：使用说明如下依次输入。0 3 0 0 得到原始二叉树:峋造三叉树:;输入兀素：输入兀素：趟1人兀素输入元素：1 0、融入兀素：I o%人 元 素：二 L输入元素：然后进入菜单界面如下:,*全线索二叉树*,*1：求前驱*,*3:孑 *卜*4:求右孩子*卜*5:插入兀素*,*6:册）|除元素*7:求中 序序列*,*8:清空二叉树并退出*，入要进行的项目：之后按环节进行相应问题求解!六:测试结果（截屏）第一项测试:求6的前驱得到2,测试成功!w*+线 索 叉树*M*求 市 弱 区*4:*

16、5:插入兀素*6:*7 中 歹 1*卜长*8:清空二叉树并退出*输人要进行的项目：输入要查找的元素:该点的中序前驱为:继续按1,退出按0162第二项测试：求5的后继得到7,测试成功!*-幺 戋 根 y*4:求右慈子*5 .yj_*6:册|除兀素*7 中 歹 ij*8:清空二叉树并退出*输入要进行的项目:输入要查找的元素:该点的中序前岖为:继续按1,退出按01输入要进行的项目:输入要查找的元素:该点的中序后继为:继续按1,退出按0162257第三项测试：求5的左孩子得到6,测试成功!进查中1,要要的按*全线索二叉树*：*6:册，除兀素*：*7 :求中序序歹 lj*退出按0行找序目素为刻项元继W的

17、的后出退16225735第四项测试：求2的右孩子得到5,测试成功!卜*5 :J /T Q *卜*6:册|除兀素*=;*卜*7:求中 序序列*卜*8 ：清空二叉树并退出*检人要进行的项目:愉人要查找的元素:该点的中序前驱为:限续按1,退出按0162恸入要进行的项目:恸入要查找的元素:悭点的中序后继为:怅续按1,退出按02571恸入要进行的项目:翁人要查找的元素:该点的左孩子为：6除续按1,退出按035142檎入要进行的项目:自入要查找的元素:核点的右孩子为：5限续按1,退出按0第五项测试:将9 插入做为6 的左孩子，测试成功!卜*+线率一叉根F 比*4:*求*,*1*,*4 *卜*5:插入元素*

18、卜*6:册（|除兀素*卜*7 :求中序序歹肝*卜*8 清空二叉树并退出*悔入要进行的项目：5输入所要插入的节点：9掩入所要查找的节点：6k*1:插入为左孩子*卜*2：插入为 右孩子*他择操作：1区续按1,退出按。府人要进行的项目：3输入要查找的元素：6假点的左孩子为：9阿续按1,退出按。第六项测试:删除节点4后 求2的左孩子，结果不存在，测试成功!*至线李叉树*3 ：枣左孩子*4:求右孩子*6:1 *7 :求中 序序歹l j*8:清空二叉树并退出*输入要进行的项目：6输入您要删除的节点：4继续按1,退出按01输入要进行的项目：3输入要查找的元素：2该点不存在左孩子！继续族1,退出按0第七项测试

19、：求中序序列得到42 6 85713,测试成功!*5678*7*并*询:退梆进列131,*要序57按*入序68续擀输中142继*七：组内个人设计部分typede f str u ct B i ThrNo d e in t data；s truct B i T hrNo d e*lch i 1 d,*rchi 1 d,prior,*n ext;Bi T hrNo d e.*Bi T hrT r e e;抽象数据类型B iTh r NodeB i T hrTree C re a tBi T ree(Bi T h r Tree p);二叉树的构建B i ThrTr e e InOrderTh rea

20、 d ing(BiThrTree p);中序线索化int I n se r t(BiThrTree p);/插入元素i n t D e 1 e t e(B iTh r T r ee p);删除元素I n t main()主函数调用上述函数求解相应问题i n t I n 0 r de r(BiTh r T r e e p)；求中序序列i n t qi a n q u(BiT h rT r e e p);求前驱七：附 录（带源程序）注：算法中已经带有注释，故下列代码不反复含注释!#incl u d e#in c 1 ude#d efi n e INIT STACK SIZE 100#d e f i

21、 ne STACKINCRE M E NT 10#d e fin e OV ERF LOW -2#de f i ne ERROR-1#define OK 1ty p e d e f s t r u ct BiT h rNod e i n t data；s t r u ct B i ThrNode*I c hi 1 d,*r c h ild,*p r i o r,*next;B i ThrNod e,*Bi T h r T r ee;typ e def Bi T h r N o de*EI e m T y p e;type d e f s t r uct日em Typ e data 1 0 0;

22、in t Stac k size；SqStack;BiThrTree pre;int main()Bi T hrTr e e C r e atB i Tree(B i T hrTr e e p);B iT h r Tree InO r d erT h r e ad i n g(BiThrT r e e p)；int I n Orde r(BiThrT r e e p);in t q ianq u(B i ThrT r e e p)；in t h ouji(BiT h r T r e e p);int zuoha i(Bi T hrT r e e p);i n t youhai(BiTh r T

23、 r e e p)；i nt lnsert(B iThrTr e e p);i n t Del e t e(B iThrTre e p)；i n t C 1 e a r(BiTh r T r ee p)；i nt a;Bi T h rTree T;T=N U LL;printf(构造二叉树：n );T=CreatBiTree(T);p r intf(二叉树建立完毕！n”);T=lnOr d e rThr e ading(T);sy s tem(Hc ls);prin t f(”*n);pr i nt f(”*rpg区*pHntf(”*2 继*n”)；p ri n 廿(”*)prjntf(”*4

24、.*口p r n tf(”*5.1t*n”)；p r i n t f(H*6:删除元素*n”)，p r in t f(”*7.中 歹 ij*n);p rin t f(”*g 空211树并1出*火 *n”)，p r in t f（输入要进行的项目:）；scanf(%d;&a)；swi t c h(a)c ase 1：qi a nq u(T)；bre a k；c a s e 2：h o uj i(T);br e ak;c a s e 3：z u o hai(T);b r e a k;case 4:youha i(T);brea k；cas e 5：Ins e rt(T);bre a k；cas e

25、 6：De 1 ete(T)；br e ak;c as e 7:I nOrde r(T)；break;case 8:Clear(T);ex i t(0);r e turn O K；)in t InitS t ack(SqStack*p)p-Stacksize=l;retu r n 0;i nt P ush(S q S tack*p,ElemT y p e e)p-S tac k s i z e=p-S t a c ksize+1;p-d atap-S t acksize=e;r e t urn 0;)日em T ype Pop(S q Stac k*p,日 e mType e)e=p d a

26、t ap-St a c k size；p-S ta c ksize=p-S t ac k size-1;r e t urn e；Bi T hrTree C r e a tBiTre e(B iThrTre e p)int m;prin t f(输入元素:n);scanf(%d ,&m)；if(m=0)p=N U LL;e lsei f (!(p=(B iThrT r ee)malloc(si z eof(B i T h rNode)exi t(0);e Is e(p-d a ta=m；p prio r=NULL；p-nex t=NULL;p-lc h il d=N U LL;p-r child

27、=N ULL;p-l c h ild=CreatBiTr e e(p-1 c h ild);p r c h i ld=CreatBi T r e e(p-rch i Id)；)r etu r n p；)int Stac k Emp t y(S q S t a ck*p)i f (p-S t a ck s iz e=-l)r e turn 1;else r e turn 0;)BiTh rT r ee InOrd e rThre a ding(BiThrTre e p)i nt Init S ta c k (S q S tack*p)；int S t a ckEmp t y(Sq Stac k*

28、S);int P u sh(S qStac k*S,ElemTyp e e);E lemT y p e P o p(S qSt a c k*S,ElemType e);BiThr T ree T hr;Sq S tac k S;InitS t ack(&S);B iThrT r e e pl;i f (!(T h r=(BiThrTr e e)mal 1 oc(siz e o f(B iThrNode)exit(O VER FLOW);Thr-d a ta=0;Th r-l c hi 1 d=p;T hr-rchil d=NU L L;P 1 =P；p r e=Th r；while(p 11

29、1 !StackEmpt y(&S)i f(pl)Pus h(&S,pl);pl=pl-1 c hild;e lsepl=P o p (&S,p l)；pre-ne x t=p 1 ；p l-prio r=p r e；pr e=pl；pl=p 1 r child;)pre-n ext=Thr;Th r-prio r=pr e；p r int f(二叉树线索化完毕！n r e tu r n T h r；)int qian q u(BiThrTr e e p)int houji(B i ThrTree p)；i n t zu o ha i(BiThrT r ee p);in t y o u h a

30、 i(BiTh r T r ee p)；i n t Ins e rt(B i ThrTr e e p);i n t I n Orde r(B i T hrT r ee p);i n t Delete(BiT h rTree p);i n t C 1 ea r(BiThrT r ee p);int e,m,j；p rin tf(输入要查找的元素：);s c anf(n%d/&e);BiThrTre e p2;BiThrTree p3;for(p 2=p-ne x t；p 2-da t a!=0;p2=p2-ne x t)if(p 2-data=e)p 3=p 2-p rio r；i f(p3-d

31、 ata=0)P ri n tf(该点不存在中序前驱！n)；b r eak;)e ls e printf(该点的中序前驱为：);pr i nt f(%dn,p3-data);br e a k;)prin t f(继续按1,退出按0n);scan f(%d,&j);if。)p r intf(输入要进行的项目:)；s c anf(%dsw i tch(m)c a se l:qianqu(p)；b r eak;case 2：h o uji(p);b r eak;c a se 3:z u ohai(p)；break；c a se 4:youha i(p);b r ea k；c ase 5:lnser

32、t(p)；b r e a k;c a se 6:Delete(p);bre a k;ca s e 7:lnO r der(p);bre a k;case 8：Cl e ar(p);exit(0);)el s e e x it(O);r eturn 0;int h o u j i(B iT h rT r ee p)int qia n q u(B i T hr T r e e p);int z uo h ai(Bi T hrT r ee p);in t youh a i(BiTh r T r e e p)；int In s ert(B i Th r T r e e p)；int InO rder(

33、B i Th r Tree p);i n t D e Ie t e(B iT h r Tre e p)；int C lear(B iThrTre e p)；int e,m,j；p r i n t f(“输入要查找的元素：”)；scanf(M%d,&e);BiThr T r ee p 2;BiThr T r e e p3;f o r(p 2=p-next;p2!=p;p 2=p2-next)if(p 2-d ata=e)p 3=p2-n e x t;if(p 3 da t a=0)pr i ntf(该点不存在中序后继!n);b reak;)elseprin t f(该点的中序后继为：)；prin

34、 t f(n%dn H,p 3-data);brea k；)printf(继续按1,退出按0n );s c anf(%d j);i f(J)(prin t f(输入要进行的项目:)；sea n f(%d,&m);s w i tc h(m)ca s e 1：q i a n qu(p);brea k；c ase 2:h o uji(p);br e ak；case 3：z uohai(p);b rea k；c as e 4:y ouh a i(p)；b reak;cas e 5：I nser t(p);brea k;case 6:Del e te(p)；b reak;case 7：I n Orde

35、r(p);br e a k;c a se 8：C 1 e a r(p)；e x it (0);else ex i t(0);re t u rn 0;)i n t zu o ha i(Bi T hrT r ee p)int qi a n q u(BiTh r Tree p)；in t houji(B i ThrTre e p)；int you h ai(BiTh r T ree p);i n t In s ert(B i T hrTree p);i n t In 0 r der(B iTh r T ree p);i n t De 1 ete(B i ThrTree p)；in t Clear(B

36、 iThrT r e e p);i n t e,m,j;printf(输入要查找的元素：)；sc a nf(%d”，&e);B i T h r T ree p 2；B i Th r T re e p3；for(p 2=p-next；p2!=p;p 2=p2-next)if(p 2-d ata=e)p3=p 2 lc h ild;if(p3=NULL)printf(该点不存在左孩子!n)；b rea k；els e(printf(该点的左孩子为：)；printf(%d n,p 3-d a t a);break;)pr i n t f(继续按1,退出按0n);s can f(%dz&j);i f(

37、j)prin t f（输入要进行的项目：）；scanf(n%d ,&m)；sw i tch(m)case l:qianqu(p);b reak;ca s e 2:houji(p);b reak;case 3:zuo h a i(p)；b r eak；c a s e 4:youha i(p);br e ak；ca s e 5:1ns e r t(p)；br e a k；c a se 6：D elet e(p)；break；case 7:I nO r d e r(p);bre a k;c a se 8:Clear(p);exit(O);)els e e x it(0);return 0；)int

38、yo u hai(B i T h rTr e e p)int qianqu(B iTh r Tre e p)；int h o uji(BiThrTree p);int zuo h ai(BiThrTree p);i n t I n s ert(BiThrT re e p)；int InOrder(BiT h r T r e e p);i n t D e 1 et e(BiThr T re e p);int C 1 e a r(BiTh r Tree p);in t e,mJ；printf(H输入要查找的元素:)；s c a nf(%d,&e)；BiThrT r e e p 2;BiThrT r

39、 e e p3;fo r (p2=p-next；p2!=p；p2=p 2-n ext)i f (p2-d ata=e)p3=p2-rc h i 1 d;i f(p3=NULL)print f (该点不存在右孩子!n);break；)e Is e(pri n t f(该点的右孩子为：)；printf(%dn,p3-d a ta);br e a k；)printf(继续按1,退出按0n )；scanf(%d,&j);if(j)(pr i n t f(输入要进行的项目：)；sea n f(%d ,&m)；sw i t c h(m)c ase 1 ：q ia n qu(p);b rea k；cas e

40、 2：houji(p);brea k；c a se 3：zuohai(p);br e ak;case 4：you h ai(p);bre a k;c ase 5：I n s er t(p)；brea k；ca s e 6:Del e te(p);brea k；case 7：I n Orde r(p)；b r e a k；ca s e 8:C lear(p);exit(O);)el s e e xit(O);r etu r n 0;in t In 0 rd e r(BiTh rTre e p)i n t q i anq u(Bi T hrTr e e p);int houji(BiThrTree

41、 p);in t zuo h a i(B iThrTree p);i n t yo u hai(B i T h rTre e p)；int Ins e rt(BiTh rT re e p)；i nt Deletef B iThrTree p);int C 1 e ar(B iThrT r e e p)；BiTh r T ree p 1;i n t j,m;P r i ntf(“中序序列为:n ”)；fo r(p 1 =p-n e x t；p 1 !=p;pl=p lnext)p r i nt f(H%d”，p l-data);)p r i nt f(n);P r in tf(继续按1,退出按0

42、 n”)；s can f(%d，&j);if(j)(p i intf(输入要进行的项目:);s c a nf(%dswi t c h(m)c a se 1:q ianqu(p);break;c ase 2：houji(p);b r ea k；cas e 3:zuo h ai(p)；break；cas e 4:youh a i(p);b reak;c a se 5:ln s ert(p);b r e a k;c a se 6:D el e te(p);b reak;ca s e 7：InOrd e r(p)；brea k；c as e 8:Clea r(p);e x it(0)；)else e

43、x it(0);return 0;int Ins e rt(B i ThrTre e p)i n t q i a n q u(BiTh r T r ee p)；int houji(BiThrT r e e p)；int zuohai(BiThrTre e p)；i n t y ouh a i(BiT h rTr e e p)；i n t I nO r der(Bi T hrT re e p)；int Del e t e(BiThrTree p);int Clear(B i ThrTree p)；i n t a,b,ij,m；B iT h rTr e e plz p 2；p 2=(BiTh r

44、Tree)ma 1 loc(sizeof(Bi T hrNod e)；pri n t f(输入所要插入的节点：);scanf(%d,&a);p r i ntf(输入所要查找的节点：)；scanf(%d,&b);for(p l=p-next;p 1!=p;pl=pl-n e x t)if(pl-d ata=b)break;)i f(p 1=p)printf(该节点不存在！n);else p p intf(”*,插 入 为 j方 千*n”)print f(*2：入为右子*uprintf（选择操作：）;scanf(%d,&j);sw i t c h(j)ca s e 1:p2 data=a;p2-1

45、 c h il d=NULL;p2-rc h i I d=N ULL;p2-ne x t=pl;p2-pr i or=plp r ior;p 1 p rio r-nex t=p 2;p 1-p r io r=p2;pl-lchi 1 d=p 2;br e a k；)case 2:p 2-dat a=a；p 2-l c hil d=NU LL;p 2 rchild=NULL;p2-prio r=p 1；p 2 ne x t=p 1 n e xt;p 1 n ext-pr i o r=p2;pl-next=p 2；p l-r c h i 1 d=p2;b r e ak;d e f aul t:ex

46、it(0);)p r in t f (继续按1,退出按0 n“)；sea nf(u%d,&j);P r int f (n输入要进行的项目：”);s canf(H%d，&m);s w it c h(m)c a s e 1：qi a n qu(p)；bre a k；ca s e 2：ho u ji(p);break;case 3：zuo h ai(p);b r ea k;case 4:youhai(p)；b r e ak;cas e 5:ln s ert(p);break;case 6:Delete(p);b re a k;c ase 7:1 n 0 r d er(p);brea k；c a se

47、 8:C lear(p);e x it(O);els e e xit(0);e t u rn 0;i nt De 1 ete(B i Th r Tree p)i n t In0 r d e r(BiT h rTre e p)；int q ianqu(B i T h r T ree p);i n t houji(BiTh rTr e e p)；i n t zuo h ai(B iTh r Tree p);in t youha i(BiThrT r ee p);int Inse r t(B i Th r Tr e e p)；i nt Clea r(BiThrTr e e p);in t a,j,m

48、;BiThr T r ee p 1 ;Bi T h rTree p 2；p r i n t f(输入您要删除的节点：”)；sea n f (%d,&a)；for(p l=p-next;pl!=p;p 1=p 1-n e x t)if(p l-d a ta=a)b reak;if(P 1 =P)pri n tf(“该树中无此节点!”);elsei f(p 1=P 1prior-rchild)p 1-priornext=p 1 next；p l-n ex t prior=pl p ri o r;pl-p r i o r-rchil d 二N ULL；fr e e(p l)；i f(p l=p 1-

49、n ext-1 ch i ld)p l prior-n ex t=pl-n e x t;p l-n e x t-p r i o r=pl-pri o r;p 1 n e x t-Ichi Id=NULL;f ree(p 1);)prin t f (继续按1,退出按0 n“)；scant(”cT,&j)；printf(输入要进行的项目：);s canf(%d n,&m)；s witch(m)ca s e 1：q ianqu(p);b r eak;case 2:h ou j i(p);br e ak;c as e 3:zuohai(p);bre a k；case 4:y ouhai(p);break；c a s e 5：Inser t(p)；b re a k;case 6:Del e te(p);b r eak;case 7:lnOr d e r(p);br e a k；case 8：C 1 ear(p)；e x it(O)；)el s e e x it(O);ret u rn 0;int Clea r(Bi T h r T r ee p)B i T hr T r e e pl,p 2；f or(pl=p-n e x t;p2!=p;)p 2=pl-n e xt;fre e(p 1)；P 1 =p2;)f r ee(p);)