2023年数据结构二叉树操作实验报告.docx

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

1、数据结构一实验报告指导教师 x X实验时间：指23年1 1月L日学院计算机学院专业 信息安全班级 XXXXXX 学号 XXXXX 姓名 X X 实验室S331实验题目:二叉树操作实验规定：采用二叉树链表作为存储结构，完毕二叉树的建立,先序、中序和后序以及按层次 遍历的操作，求所有叶子及结点总数的操作。示例程序：# i n clud e s t d i o. hi n clud e string. h# d e fine Max 2 0结点的最大个数ty p e def str u ct n o d e cha r data;str u ct node *lchild, c hild; BinT

2、Node；自定义二叉树的结点类型type d e f B i nTNode *BinTree; 定义二叉树的指针i nt NodeNum, leaf;NodeNum为结点数，lea f 为叶子数= = =基于先序遍历算法仓ij建二叉树二= = =/ /二二=二=规定输入先序序列，其中加入虚结点以示空指针的位置= = =Bi n T ree Cr e a t B i nTree (voi d )if(p-l c hild! =NULL)rear=( r ear+1) %No d eNum;cqrear=p-l c hild; / /左子树入队 if(p r c h i 1 d! =NULL)。

3、r ear=(r ear +1)%N o deNum；oc q r e a r=pr c hil d ;/ / 右子树入队)I/=主 函数=vo i d main()(BinTree root;in t i , d epth;printf ( n)；p rintf(nCr eat B i n_Tre e ； I n put p r e order:)；输入完全二叉树的先序序列,用#代表虚结点，如ABD#CE#F#r o ot=C r e atBinT r ee ();创建二叉树，返回根结点do 从菜单中选择遍历方式，输入序号。ooprin t f(Mt * * * s el e ct * *

4、* *n )；p r intf(n t 1： P r eord e r Tra v ersal n n)；o p ri n t f(nt2: lorder Tra v e rs a 1 nH);。p rin t f(H t 3 ： Pos t or d e r tra ver s a 1 n”);printf(nt4: P o stTre e De p th, Node number, Leaf n umbernn);oprintf Ct5:Leve 1 Depth n ”); / /按层次遍历之前，先选择4 ,求出该树的结点数。 oprintf(ntO： Exi t nH)；6prin t

5、f (、* n )scanfC%dn,&i) ;/输入菜单序号(05)s wi t ch (i) 。c ase 1: p rintf(nP r int Bin_tree P r e o r der： )；r eorder(root) ；/ /先序遍历3break;case 2: printf (nPri n t Bi n _ T r e e Ino r de r : n);Ino r de r ( r oot);中序遍历break;。 ca s e 3 ： p rint f ( n P ri nt B i n_T ree Pos tor der:);。 Posto r d e r (root)

6、; 后序遍历 ?bre a k;c a se 4: dep t h=TreeDepth(r o ot)；/求树的深度及叶子数。 printf( n Bin T ree Dept h = %d BinT ree No d e numb e r=% d ”，d epth,NodeN u m);p rintf(n Bi n T r ee Leaf num b er=%cT,lea f )；o break;c as e 5: p r i n tf(nL e v e P rint Bi n _T r ee: )；Ie v elorder(root);/ /按层次遍历。 break;a d efau 1

7、t : exit(l );p r intf(nn n )； while ( i !=0);程序结果:D:C语言编的程序DebugCppl.exe”Creat Bin_Tree ； Input preorder ： ABDttttttCEItttFtttt xxxxxxxxxx select xxxxxxxxxxxx 1： Preorder Traversal 2： Iorder Traversal 3： Postorder traversal4： PostTreeDepth,Node number .Leaf number 5： Leuel Depth0： Exit1Print Bin_tre

8、e Preorder： ABDCEFx x x x x x x x x x select x x x x x x x x wx1： Preorder Traversal2： Iorder Traversal3： Postorder trauersal4： PostTreeDepthj.Node number,Leaf number5： Leuel Depth0： Exitrint Bin_Tree Inorder： DBAECF* select x射射射射射射射射2Print2Print3c语言编的程序DebugCppl.exe”Bin_Tree Inorder： DBAECF * selec

