树的操作实验报告

数据结构实验报告报告名称树的操作专业网络工程班级1001学号29姓名张剑指导教师陈淑红李珍辉黄哲2012年5月22日一、实验目的：熟练掌握树的基本操作，进一步理解树的非线性特点，递归性特点和动态数据结构特点二、实验内容与基本要求：1.建立二叉树的二叉链表，2.统计二叉树中叶子结点个数3.求二叉树深度三、概要设计：1.数据结构：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树。2.抽象数据类型：基本操作P：Inittree（&T）；操作结果：构造空树T。DestoryTree(*T)初始条件：树T存在。操作结果：销树T。CreateTree（&T）初始条件：definition给树T的定义。操作结果;按definition构造树T。ClearTree（&T）初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty（T）初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则返回FALSE。TreeDepth（T）初始条件：树T存在。操作结果：返回T的深度。Root（T）初始条件：树T存在。操作结果：返回T的根。Valul（T，cur-e）初始条件：树T存在，cur-e是T中某个结点。操作结果：返回cur-e的值。Assign(T,cur-e,value);初始条件：树T存在，cur-e是T中某个结点。操作结果：结点cur-e赋值为alue。Parent(T,cur-e)初始条件：树T存在，cur-e是T中某个结点。操作结果：若cur-e是T的非根结点，怎返回它的双亲，否则函数值为空。LeftChild(T,cur-e);初始条件：树T存在，cur-e是T中某个结点。操作结果：若cur-e是T的非叶子结点，则返回它的左孩子，否则返回空。RightSibling(T,cur-e);初始条件：树T存在，cur-e是T中某个结点。操作结果：若cur-e有右兄弟，则返回它的右兄弟，否则函数值为空。InsertChild(&T,&p,i,c)初始条件：树T存在，p指向T中某个结点，1=i=p所指结点的度+1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵树。DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1=i=p所指结点的度。操作结果：删除c为T中p指结点的第i棵树。TraverseTree(T,Visit());初始条件：树T存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数Visit（）一次且至多一次。一旦Visit()失败,则操作失败。四、详细设计：#includestdio.h#includemalloc.h#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;voidCreateBTNode(BTNode*&b,charstr[])/*由str串创建二叉链*/{BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;chara[MaxSize];gets(a);str=a;charch;b=NULL;/*建立的二叉树初始时为空*/ch=str[j];while(ch!='\0')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=p;k=1;break;/*为左结点*/case')':top--;break;case',':k=2;break;/*为右结点*/default:p=(BTNode*)malloc(sizeof(BTNode));p-data=ch;p-lchild=p-rchild=NULL;if(b==NULL)/*p指向二叉树的根结点*/b=p;else/*已建立二叉树根结点*/{switch(k){case1:St[top]-lchild=p;break;case2:St[top]-rchild=p;break;}}}j++;ch=str[j];}}intBTNodeDepth(BTNode*b)/*求二叉树b的深度*/{intlchilddep,rchilddep;if(b==NULL)return(0);/*空树的高度为0*/else{lchilddep=BTNodeDepth(b-lchild);/*求左子树的高度为lchilddep*/rchilddep=BTNodeDepth(b-rchild);/*求右子树的高度为rchilddep*/return(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1);}}voidDispBTNode(BTNode*b)/*以括号表示法输出二叉树*/{if(b!=NULL){printf(%c,b-data);if(b-lchild!=NULL||b-rchild!=NULL){printf(();DispBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf());}}}intNodes(BTNode*b)/*求二叉树b的结点个数*/{intnum1,num2;if(b==NULL)return0;elseif(b-lchild==NULL&&b-rchild==NULL)return1;else{num1=Nodes(b-lchild);num2=Nodes(b-rchild);return(num1+num2+1);}}intLeafNodes(BTNode*b)/*求二叉树b的叶子结点个数*/{intnum1,num2;if(b==NULL)return0;elseif(b-lchild==NULL&&b-rchild==NULL)return1;else{num1=LeafNodes(b-lchild);num2=LeafNodes(b-rchild);return(num1+num2);}}voidInOrder(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;if(b!=NULL){p=b;while(top-1||p!=NULL){while(p!=NULL){top++;St[top]=p;p=p-lchild;}if(top-1){p=St[top];top--;printf(%c,p-data);p=p-rchild;}}printf(\n);}}voidmain(){BTNode*b,*p,*lp,*rp;intc,x;char*s;printf(/*******************本程序可实现如下功能*********************/\n);printf(\t1.输出输出二叉树t\n\t2.求二叉树的深度t\n\t3.求二叉树的结点个数t\n\t4.求二叉树的叶子结点个数t\n\t5.二叉树的中序遍历非递归算法表示t\n\t6.退出程序.\n);printf(请输入二叉树：);CreateBTNode(b,s);printf(\n);while(c){printf(请选择您要进入的功能:);scanf(%d,&x);switch(x){case1:getchar();printf((1)输出二叉树:);DispBTNode(b);printf(\n);printf(\n);break;case2:getchar();printf((2)二叉树b的深度:%d\n,BTNodeDepth(b));printf(\n);break;case3:getchar();printf((3)二叉树b的结点个数:%d\n,Nodes(b));printf(\n);break;case4:getchar();printf((4)二叉树b的叶子节点个数:%d\n,LeafNodes(b));printf(\n);break;case5:getchar();printf((5)中序遍历序列非递归算法：);InOrder(b);printf(\n);printf(\n);break;case6:getchar();c=0;break;default:printf(输入错误，请重试！\n);break;}}}五、调试分析及测试结果：测试数据：1、2、实现提示：1.按先序遍历序列建立二叉树的二叉链表；2.用递归的方法统计二叉树中叶子结点个数和求二叉树的深度。3．利用“非递归中序遍历”算法求上面两棵二叉树的中序序列。测试结果及分析：ADBCABCDEFG1.运行程序，进入功能选择界面，先测试数据一，按要求输入二叉树显示如下。图一2.选择功能1，此时输出二叉树。图二3.进入功能2，求二叉树的深度，此二叉树的深度为3，可知结果是正确的。图三4.进入功能3，得到二叉树的结点个数。图四5.按数字键4.可输出二叉树中叶子结点的个数。图五6.按中序遍历非递归算法输出二叉树。图六7.退出程序。图七8.测试数据2，显示结果如下。图八六、实验心得及经验教训：通过这次实验，掌握了数据结构中树的一些基本操作。知道了怎样有C语言实现输出二叉树，以及求二叉树的深度，结点个数和二叉树的叶子结点的个数。基本上知道了二叉树前序，中序，后续遍历的递归和非递归算法的实现。学到了很多，认真对待每一次实验，做好每一次实验。就会发现做实验也是一种乐趣，没一个实验的成功都是一种乐趣。