《2023年数据结构二叉树操作实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构二叉树操作实验报告.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数 据 结 构 实验报告指导教师 x X 实验时间：指2 3 年J_L月 L 日学院 计算机学院 专业 信息安全班级 XXXXXX 学号 X X X X X 姓名 X X 实验室S331实验题目:二叉树操作实验规定：采用二叉树链表作为存储结构，完毕二叉树的建立,先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。示例程序：#i n cl ud e s t d i o.h#i n cl ud e string.h#d e fine M ax 2 0 结点的最大个数ty p e def str u ct no d echa r data;s t r u c t n o d e *1
2、chil d,*r c hil d;B inTN ode；自定义二叉树的结点类型ty pe d e f B i nTN ode*B inTr e e;定义二叉树的指针i nt N odeN um,l eaf;N odeN um为结点数，l ea f 为叶子数=二=基于先序遍历算法创建二叉树=/=规定输入先序序列，其 中 加 入 虚 结 点 以 不 空 指 针 的 位 置=B i n Tree C r e a t B i nTree(voi d)B inTr e e T;char c h;if(c h=g e tc h a r()=#)r e t u r n (N UL L)；读入礼返回空指针e
3、l s e(T=(B i nTN o d e *)m al l oc(si z eof(B inTN ode)；生成结点 T-data=ch;T 1 ch i l d=C re a tB i nTr e e()；/构造左子树oT-rchi 1 d=C reatB inTree();构造右子树re t u r n(T);)=二 二=二 二=N L R 先序遍历=二=vo i d P reorder(B inTr e e T)Ii f(T)g p rintf T data);访问结点oP r eorder(T-l c h i 1 d);先序遍历左子树P re o r de r(T-r chil d
4、);/先序遍历右子树)/=二=二 二 二 二 二L N R 中序遍历二=/=L R N 后序遍历=/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=i n t T reeD epth(B i n Tree T)i n t h 1,hr,ma x；if(T)hl=Tre e D ep t h(T-1 ch i 1 d);“/求左深度。hr=Tr e eD e pth(T-rchil d);/求右深度m ax=hl h r?hl:hr;取左右深度的最大值N o d e N u m=N o d eN u m+1 ；求结点数i f(h l=0&,h r=0)l e a f=l e a f+1
5、;/若左右深度为 0,即为叶子。r e t u r n(m ax +l);)el s e r eturn(0)；)=运 用 先 进 先 出(F I F O)队列，按层次遍历二叉树=v o i d L ev e l or d er(B inT r ee T)Ii n t front=0,r e a r=l;B inTN ode*c q M a x ,*p;定义结点的指针数组c qcq 1 =T;/根入队whil e(f r o nt!=rear)(8 f ron t=(fr o n t+1)%N o d e N u m;。p=cqf r ont；出队a p r i n t f(%c，p-data
6、);/出队，输出结点的值g i f(p-l ch i 1 d!=N UL L)。r e a r=(rea r+1)%N o d eN um;00cqr e a r=p-l c h i 1 d；/左子树入队oi f(p-r chi 1 d!=N U L L)。re a r=(re a r+1)%N o d eN um;o c q re a r=p-rchi 1 d;右子树入队)void m ain()B inT r ee r oot；in t i,d epth；pr i n t f(n)；p rint f(C r e at B i n Tre e;I np u t pr e o rd e r:，
7、z)；输入完全二叉树的先序序列，/用#代表虚结点，如A B D#C E#F#r o ot=C r e atB inTr e e();创建二叉树，返回根结点do /从菜单中选择遍历方式，输入序号。o printf(t*sel ect*);p ri n tf(tl:P r eo r d er Travers a 1 n )；8 P r i n t f(t2:I o r d e r Tr a ve r s a 1 n)；oprintf(t3:P o s torder t rave r s al n)；叩 r intf(t4:P os t TreeD e p t h,N ode n um b er,L
8、 eaf num b ern)；printf C t5:L evel D epthnz，);/按层次遍历之前,先选择4,求出该树的结点数。叩 r int f(H t 0 :E x itn)；print f(t*n )；scanf(%d ，&i );/输入菜单序号(0-5)swi t ch(i )必 c a s e 1 :pri n tf(P ri n t B i n_tre e P r eo r d e r:，z)；。P r eord e r(roo t);/先序遍历o b r e ak；ocase 2:pr i n t f(P rint B i nTree I norder：)；g I no
9、rder(ro o t);中序遍历b reak;。c a s e 3 ：p rin t f(P rint B i n_Tree P os t o r d e r：)；g P ost o r der(roo t);后序遍历b r eak;ca s e 4 :depth=TreeD ep t h(roo t);求树的深度及叶子数opri nt f(B inTr e e D epth=%d B inTre e N od e num b er=%d，z,de p t h,No d eN u m);o opri nt f(B i nTree L eaf n u m b er=%d，z,l eaf)；oo
10、b re a k;o e*c a s e 5:print f(L e v eP r int B i n_Tr e e：)；L e vel o r der(r oot);/按层次遍历g b r ea k ;def a u 1 t :e x i t(l)；)gpr i n tf(n)；wh il e(i!=0 );)实验内容及环节:1、分析、理解程序。2、添加中序和后序遍历算法.3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针),如 ABD#CE#F#,建立二叉树，求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。4、画出所设计的二义树，以后序遍历算法为例
11、，画出执行踪迹示意图。给出实验结果。5、给出实验结果。改正后的完整程序：#includestdio.hn#in c lu d e s tr i ng.h#include#i n c lu d e#d e f ine Max 20/结点的最大个数typed e f stru c t no d ec har data；str u c t n o de*Ichii d,*r c hi 1 d；BinTN ode；/自定义二叉树的结点类型t yp e def B i n TNo d e*BinTre e;/定义二叉树的指针i nt Nod e N u m,lea f；/N o de Num 为结点数，
12、leaf 为叶子数/=基于先序 遍历算 法创建二叉树=规定输入先序序列，其中加入虚结点#以示空指针的位置=B inT r ee C r e a tB i nT r e e(v o id)BinT r ee T;c h ar ch;if(c h=getch a ()=#)r e tu r n(NU LL);读入#，返回空指针elseoT=(Bin T Node)m a lloc(s i zeof(B in T N od e);/生成结点。T-data=c h;T-1 ch i 1 d=C r eatBi n Tree();/构造左子树ooTrchild=Cr e a t B inTree();构
13、造右子树oreturn(T);)/=NLR 先 序 遍 历=void Pr e or d er(B inT r eeT)(if(T)op r in tf(n%c n,T-d ata);访问结点Preorder(T-lch i Id);先序遍历左子树。Pr e o r d e r(T-rchi 1 d);先序遍历右子树)/=LNR 中序遍历=void I norder(BinTree T)(i f(T)。I norder(T lch i I d);先序遍历左子树pr i n t f(*%cn,T-d a ta);访问结点I norder(Trc h i 1 d);先序遍历右子树)/*void I
14、n o rde r(B inTr e e T)。whi 1 e(p I|!St a ck E m p t y(Bin T re e T)qf(T)Push(BinTr e e T,T);T=T-1 c hild；/根指针进栈，遍历左子树oels e /根指针退栈，访问根节点，遍历右子树P o p(Bi nTre e T,t)；“i f(!V i sit(T-d ata)r e turn ERROR;。T=T-rc h ild;/e ls e)/whilere t urn OK;)*/=L RN 后序 历=v oi d Po s to r der(B i n T r e eT)(if(T)。P
15、o s tor d e r(T lchil d)；先序遍历左子树。P ostorder(T r chi 1 d);先序遍历右子树pr i ntf(u%c ,T-data);访问结点=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=:int T reeDepth(B inTr e e T)(i n t hl,h r,max；if(T)hl=TreeDe p th(T-lc h ild);求左深度h r=T reeD e pth(T-r ch i 1 d)；/求右深度ma x=h 1 hr?hl:h r;/取左右深度的最大值N od eNum=Nod eNum+1；求结点数if(h l=O&
16、hr=0)lea f=leaf+l;/若左右深度为 0,即为叶子。r e tum(max+l);)else r e tu r n (0);)=二=运用 先进先出(FIFO)队列，按层次遍历二叉树=void L eve 1 o rd e r(B i nT r ee T)(i n t fr o n t=0,rear=1 ；BinTNode*cqMax,*p;/定义结点的指针数组c qcql=T;/根入队while(f r ont!=r e a r)(fr o n t=(f r on t+l)%NodeN u m;p=c q f r ont;出队pri n tf(%c n,p-data);出队，输出
17、结点的值if(p-l c hild!=NULL)rear=(r ear+1)%No d eNum;。cqrear=p-l c hild;/左子树入队0 ooif(p-r c h i Id!=NULL)。r ear=(r e a r +1)%N o deNum；。c q r e a r=p r c hil d;/右子树入队)/=函 数=vo i d main()(BinTree root;in t i,d epth;printf(n)；p rintf(r e a t B i n_Tre e；I n put p r e orde r:)；输入完全二叉树的先序序列,用#代表虚结点，如 A B D#C
18、 E#F#r o ot=C r e atBinT r ee();创建二叉树，返回根结点do 从菜单中选择遍历方式，输入序号。prin t f(ut*select*);p r intf(t 1 ：P r eord e r Tra v ersal n”)；e p ri n t f(nt2:lorderTra v e rs a l n );p rin t f(M t 3：Pos t or d e r tr a ver s a 1 nM);ooprintf(nt4:P o stTre e De p th,Node number,L e a f n umbern);printf(nt5:Le ve 1
19、Depthn );/按层次遍历之前,先选择4,求出该树的结点数。叩rimf(tO：Exi t n)；gprin t f(%*n )scanf(%dn,&i);/输入菜单序号(05)s wi t c h(i)g c ase 1:p rintf(P r int Bin_tree P r e o r der：)；P r eorder(root)；/先序遍历ob r e a k;c a s e 2:printf(Pri n t Bi n _ T r e e Ino r de r:)；。Ino r de r(r oot);中序遍历wbreak;。ca s e 3：p rint f(”P rint B i
20、 n_T ree Pos t o r der:)；6Posto r d e r(root);后序遍历bre a k;c a se 4:dep t h=TreeDepth(r o ot)；求树的深度及叶子数。printf(n Bin T ree Dept h=%d BinT r e e No d e numb e r=%d ,depth,NodeN u m);a p rintf(M Bi n T r ee Leaf num b er=%d,lea f)；。b re a k;c as e 5:p r i n tf(nL e v e P rint Bi n _T r ee:)；Le v elorde
21、r(root);/按层次遍历。break;。d efau 1 t:exit(1);。p r intf(Hn )；while(i!=0);)程序结果:2：Iorder T raversal3：Postorder tra u ersa l4：Post Tree Depth,Node number,.Leaf number5：Leuel Depth0：E xit3P rint Bin_Tree P ostorder：DBEFCAxxxxxxxMxx s e le c t xxxxxxxxxxx/1：Preorder T raversal2：Iorder T rauersal3：Postorder tra u ersa l4：PostTreeDepth,Node number,Leaf number5：Leuel Depth0：E xitBinTree Depth=3 BinTree Node nunber=6 BinTree Leaf nunber=3xxxxxxxxxx se le c t xxxxxxxxxxxx1：Preorder T raversal二叉树及后序遍历（虚线途径）心得体会:通过本次实验，我纯熟了二叉树先序、中序和后序三种遍历，不仅是程序的编写，尚有二叉树的绘制。