9、t *1:2：4：0：Preorder Trauersal Iorder Trauersal Postorder trauersal PostTreeDepth,Node number .Leaf nunber Leuel Depth Exit3 PrintBin_Tree Postorder： DBEFCA xxxxxxxxxx select xxxxxxxxxxxx1：2：3：4：0：Preorder Trauersal Iorder Trauersal Postorder trauersal PostTreeDepthj-Node number .Leaf number Leuel De

10、pth ExitXXXXXXXMXXXX-XXXXXXXXXXXXXMMX4BinTree Depth=3 BinTree Node nunber=6 BinTree Leaf number=3 MMXMXXXMMM SClect MXMXXXXMMXMM 1： Preorder Trauersal,D:CiBBK?DebugCppl.exeHBinTree Depth=3 BinTree Node number=6 BinTree Leaf nunber=3 xxxxxxxxxx select xxxxxxxxxxxx1：2：3：4：0：Preorder Trauersal Iorder T

11、raversal Postorder traversal PostTreeDepth,Node numberLeaf number Leuel Depth ExitMXMXXMXXMXXMXMMXMXXMMMXXMXXMXXX5LeuePrint Bin_Tree： ABCDEF * select *1：2：3：4：0：Preorder Traversal Iorder Traversal Postorder trauersalPost Tree Depth, Node number .Leaf number Leuel Depth ExitM X M M X M X-X X M M M X

12、XX M-XX X M X M X X M6Press any key to cont inue二叉树及后序遍历（虚线途径）心得体会:通过本次实验，我纯熟了二叉树先序、中序和后序三种遍历，不仅是程序的编写，尚有二叉树的绘制。Bin Tree T;char c h;if ( c h = g e tc h a r ()=#)r e t u rn (NULL)；读入#，返回空指针els e T二(B i nTN ode *)malloc(si z eof (B inTNode)； 生成结点 T-data=ch;qT 1 ch i ld = Cre a tB i nTr e e () ；/ / 构造左

13、子树oT-r c hi 1 d= C reatBinTree ();构造右子树re t u r n (T);)/= = = = NLR 先序遍历= =vo i d P reorder (Bin Tree T)(i f8 P rintf (c，T data); 访问结点oP r eorder (T-lc h i 1 d );先序遍历左子树Pre o r de r ( T- r child) ;/先序遍历右子树)LNR 中序遍历=/= = =LRN 后序遍历= = =采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(Bi nTree T)i n t h 1, hr,

14、 m a x；if(T) hl=Tre e Dep t h(T- 1 ch i 1 d) ;“/求左深度。 hr=Tr e eD e pth ( T-rchild) ;/ /求右深度max=hlh r ? hl :hr;取左右深度的最大值Nod e N u m=No d eN u 1 ；求结点数i f (h l= = 0&hr=0) le a f=l e a f + 1 ; / /若左右深度为 0,即为叶子。r e t u r n(max + l);)els e r eturn(0)；)=运用先进先出(FIFO)队列，按层次遍历二叉树= = =void Lev e lor d er (BinT

15、 r ee T)(i n t front=0, rear=l;BinTNode *cqMax , *p;/定义结点的指针数组c qcq L 1 =T;/ / 根入队while( f r ont!=rear)g f ron t = (fr ont+l)%NodeN um ;。p=cqf r ont；出队。printf(”c，p-data) ;/出队，输出结点的值si f (p-lch i 1 d !=NULL) 3 r e ar= (rea r +1) %No d eNum;/左子树入队/左子树入队cqr e a r =p-l c h il d ；。i f(p- r chi Id! =NULL)

16、 re a r 二(re a r +1) %No d eNum;=p rchi 1 d;右子树入队void main()BinT r ee r oot；in t i, d epth；pr i n t f (n)；p rint f (Cr e at Bin Tre e ; Inp u t pr e o rd e r: )； 输入完全二叉树的先 序序列，/用#代表虚结点，如ABD#CE#F#r o ot=Cr e atBinTr e e();创建二叉树，返回根结点do / /从菜单中选择遍历方式,输入序号。o printf (t* * * * sei e ct * * * * * * * n n

17、);p ri n tf (tl: P r eo r d er Travers a 1 n );mp r i nIo r d e r Tr a ve r s a 1 n)；oprintf ( ” t3: Po s torder t rave r s aln)；叩 r intf ( n t4: P os t TreeDe P t h , Node n umber, Leaf numbern)；printf Ct5: Level Depthn); 按层次遍历之前,先选择4,求出该树的结点数。叩 r int f ( n t 0 : Exitn);print f (t * * * * * * * * *

18、 * * * * * * n );scanfC%d n , & i ) ;/ / 输入菜单序号(0-5)swi t ch ( i ) c a s e 1 : pri n tf (Pri n t B i n_tre e P r eo r d e r: z，);o P r eord e r (roo t ) ;/ / 先序遍历obre ak；3 c ase 2: pr i n t f (Print Bin Tree Inorder： )； g Inorder (ro o t); 中序遍历obreak;。 case 3 ： p rin t f (Print B i n_Tree Pos torde

19、r： )；g Post o r der (roo t ); 后序遍历 b r eak;ca s e 4 : depthsTreeDep t h(roo t );求树的深度及叶子数sprint f (B i nT r e e D epth=%d BinTre e Nod e number=%d，/, de p t h , N o d eN u m);。 6printf ( BinTree Leaf n u m b er-% d z，, leaf)； g b re a k;wca s e 5: print f (L e v eP r int B i n_Tr e e： )；L e velo r d

