数据结构-实验报告3树形结构.doc

南方医科大学生物医学工程学院南方医科大学生物医学工程学院____电子信息工程电子信息工程_ _系系 数据结构数据结构实验报告实验报告1姓名姓名田媛学号学号113200880200009专业专业年年级级08 电子信息工程单单元元第第 6 章章内容内容树树形形结结构构日期日期2010-6-18实验题实验题目目实验三实验三 树形结构树形结构（综合性实验（综合性实验 3 学时）学时）实验实验目的目的本次实习的目的在于深入了解二叉树的特征及对其进行的基本操作，在此基 础上培养应用二叉树解决实际问题的能力实验实验内容内容一、必做一、必做题题： ：1、 给定一棵用二叉链表表示的二叉树，其根指针为 root试写出求二叉树结点数目 的算法（递归算法或者非递归算法） 2、 给定一棵用二叉链表表示的二叉树，其根指针为 root使写出求二叉树的深度的 算法二、二、选选做做题题： ：1、二叉树的建立与遍历[问题描述] 建立一棵二叉树，并对其进行遍历（先序、中序、后序） ，打印输出遍历结 果[基本要求] 从键盘接受输入（先序） ，以二叉链表作为存储结构，建立二叉树（以先序 来建立） ，并采用递归算法对其进行遍历（先序、中序、后序） ，将遍历结果打印输出。

[测试数据] ABCффDEфGффFффф（其中 ф 表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA实验实验要求及要求及 讨论讨论（本次（本次实验实验的的要求是否达要求是否达 到，有何到，有何问题问题， ，是怎么解决是怎么解决 的）的）一、抄写自己所选择的题目 二、写出算法设计思路 三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范 围等可能出现的异常问题）四、写出算法设计、编程和调试运行的体会数据结构实验报告数据结构实验报告一、抄写自己所选择的题目 1.给定一棵用二叉链表表示的二叉树，其根指针为 root试写出求二叉树结点数目的算法（递归算法或者非递归 算法） 2.给定一棵用二叉链表表示的二叉树，其根指针为 root使写出求二叉树的深度的算法二、写出算法设计思路 1.先要求用户以先序的形式输入所要操作的二叉树，接着构建一个用二叉链表表示的二叉树，根指针为 root然后在 对输入的二叉树进行中序遍历的同时计算出结点的数目，输出最后结果 2. 先要求用户以先序的形式输入所要操作的二叉树，接着构建一个用二叉链表表示的二叉树，根指针为 root。

然后， 调用计算二叉树的深度函数，计算出深度后将其输出南方医科大学生物医学工程学院南方医科大学生物医学工程学院____电子信息工程电子信息工程_ _系系 数据结构数据结构实验报告实验报告2三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题） 1./*/* header.hheader.h 头文件头文件*/*/#include#include#include /* malloc()等 */#include /* INT_MAX 等 */#include /* EOF(=^Z 或 F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */#include/* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 /*“shiy3-1.c“/*“shiy3-1.c“给定一棵用二叉链表表示的二叉树，其根指针为给定一棵用二叉链表表示的二叉树，其根指针为 root.root.求二叉树结点数目求二叉树结点数目 */*/#include“header.h“typedef char TElemType;TElemType Nil=' '; /* 以空格表示字符型为空 */int t=0; /* 定义宏观变量 t 来计算结点数目 */typedef struct BiTNode /* 二叉树的二叉链表存储结构体 */{ TElemType data;struct BiTNode *lchild,*rchild; /* 左右孩子指针 */}BiTNode,*BiTree;void CreateBiTree(BiTree *T) /* 构造以先序输入的二叉树，一空格表示无子树 */{ TElemType ch;scanf(“%c“,if(ch==Nil) /* 输入空格的情况 */*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)->data=ch; /* 生成 root 结点 */CreateBiTree( /* 以递归方式构造左、右子树 */CreateBiTree(}}Status BiTreeEmpty(BiTree T) /* 判断二叉树是否为空*/{ if(T)南方医科大学生物医学工程学院南方医科大学生物医学工程学院____电子信息工程电子信息工程_ _系系 数据结构数据结构实验报告实验报告3return FALSE;elsereturn TRUE;}void InOrderTraverse(BiTree T,Status(*Visit)(TElemType)) /*中序遍历二叉树*/{ if(T){InOrderTraverse(T->lchild,Visit); /* 先中序遍历左子树 */Visit(T->data); /* 再访问根结点 */InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */t++;}}Status visitT(TElemType e){return OK;}void main(){ int i;BiTree T,p,c;TElemType e1,e2;printf(“请先序输入二叉树(如:abc__d__e__表示 a 为根结点；b,e 为 a 的左右子树；c,d 为 b 的左右子树的二 叉树（“_”表示空格）)：\n“);CreateBiTree(if(BiTreeEmpty(T)) printf(“您输入的二叉树是空的。

\n“);InOrderTraverse(T,visitT);printf(“\n 您输入的二叉树结点数目为：%d\n“,t);getch();} 2 2．．/*/* “shiy3-2.c““shiy3-2.c“ 给定一棵用二叉链表表示的二叉树，其根指针为给定一棵用二叉链表表示的二叉树，其根指针为 rootroot求二叉树深度求二叉树深度 */*/#include“header.h“typedef char TElemType;TElemType Nil=' '; /* 以空格表示字符型为空 */typedef struct BiTNode /* 二叉树的二叉链表存储结构体 */{ TElemType data;struct BiTNode *lchild,*rchild; /* 左右孩子指针 */}BiTNode,*BiTree;void CreateBiTree(BiTree *T) /* 构造以先序输入的二叉树，一空格表示无子树 */{ TElemType ch;scanf(“%c“,if(ch==Nil) /* 输入空格的情况 */*T=NULL;else{南方医科大学生物医学工程学院南方医科大学生物医学工程学院____电子信息工程电子信息工程_ _系系 数据结构数据结构实验报告实验报告4*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)->data=ch; /* 生成 root 结点 */CreateBiTree( /* 以递归方式构造左、右子树 */CreateBiTree(}}Status BiTreeEmpty(BiTree T) /* 判断二叉树是否为空*/{ if(T)return FALSE;elsereturn TRUE;}int BiTreeDepth(BiTree T) /* 计算二叉树深度 */{ int i,j;if(!T)return 0;if(T->lchild)i=BiTreeDepth(T->lchild);elsei=0;if(T->rchild)j=BiTreeDepth(T->rchild);elsej=0;return i>j?i+1:j+1;}void main(){ int i;BiTree T,p,c;TElemType e1,e2;printf(“如:abc__d__e__表示 a 为根结点；b,e 为 a 的左右子树；c,d 为 b 的左右子树的二叉树（“_”表示空 格）)：\n“);CreateBiTree(if(BiTreeEmpty(T)) printf(“您输入的二叉树是空的。

\n“);elseprintf(“\n 树的深度为：%d\n“,BiTreeDepth(T));getch();}四、写出算法设计、编程和调试运行的体会由于我的 C 功底比较薄弱，每次编程只能和好友合作进行，已尽可能多学到一点东西，三次实验课下来我的收获 也是很多，简单的程序已近可以独立完成了渐渐的我发现在我手指下敲出的数码有了生命每一个程序的调试都是 一个不小的挑战，尽管艰难，但是就像老妈说的苦尽甘来，我挺过来了伴随着一个又一个程序的实现，我的能力也南方医科大学生物医学工程学院南方医科大学生物医学工程学院____电子信息工程电子信息工程_ _系系 数据结构数据结构实验报告实验报告1在一步一步的提升着。