树和二叉树实验报告Word下载.docx

1、后序遍历左子树，后序遍历右子树，访问根结点4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。五、程序清单#includestdlib.h#define M 100typedef char Etype; /定义二叉树结点值的类型为字符型typedef struct BiTNode /树结点结构 Etype data; struct BiTNode *lch,*rch;BiTNode,*BiTree;BiTree

2、queM;int front=0,rear=0;/函数原型声明BiTNode *creat_bt1（）;BiTNode *creat_bt2（）;void preorder（BiTNode *p）;void inorder（BiTNode *p）;void postorder（BiTNode *p）;void enqueue（BiTree）;BiTree delqueue（ ）;void levorder（BiTree）;int treedepth（BiTree）;void prtbtree（BiTree,int）;void exchange（BiTree）;int leafcount（BiT

3、ree）;void paintleaf（BiTree）;BiTNode *t;int count=0;/主函数void main（） char ch; int k; do printf（nnn）;n=主菜单=nn 1.建立二叉树方法1nn 2.建立二叉树方法2nn 3.先序递归遍历二叉树nn 4.中序递归遍历二叉树nn 5.后序递归遍历二叉树nn 6.层次遍历二叉树nn 7.计算二叉树的高度nn 8.计算二叉树中叶结点个数nn 9.交换二叉树的左右子树nn 10.打印二叉树nn 0.结束程序运行n=n 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） scanf（%d,&k）;

4、switch（k） case 1:t=creat_bt1（ ）;break; /调用性质5建立二叉树算法 case 2:printf（n请输入二叉树各结点值:fflush（stdin）; t=creat_bt2（）; /调用递归建立二叉树算法 case 3:if（t） printf（先序遍历二叉树: preorder（t）;n else printf（二叉树为空! break; case 4:中序遍历二叉树: inorder（t）; case 5:后序遍历二叉树: postorder（t）; case 6:层次遍历二叉树： levorder（t）;二叉树为空！ case 7:二叉树的高度为：,

5、treedepth（t）; case 8:二叉树的叶子结点数为：%dn,leafcount（t）;二叉树的叶结点为：paintleaf（t）; case 9:交换二叉树的左右子树： exchange（t）; prtbtree（t,0）; case 10:逆时针旋转90度输出的二叉树： case 0:exit（0）; /switch while（k=1&kdata=e;lch=NULL;rch=NULL; vi=p; if（i=1） t=p; /序号为1的结点是根 else j=i/2; if（i%2=0）vj-lch=p; /序号为偶数，作为左孩子 else vj-rch=p; /序号为奇数，

6、作为右孩子 n请继续输入二叉树各结点的编号和对应的值：return（t）;/creat_bt1;/模仿先序递归遍历方法，建立二叉树BiTNode *creat_bt2（） BiTNode *t; Etype e;%c if（e=）t=NULL; /对于值，不分配新结点 else t=（BiTNode *）malloc（sizeof（BiTNode）; t-lch=creat_bt2（）; /左孩子获得新指针值 rch=creat_bt2（）; /右孩子获得新指针值 /creat_bt2/先序递归遍历二叉树void preorder（BiTNode *p）if（p）%3c,p-data）; pr

7、eorder（p-lch）;rch）; /preorder/中序递归遍历二叉树void inorder（BiTNode *p） inorder（p- /inorder/后序递归遍历二叉树void postorder（BiTNode *p） if（p） postorder（p- postorder（p- /postordervoid enqueue（BiTree T） if（front!=（rear+1）%M） rear=（rear+1）%M; querear=T;BiTree delqueue（ ） if（front=rear）return NULL; front=（front+1）%M; r

8、eturn（quefront）;void levorder（BiTree T） /层次遍历二叉树 BiTree p; if（T） enqueue（T）; while（front!=rear） p=delqueue（ ）;%3d if（p-lch!=NULL）enqueue（p-rch!int treedepth（BiTree bt） /计算二叉树的高度 int hl,hr,max; if（bt!=NULL） hl=treedepth（bt- hr=treedepth（bt- max=（hlhr）?hl:hr; return （max+1）; else return （0）;void prtbt

9、ree（BiTree bt,int level） /逆时针旋转90度输出二叉树树形int j;if（bt）prtbtree（bt-rch,level+1）;for（j=0;jprtbtree（bt-lch,level+1）;void exchange（BiTree bt） /交换二叉树左右子树BiTree p;p=bt-lch;bt-lch=bt-rch;exchange（bt-int leafcount（BiTree bt） /计算叶结点数if（bt!leafcount（bt-leafcount（bt-if（bt-lch=NULL）&（bt-rch=NULL） count+;return（c

10、ount）;void paintleaf（BiTree bt） /输出叶结点 if（bt! if（bt-lch=NULL&rch=NULL） paintleaf（bt- 图11.2所示二叉树的输入数据顺序应该是：abd#g#ce#h#f#。图11.2 二叉树示意图运行结果：=主菜单= 1.建立二叉树方法1 2.建立二叉树方法2 3.先序递归遍历二叉树 4.中序递归遍历二叉树 5.后序递归遍历二叉树 6.层次遍历二叉树 7.计算二叉树的高度 8.计算二叉树中叶结点个数 9.交换二叉树的左右子树 10.打印二叉树 0.结束程序运行= 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10）

11、1请输入二叉树各结点的编号和对应的值（如1，a）：1，a请继续输入二叉树各结点的编号和对应的值：2，b3，c4，d6，e7，f9，g13，h0，#=主菜单= 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 3先序遍历二叉树：a b d g c e h f 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 4中序遍历二叉树：d g b a e h c f 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 5后序遍历二叉树：g d b h e f c a 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 6 97 98 请输入您的选择（0,

12、1,2,3,4,5,6,7,8,9,10） 74 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 83 g h f 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 9 d g b a e h c f 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 10 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 2请输入二叉树各结点值：abd#g#ce#h#f# 请输入您的选择（0,1,2,3,4,5,6,7,8,9,10） 0请按任意键继续. . .6、调试心得及收获建立二叉树有两种方法：一种方法是利用二叉树的性质5来建立二叉树；建立后，通过先序、中序、后序遍历，对二叉树有了进一步的理解与掌握。对二叉树中各种计算也更了解了！7、其他所想到的一个二叉树，有许多部分构成，每一个部分都需要精心编写，才能对其进行操作，不至于出错。