20、er ( r oot) ;/ / 按层次遍历g b r ea k ;def a u 1 t : e x i t(l)；gpr i n tf ( ” n)； w h ile (i!= 0);实验内容及环节：1、分析、理解程序。2、添加中序和后序遍历算法.3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针), 如ABD#CE#F#,建立二叉树，求出先序、中序和后序以及按层次遍历序列, 求所有叶子及结点总数。4、画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。给出实验结果。5、给出实验结果。改正后的完整程序：#includeHstdio.hn#in c lu

21、d en s tr i n g.hn#includei 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 ；JBinTNode ；/自定义二叉树的结点类型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 为结点数，leaf 为叶子数/=基于先序遍历算法创建二叉树= = =规定输入先序序列，其中加入虚结点 #”

22、以示空指针的位置= = = = = =B inT r ee C r e a tB i nT r e e (v o i d)BinT r ee T;c h ar ch;if( (c h =getch a r()=# f )r e tu r n(NU LL); 读入#，返回空指针 elseoT=(Bin T Node * )m a lloc(s i zeof( B in T Nod e ) ;/ / 生成结点。 T-data= c h;T- 1 ch i 1 d=C r eatBi n Tree ();构造左子树Trchild=Cr eat B inTree ();构造右子树6return(T);

23、) ) =NLR 先序遍历= = = = = = = void Pr e or d er( B inT r ee T) if(T)叩 r i n tf(n%c n ,T- d ata); 访问结点oPreorder (T-lc h i Id); 先序遍历左子树3 Pr e o r d e r(T-rchi 1 d );先序遍历右子树)/ / = = =LNR 中序遍历= void I norder(Bin T ree T)(i f(T)g I norder ( T lch i Id);先序遍历左子树pr i n t f( n %c ”，T- d ata);访问结点访问结点I norder(T

24、rc h i 1 d );先序遍历右子树)/*void Ino rde r (B inTr e e T )。whi 1 e( p I |! St a ck E m p t y (Bin Tree T) oif(T) (Push (BinTr e e T,T); T =T-1 c hild； /根指针进栈，遍历左子树els e 根指针退栈，访问根节点，遍历右子树P o p(Bi n Tre e T, t)；“i f (!V i sit(T- d ata)r e turn ER ROR;。T =T-rc h i 1 d; /els e / / whilere t urn OK;)*/=L RN 后

25、序遍历= = = = = = =v oi d Po s to r der ( B i nT r e eT)(if(T) e P o s tor d e r(T lchil d )；先序遍历左子树。 P ostorder(T r chi 1 d);先序遍历右子树pr i ntf(n%c n ,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

26、 1 d )；/ / 求右深度ma x = h 1 hr? hl: h r;/取左右深度的最大值aNo d eNum = Nod eNum+l ；求结点数if( h l=O&hr= 0 ) lea f =leaf+l; /若左右深度为 0,即为叶子。r e turn(max+l);else return ( 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 ear)ofr o n t =( f r o n t+l)%NodeN u m;p=c q f r ont;出队pri n tf( n % c H,p-data);出队，输出结点的值