数据结构二叉树C语言实现.docx
数学与信息技术学院20162017(下)学年计科专业2015级数据结构实验报告5学号：2015201018姓名：汪继超实验名称树的操作实现与应用完成时间一.实验目的和要求：1 .掌握树特别是二叉树的根本概念、定义和性质。2 .掌握二叉树的根本结构、内部逻辑和三种遍历算法的根本思想，悉二叉树的存储结构和指针链接的变化。3 .通过对二叉树的建立和三种遍历算法的实现，学会编程的方法。熟二.实验原理树是一种应用极为广泛的数据结构，也是本门课程的重点，它的特点在于非线性。遍历操作是树众多操作的根底，所以本次实验主要强调突出二叉树的三种根本遍历操作的实现。三.实验内容(1)根据屏幕提示输入二叉树的各个结点，并建立该二叉树；(2)选择某种遍历方式输出该二叉树；(3)求该二叉树的叶子结点数；(4)求该二叉树的高度；(5)将该二叉树中所有结点的左、右子树相互换，并输出。实验过程：/*注：此程序为二叉树树的操作实现与应用*/#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<windows.h>typedefintTElemType;typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;BiTNode*CreatBiTreeOBiTreeT;intch;scanf("%d,(fech);if(ch=O)T=NULL;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("一,');)voidInOrderTraverse(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(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->rchild);returnlh>rh?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(Menu();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:Printf("n后序遍历：")；PostOrderTraverse(P);break;case 5:exchange(P);Printf("n交换左右孩子后先序遍历：");PreOrderTraverse(P);break;case 6:count1=COUnteaves(P);printf("n二叉树的叶子结点数为：%d'countl);break;case 7:Printffn树的深度为:")；High=TreeHigh(P);printf("%d,',high);break;caseO:Printfen谢谢使用，欢送下次光临！n");exit(O);default:printf("n输入错误！")；SyStem("pause");break;printf("nn是否继续进行(yorn):");fflush(stdin);scanf("%c",(fcb);if(b='y'b='Y,)f=l;system(,cls);Menu();Printf("请再次选择你需要操作的步骤(0-6):");scanf("%d',<fen);1elseexit(O);实验结果:主菜单：汪继超:201520101813 5 7树一工父度 初深 树遍子的 建序篇 创M求* 2460萦9 叉叉 二二 历囊 富子 ½叶出 先后看再次选择你需要操作的步骤一G ：1.创立树:BiTNode CreatBiTreeO <BiTree T;int ch;SCanf(W.Gch);IF(Ch-O) T-NUlL;else(T-(BiTNode «)nalloc(sizeoF(BiTNode);if(tT) exit(t);T->data*ch;PTntfr请输入X的左结点6);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 一是否继续进行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个结点。注：文件名为：学号+次数
