1、数学与信息技术学院20162017(下)学年计科专业2015级数据结构实验报告5学号：2015201018姓名：汪继超实验名称树的操作实现与应用完成时间一.实验目的和要求：1 .掌握树特别是二叉树的根本概念、定义和性质。2 .掌握二叉树的根本结构、内部逻辑和三种遍历算法的根本思想，悉二叉树的存储结构和指针链接的变化。3 .通过对二叉树的建立和三种遍历算法的实现，学会编程的方法。熟二.实验原理树是一种应用极为广泛的数据结构，也是本门课程的重点，它的特点在于非线性。遍历操作是树众多操作的根底，所以本次实验主要强调突出二叉树的三种根本遍历操作的实现。三.实验内容(1)根据屏幕提示输入二叉树的各个结点
2、并建立该二叉树；(2)选择某种遍历方式输出该二叉树；(3)求该二叉树的叶子结点数；(4)求该二叉树的高度；(5)将该二叉树中所有结点的左、右子树相互换，并输出。实验过程：/*注：此程序为二叉树树的操作实现与应用*/#include#include#include#includetypedefintTElemType;typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;BiTNode*CreatBiTreeOBiTreeT;intch;scanf(%d,(fech);if(ch=O)T=N
3、ULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(O);T-data=ch;PrimfC请输入d的左结点：”,ch);T-lchild=CreatBiTree();PrintfC请输入d的右结点：,ch);T-rchiId=CreatBiTreeO;returnT;voidPreOrderTraverseCBiTNode*P)(if(P!=NULL)(printf(%-2d,P-data);PreOrderTraverse(P-lchiId);PreOrderTraverse(P-rchiId);)elseprintf(一,);)voi
4、dInOrderTraverse(BiTNode*P)(if(P!=NULL)InOrderTraverse(P-lchild);printf(%-2d,P-data);InOrderTraverse(P-rchild);elseprintf(一);voidPostOrderTraverse(BiTNode*P)(if(P!=NULL)(PostOrderTraverse(P-lchild);PostOrderTraverse(P-rchild);printf(%-2d,P-data);)elseprintf(一,);)voidexchange(BiTNode*P)(BiTNode*q;if(
5、P)(q=P-lchild;P-Ichild=P-rchild;P-rchild=q;exchange(P-lchild);exchange(P-rchild);)intcount_leaves(BiTNode*P)(if(!P)returnO;elseif(!P-lchild&!P-rchild)return1;elsereturncount_leaves(P-lchild)+count_leaves(P-rchild);)intTreeHigh(BiTNode*T)(intlh=0,rh=O;if(!T)returnO;lh=TrecHigh(T-lchild);rh=TrecHigh(T
6、rchild);returnlhrh?lh+l:rh+l;)voidMenu()(printf(欢送使用树的操作实现与应用系统nn);pritf*木*木木printf(*1.创立树*n);printf(*3.中序遍历二叉树*n);printf(*5.左右子树交换*n);printf(*7.求树的深度*n);printf(菜单2.先序遍历二叉树4.后序遍历二叉树6.求叶子数0.退出n);voidmain()(intn,f,high,countl;charb;BiTNode*P=NULL;system(,colorOA);SeteOnSoIeTiHee汪继超:2015201018);do(Men
7、u();printf(n请选择您需要操作的步骤(07):);fflush(stdin);scanf(%d,&n);if(n=O&n=7)f=l;else(f=0;system(,cls);Printf(您输入有误，请重新选择!n);1)while(f=0);while(f=l)(switch(n)(case 1:PrintfCn请输入根节点：”)；P=CreatBiTreeO;break;case 2:printf(n先序遍历：)；PreOrderTraverse(P);break;case 3:printf(n中序遍历：)；InOrderTraverse(P);break;case 4:Pr
8、intf(n后序遍历：)；PostOrderTraverse(P);break;case 5:exchange(P);Printf(n交换左右孩子后先序遍历：);PreOrderTraverse(P);break;case 6:count1=COUnteaves(P);printf(n二叉树的叶子结点数为：%dcountl);break;case 7:Printffn树的深度为:)；High=TreeHigh(P);printf(%d,high);break;caseO:Printfen谢谢使用，欢送下次光临！n);exit(O);default:printf(n输入错误！)；SyStem(p
9、ause);break;printf(nn是否继续进行(yorn):);fflush(stdin);scanf(%c,(fcb);if(b=yb=Y,)f=l;system(,cls);Menu();Printf(请再次选择你需要操作的步骤(0-6):);scanf(%d,fen);1elseexit(O);实验结果:主菜单：汪继超:201520101813 5 7树一工父度 初深 树遍子的 建序篇 创M求* 2460萦9 叉叉 二二 历囊 富子 叶出 先后看再次选择你需要操作的步骤一G ：1.创立树:BiTNode CreatBiTreeO data*ch;PTntfr请输入X的左结点6);
10、T-lchild-CreatBiTree();Printfr请输入”的右结点，”.ch)； T-rchildCreatBiTree(); return I; fir2015201018唐径出需要操作的步强 （即7： 11占省点点占阖点电否继续进行y。，：21.先序遍历二叉树:13 5 7哥深 树率的a-一 菜树 二交度叉叉- 历囊 停叶出请再次选择你需要操作的步熟6）： 2先序遍历：12 34是否继续进行y。尸n:22.中序遍历二叉树:13 5 7树一 H父度 招深 树遍子的 建序再 创W求历. 富子 停叶出 先后奉叉叉请再次选择你需要操作的步骤。一6:3中序遍历：一3 -2 -1 -4 一是
11、否继续进行y or n：23.后序遍历二叉树:欠迎使用树的操作实现与应用系统13 5 74UJ 枳 i一工父度 KB深 树遍子的 建序真 创求富子 居叶出 2 4 6 0fete- 叉叉 - 历场请再次选择你需要操作的步骤4后序遍历：3 24 1是否继续进行。or n：注：“一”表示树结点为空。3.左右孩子交换后先序遍历检验:建序育求 13 5 74MJ 和二 招深 树遍子的Xnr 菜遍遍子 停叶出蕾fi 叉叉 - 历戮请再次选择你需要操作的步骤06：5交换左右孩子后先序遍历：142-3是否继续进行yorn:4 .求树的叶子数:叉叉 二二富子 暂叶出 2 4 6 0作单操菜J叔一工父度 招深 树遍子的 建序音 求 13 5 7请再次选择你需要操作的步骤06）：6二叉树的叶子结点数为：2是否继续进行yOr11三5 .求树的深度:叉叉二二历囊 富子 居叶出 2 4 6 0作单J叔一工父度 树遍子的 建序音求 13 5 7请再次选择你需要操作的步骤06：6二叉树的叶子结点数为：2是否继续进行（yorn：问题讨论：I.二叉树遍历是其所有操作的根底，遍历操作中复杂的递归问题，可以通过0-5个结点的二叉树根本模型进行深度分析，总结扩展n个结点。注：文件名为：学号+次数
