《树和二叉树实验报告》由会员分享，可在线阅读，更多相关《树和二叉树实验报告（15页珍藏版）》请在金锄头文库上搜索。
1、树和二叉树一、实验目的1. 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2. 掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1. 认真阅读和掌握本实验的程序。2. 上机运行本程序。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结果。三、实验内容1. 输入字符序列，建立二叉链表。2. 按先序、中序和后序遍历二叉树（递归算法）。3. 按某种形式输出整棵二叉树。4. 求二叉树的高度。5. 求二叉树的叶节点个数。6. 交换二叉树的左右子树。7. 借助队列实现二叉树的层次遍历。&在主函数中设计一个简单的
2、菜单，分别调试上述算法。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立 二叉树有各种不同的方法。一种方法是利用二叉树的性质5來建立二叉树， 输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号， 数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与 先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的 某孩子为空时以字符“#”來充当，也要输入。若当前数据不为“#”，则申 请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。四、解题思路1、先序遍历：访问根结点，先序遍历左子树，先序遍历右子树2、中序遍历：中序遍历左子树，访
3、问根结点，中序遍历右子树3、后序遍历：后序遍历左子树，后序遍历右子树，访问根结点4、层次遍历算法：采用一个队列q,先将二叉树根结点入队列，然后退队列， 输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右 子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达 到按层次遍历二叉树的目的。五、程序清单# iiiclude# iiiclude#define M 100tvpedef char Etyp 亡； tvpedef stmct BiTNode定义二叉树结点值的类型为字符型树结点结构Etype data;stmct BiTNode *lch,*rch;BiT
4、Node,*BiTree;BiTree queNIJ;iiit fiont=0,reai=0;函数原型声明BiTNode *cieat_btlQ;BiTNode *cieat_bt2();void preordei (BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void enqueue(BiTree);BiTree delqueue();void levorder(BiTree);iiit treedepth(BiTree);void pitbtiee(BiTree,int);void exchange(B l
5、Tree);iiit leafcount(BiTree);void paintleaf(BiTree);BiTNode *t;iiit count=0;主函数void main()chai- ch;iiit k;dopnntf(” n= 主菜单=“)； pnntf(” nn1.建立二叉树方法1”)；pnntf(”nn2.建立二叉树方法2”)；3. 先序递归遍历二叉树”)；printf(” nn4.中序递归遍历二叉树”)；5. 后序递归遍历二叉树”)；printf(” nn6.层次遍历二叉树”)；7. 计算二叉树的高度”)；pnntf(” nn8.计算二叉树中叶结点个数”)；pnntf(” nn
6、9.交换二叉树的左右子树”)；pnntf(” nn10.打印二叉树”)；pnntf(” nn0.结束程序运行”)；pimtf(,ii=); prmtfCi 请输入您的选择(0丄234,5,6亿8910门; scanff%dt&k);switch(k)case 1 :t=creat_btl();break;调用性质5建立二叉树算法case 2:printf(n 请输入二叉树各结点值:”);fflush(stdin);t=creat_bt2();break;调用递归建立二叉树算法case 3:if(t)pnntf(先序遍历二叉树:)；preoider(t);pnntf(”nj;else pnntf
7、f 二叉树为空!n”)；break;case 4:if(t)printfC*中序遍历二叉树:)；inorder(t);pnntf(”nj;else pnntff 二叉树为空!n”)；break;case 5:if(t)printf(”后序遍历二叉树:)；postordei(t);pnntf(”nj;else pnntff 二叉树为空!n”)；break;case 6:if(t)printf(层次遍历二叉树：”)；levoider(t);pnntffiT);else prmtfC1 二叉树为空！ 1T);break;case 7:if(t)printf(二叉树的高度为:%d,treedepth(
8、t);else prmtfC1 二叉树为空！ 1T);break;case 8:if(t)printf(二叉树的叶子结点数为：%dii,leafcount(t);printff 二叉树的叶结点为:”);pamtleaf(t);else pimtfC1匸叉树为空！ E);break;case 9:if(t)pnntfC*交换二叉树的左右子树：n”)；exchange(t);prtbtiee(t,O);else pimtfC1匸叉树为空！ E);break;case 10:if(t)pnntf(”逆时针旋转90度输出的二叉树：5”)； pilbtree(t,O);pnntf(”n”)；else p
9、nntf(二叉树为空！break:case 0:exit(0); /switchwlule(k= 1 &kdata=e;p-lch=NULL;p-rch=NULL;V1=P；唤=1)t=p;/序号为1的结点是根else尸2;if(i%2=0) vj -lch=p; else vj-rch=p;序号为偶数，作为左孩子序号为奇数，作为右孩子请继续输入二叉树各结点的编号和对应的值：”); scanf(H%d,%c,&i.&e);return(t);/creat_btl;模仿先序递归遍历方法，建立二叉树BiTNode *cieat_bt2QBiTNode *t;Etvpe e;scanff%c”,&亡
10、)；if(e却)t=NULL;/对于#值，不分配新结点elset=(BiTNode *)nialloc(sizeof(BiTNode);左孩子获得新指针值 右孩子获得新指针值t-data=e;t-lch=creat_bt2 Q;t-rch=creat_bt2Q;return(t); /creat_bt2先序递归遍历二叉树void preordei (BiTNode *p)】f(p)piintf(”3c、pdata);preoider(p-lch);preoider(p-ich); /preorder/中序递归遍历二叉树void inorder(BiTNode *p)】f(p)inordei(p
11、-lch);piiiitf(M%3c,p-data); inordei(p-rch); /morder/后序递归遍历二叉树void postoider(BiTNode *p)if(p) postordei(p-lch);postorder(p-rch);pnntff%3c”,pdas); /postorder void enqueue(BiTree T)=(reai+1 )%M)rear=(reai+1 )%M;querear=T;BiTree delqueue()if(front=rear)ietuin NULL; fiont=(fiont+1 )%M; retuin(quefiont);v
12、oid levorder(BiTiee T)BiTree p;】f(T)enqueue(T);while(fiont! =reai) p=delqueue(); piintf(”3d”,pdata); if(p-lch?=NULL)enqueue(p-lch); if(p-ich! =NULL)enqueue(p-rch); iiit treedepth(BiTree bt)iiit lilju;max;if(bt!=NULL) hl=treedepth(bt-lch); lu-treedeptli(bt-rch); max=(lillu)?hl:lir; return (inax+1);el
13、se return (0);层次遍历二叉树计算二叉树的高度void pitbtiee(BiTree bt.iiit level)mtj；】f(bt)prtbtree(bt-rchJevel+1);逆时针旋转90度输出二叉树树形Br(J=0；jv=6*level;j+)pnntfC ”)；printf(%cn,btAdata);pitbtree(bt-lch,level+1);void exchange(BiTree bt) 交换二叉树左右子树BiTiee p;if(bt)p=bt-lch;bt-lch=bt-rch;bt-rch=p; exchange(bt-lch);exchaiige(bt-rch);iiit leafcount(BiTree bt) /计算叶结点数
