树的操作实验报告

数据结构实验报告报告名称树的操作专业网络工程班级1001学号29姓名张剑指导教师陈淑红李珍辉黄哲2012年5月22日一、实验目的：熟练掌握树的根本操作，进一步理解树的非线性特点，递归性特点和动态数据结构特点二、实验内容与根本要求：1.建立二叉树的二叉链表，2.统计二叉树中叶子结点个数3.求二叉树深度三、概要设计：数据结构：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：假设D为空集，那么称为空树。抽象数据类型：根本操作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()失败,那么操作失败。四、详细设计：#include<stdio.h>#include<malloc.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(lchilddep>rchilddep)?(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; } }}五、调试分析及测试结果：测试数据：ABCDABCDEFGADBC实现提示：按先序遍历序列建立二叉树的二叉链表；2.用递归的方法统计二叉树中叶子结点个数和求二叉树的深度。3．利用“非递归中序遍历”算法求上面两棵二叉树的中序序列。测试结果及分析：1.运行程序，进入功能选择界面，先测试数据一，按要求输入二叉树显示如下。图一2.选择功能1，此时输出二叉树。图二3.进入功能2，求二叉树的深度，此二叉树的深度为3，可知结果是正确的。图三4.进入功能3，得到二叉树的结点个数。图四5.按数字键4.可输出二叉树中叶子结点的个数。图五6.按中序遍历非递归算法输出二叉树。图六7.退出程序。