数据结构上机报告6.doc

实 验 报 告 姓名 周亮 学号 2011444541 专业班级 计科2011-02 课程名称 数据结构 指导 教师 王双明 机房 名称 I515 上机日期 2012年4 月 12日 上机项目名称 树的基本操作 上机步骤及内容： 1、实验目的 1．进一步掌握指针变量、动态变量的含义； 2．掌握二叉树的结构特性，以及各种存储结构的特点和适用范围； 3．掌握用指针类型描述、访问和处理二叉树的运算。 2、内容 1 阅读并理解代码； 2 3 编程统计出计算二叉树深度、所有结点总数、度分别为2、1、0的结点数目； 3、程序代码 #includestdio.h #includemalloc.h typedef struct tree{ //树的结构定义 char data; struct tree *lchild,*rchild; //左右孩子的指针定义 }Qtree,*Ttree; char a[14] = ABC##D##EF###; //存储树中元素的数组 int i = -1; int ld,rd; //用于计算树的深度 int flage1,flage2,flage0; //用于计算度分别为2、1、0的结点数目 Ttree creat( Ttree r) // 创建树的链表 该返回值为指针类型 { i++; fflush(stdin); if( i == 0){ printf(The elements of binary tree below \n); } if( a[i] == # ) //当遇到#时 返回空指针 表明该指针不指向任何数 return NULL; else // 否则 把值存到当前指针指的内存空间中 { r = (Qtree *)malloc(sizeof(Qtree)); //动态申请内存空间 r-data = a[i] ; printf( %c ,a[i]); r-lchild = creat(r-lchild ); //分别为该结点的左右孩子指针创建树链表 r-rchild = creat(r-rchild ); } return r; // 创建完后 返回指针 } void preorder(Ttree r) //先序遍历 { if(r) //判断该指针是否为空 { printf( %c ,r-data); //输出该指针的所指向的内容 preorder(r-lchild ); //同样对左右指针调用先序遍历函数 preorder(r-rchild ); } } void inorder(Ttree r) // 中序遍历 { if( r ) { inorder( r-lchild ); printf( %c ,r-data ); inorder(r-rchild ); } } void postorder(Ttree r) //后序遍历 { if(r ) { postorder(r-lchild ); postorder(r-rchild ); printf( %c ,r-data ); } } int deep(Ttree r) // 判断深度函数 { if(!r) //当该指针指向空时 结束 返回0 return 0; else { ld = deep(r-lchild ); // 否则先对该指针所指向的结点的左右指针调用函数自身计算以它为树时所具有的深度 rd = deep(r-rchild ); if(ld = rd) //比较左右子树的深度 return rd+1; //返回该树的下面子树的深度和加上本身自己 else return ld+1; } } int degree0(Ttree r) // 判断度为0的结点个数 { int num1,num2,n = 0; if(!r) //当指针为空时结束 return 0; else if( r-lchild == NULL r-rchild == NULL ) // 否则判断该结点的左右是否都为空 n = 1;