2023年数据结构实验报告树与二叉树.docx
福建农林大学计算机与信息学院实验报告树与二叉树一、实验目的和规定1）进一步掌握指针变量、动态变量的含义。2）掌握二叉树的结构特性及各种存储结构的特点及合用范围。3）掌握用指针类型描述、访问和解决二叉树的运算。4）熟悉各种存储结构的特性及如何应用树结构解决具体问题。二、实验内容和原理实验内容：编写程序实现互换二叉树中所有结点的左右子树的算法。实验原理：【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将 二叉树中所有结点的左右子树互换，显示其结果。【基本规定】从键盘接受输入点（按层次遍历顺序），以“#"号结束, 以二叉链表作为存储结构，将其二叉树中所有结点的左右子树互换， 并将结果输出。【实现】互换二叉树中所有结点的左右子树的具体环节如下：将根结点进指针栈seqstack;当指针栈不空时，从栈顶取结点，假如此结点的左右孩子不为 空,则把其左右孩子互换,然后再分别将其左右孩子进栈；反复执行环节,直至指针栈为空时止。三、实验环境w i ndo wsXP 系统visua 1 C+6.0四、算法描述及实验环节#include ” s td i o. h "#inclu d e s td 1 ib. hMe f ine MAXSIZE 10 0t y pe d e f char e 1 e mt y p e;typedef s t r u c t btn ode e lem t ype data；struct bt n ode *1 c hi 1 d, *r c hild；)b i t no d e , *b i tr e e;typ e def st r uct n o ddbi tree a ddr；i n t pare n t;sequre；bitre e i ns_node (bitr e e s, bi t ree t)； void pr i n t _ t ree ( b itre e t )；b i t r ee c re a t_ordb t ();s equr e s e q MAXSI Z E;v oid swap( b itree t r e e);i n t n=0； void m a in()(b i tr e e tr e e; tree=c r e at_ o r dbt ();swap (tr e e);printf (输出互换后的二叉树n)；pr i nt_tre e (tree);)bitr e e creat_ o rdb t ()bit r ee t, s；elemt y p e x;t=NULL；printf ( "请按层次输入结点1的值(以#号结束,0号为空的结点)：)； scanf (% c ”, & x );get c har ();w h ile (x!='#') n+;if(x ! =，O') s = (bi tree)malloc ( s izeo f (bit nod e );s->data=x;s->lch i Id=NULL；s ->rch ild=NULL；se q n ,ad d r = s；t= i ns_node(s, t);e Iseseq n . addr=NULL;print f (请输入结点d的值(以#号结束,0号为空的结点)：,n+1);x =g e tc h ar ();getch a r();return t;b i tree i n s_node (bitr e e s, bitree t)int kk;if (n=l)t=s；elsekk=n / 2 ;i f(n%2=0)s eqkk. addr->lc h ild= s ;elseseq k k . ad dr->rc h i ld=s；)ret u rn t;)voi d pri n t_tr e e(b itree t)int i , j , k, nn, sta r t, head, r ea r ;sequ r e seqq MAXS I ZE;b i tr e e p;i f (t=NUL L )retu r n ;he a d= 0 ; n n = r e ar=0;s e qqr e ar. addr=t;f o r(;he a d< = rear&&nn<M AX SIZE;head+) p=se q q h e ad . ad d r;if(p->l ch i 1 d = NULL)s e q q + +rea r . add r =p->lchil d ;i f (p->lchil d ! =NULL)s eqq + +rear. a d dr=p-> r ch i Id;)f or (he a d=0, j = 0 , k= 1 ; h e a d< = rear；) P rin t f ( n 第%d 层数据:",j);for(i=0, s t art=head; h ea d <st a r t+k； head+) pri n t f (z，%c ”, se q q head. a ddr >data)； if ( s eqq he a d. a d dr->l c h i ld=NULL) i = i-l;if ( s eqqhe a d. addr >rch i ld = = NULL) i=i-l;)k=k*2+i; j+;)v oid swa p (bit r e e root)in t to p ;b i tree t emp, s tackMAXS I ZE ;if (root!=NULL)(t op= 1 ;s t a c k to p =root;do root = s tack t op; to p = t op- 1;if(roo t ->1 child! =NULL) | I (ro o t->rchild!=NULL) (temp= r oot->lchild;r oot->lc h ild =r o o t->rchiId;r o o t >rchil d =t e m p ;)i f (root->lchild!=NULL)top+；stack top =roo t ->lc h i 1 d；)i f ( root-> r ch i 1 d!=NULL)top+；sta c k t o p =root-> r child;)w h i1 e (top!=0);)五、调试过程Configuration: 1 - Win32 Debug Conpiling1 .cppLinking1 .exe - 0 error(s), 0 vjarning(s)六、实验结果。号为空的结点：。号为至的组电: 。号为空的结点：。号为空的结点：。号为空的结点：。号力至的绫电):。号为空的结点:。号为空的结点九。号为空的结点:。号为空的结点:。号为空的结点:第0层数据：2 Press any key to continue以晦练1口 'C:UsersAdministratorDesktopDebugl.exe".的的汨1结结3结5结3结结,结>:结>>:结>:曩 八>:入入>:入>:入>S入入占小人京八入点入小八人4父售Z 2占与(24点43鼎2焦加34鼎32皿34束 结2点后<权 值叉 的二 0向 2白值值 的的2 3 4 4束 结 号5 结结 一二二一工01音青的, »的清的情的清前请输入结点3的值以*号结束，。号为空的 善输入结点6的值以力号结束，。号为空的 请输入结点8的值(以。号结束，。号为空的 请输入结点1。的值以*号结束，。号为空白345请输入结点13的值以林号结束，。号为空 请输入结点15的值以。号结束，。号为空 请输入结点17的值以”号结束，。号为空 请输入结点19的值以州号结束，。号为空 U七、总结1) 进一步掌握指针变量、动态变量的含义。2) 掌握二叉树的结构特性及各种存储结构的特点及合用范围。3) 掌握用指针类型描述、访问和解决二叉树的运算。4) 熟悉各种存储结构的特性及如何应用树结构解决具体问题。
