资源描述：
《树的操作实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构实验报告报告名称树的操作专业网络工程班级1001学号29姓名张剑指导教师陈淑红李珍辉黄哲2012年5月22日一、实验目的：熟练掌握树的基本操作，进一步理解树的非线性特点，递归性特点和动态数据结构特点二、实验内容与基本要求：1.建立二叉树的二叉链表，2.统计二叉树中叶子结点个数3.求二叉树深度三、概要设计：1.数据结构：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树。2.抽象数据类型：基本操作P：Inittree（&T）；操作结果：构造空树T。De
2、storyTree(*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）初始
3、条件：树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的非叶子结点，则返回它的左孩子，否则返回空。Rig
4、htSibling(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
5、,Visit());初始条件：树T存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数Visit（）一次且至多一次。一旦Visit()失败,则操作失败。四、详细设计：#include#include#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;
6、/*指向右孩子*/}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!=' ')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=p;k=1;break
7、;/*为左结点*/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
8、++;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*/re
