数据结构与算法实验报告-二叉树.doc

《数据结构与算法实验报告-二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

沈阳工程学院学生实验报告（课程名称：数据结构与算法）实验题目：二叉树班级软本111学号2011417104姓名吴月芬地点F座606指导教师姜柳祝世东实验日期:2012年10月25日 一、实验目的1．掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2．掌握用指针类型描述、访问和处理二叉树的运算。二、实验环境TurboC或是VisualC++三、实验内容与要求1．输入字符序列，建立二叉链表。2．按先序、中序和后序遍历二叉树（递归算法）。3．按某种形式输出整棵二叉树。4．求二叉树的高度。5．求二叉树的叶结点个数。6．交换二叉树的左右子树。7．借助队列实现二叉树的层次遍历。8．在主函数中设计一个简单的菜单，调试上述算法，要求1-3必做，4-7为选做。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素）。图4.1所示二叉树的输入数据顺序应该是：（1,a），（2,b），（3,c），（4,d），（6,e），（7,f），（9,g），（13,h）。另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。这时，图4.1所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。12 四、实验过程及结果分析（一）二叉树1.二叉树的综合程序源代码如下所示：#include#include#defineNULL0structbitree{chardata;structbitree*lchild,*rchild;};structbitree*createbitree_1(structbitree*t){intch;scanf("%d",&ch);if(ch==0){t=NULL;}else{t->data=ch;t->lchild=(structbitree*)malloc(sizeof(structbitree));t->lchild=createbitree_1(t->lchild);t->rchild=(structbitree*)malloc(sizeof(structbitree));t->rchild=createbitree_1(t->rchild);}returnt;}structbitree*createbitree_2(structbitree*t){intch;12 scanf("%d",&ch);if(ch==0){t=NULL;}else{t->lchild=(structbitree*)malloc(sizeof(structbitree));t->lchild=createbitree_2(t->lchild);t->data=ch;t->rchild=(structbitree*)malloc(sizeof(structbitree));t->rchild=createbitree_2(t->rchild);}returnt;}voidpreorder_1(structbitree*T){if(T!=NULL){printf("%dtt",T->data);preorder_1(T->lchild);preorder_1(T->rchild);}}voidpreorder_yezi(structbitree*T){if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL)//只输出叶子节点printf("%dtt",T->data);preorder_1(T->lchild);preorder_1(T->rchild);}12 }voidinorder_1(structbitree*H){if(H){inorder_1(H->lchild);printf("%dtt",H->data);inorder_1(H->rchild);}}voidpreorder_2(structbitree*p){structbitree*s[100];inttop=-1;while(p!=NULL||top!=-1){while(p!=NULL){top++;s[top]=p;printf("%dtt",p->data);p=p->lchild;}if(top!=-1){p=s[top];top--;p=p->rchild;}}}voidpreorder_yezi_2(structbitree*p){12 structbitree*s[100];inttop=-1;while(p!=NULL||top!=-1){while(p!=NULL){top++;s[top]=p;if(p->lchild==NULL&&p->rchild==NULL)//只输出叶子节点printf("%dtt",p->data);p=p->lchild;}if(top!=-1){p=s[top];top--;p=p->rchild;}}}voidinorder_2(structbitree*p){structbitree*s[100];inttop=-1;while(p!=NULL||top!=-1){while(p!=NULL){top++;s[top]=p;p=p->lchild;}if(top!=-1)12 {p=s[top];top--;printf("%dtt",p->data);p=p->rchild;}}}voidmenu_1(){printf(" t******菜单******* ");printf("t1.树的建立 ");printf("t2.树的遍历 ");printf("t0.退出 ");}voidmenu_2(intn){if(n==1){printf(" t******菜单******* ");printf(" t1.树的递归的先序建立 ");printf(" t2.树的递归的中序建立 ");printf(" t3.树的非递归的先序建立 ");printf(" t4.树的非递归的中序建立 ");}if(n==2){printf(" t******菜单******* ");printf(" t1.树的递归的先序遍历 ");printf(" t2.树的递归的中序遍历 ");printf(" t3.树的非递归的先序遍历 ");printf(" t4.树的非递归的中序遍历 ");printf(" t5.树的递归的先序遍历叶子节点 ");12 printf(" t6.树的非递归的先序遍历叶子节点 ");}}voidmain(){structbitree*H;intn,m;H=(structbitree*)malloc(sizeof(structbitree));do{menu_1();scanf("%d",&n);if(n>2||n<0)printf(" tt您的输入有误！");elseif(n!=0){menu_2(n);scanf("%d",&m);}if(n==1){if(m==1)H=createbitree_1(H);if(m==2)H=createbitree_2(H);}if(n==2){if(m==1)preorder_1(H);if(m==2)inorder_1(H);if(m==3)preorder_2(H);if(m==4)inorder_2(H);12 if(m==5)preorder_yezi(H);if(m==6)preorder_yezi_2(H);}}while(n!=0);}2.运行过程二叉树递归的先序建立过程如图1.1所示。图1.1先序建立二叉树二叉树的递归的先序遍历如图1.2所示。12 图1.2递归先序遍历二叉树的递归的中序遍历如图1.3所示。图1.3递归的中序遍历二叉树的非递归的先序遍历如图1.4所示。12 图1.4非递归的先序遍历二叉树的非递归的中序遍历如图1.5所示。图1.5非递归的中序遍历二叉树的递归的先序遍历叶子节点如图1.6所示。12 图1.6递归的先序遍历叶子节点二叉树的非递归的先序遍历叶子节点如图1.7所示。图1.7非递归的先序遍历叶子节点结束程序操作如图1.8所示。图1.8结束程序12 五、成绩评定优良中及格不及格出勤内容格式创新效果总评指导教师：年月日12