二叉树数据结构实验报告书.doc

《数据结构》 实 验 报 告 书 实验内容：二叉树的基本运算 201100814*** 计科111 *** 前言 　　 　　计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。 　　数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。  一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] ，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。[基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符）　　则输出结果为 先序：ABCDEGF　　中序：CBEGDFA　　后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 算法设计 程序所需头文件已经预处理宏定义我们开始测试数据： 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 输出结果 说明我们成功的完成了程序。 五、总结 通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。 因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。 此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。 源代码 #includestdio.h #includestring.h #includemalloc.h #includestdlib.h #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针 int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数 //基于先序遍历算法创建二叉树 BinTree CreatBinTree(void)//要求输入先序序列，其中加入虚结点空格以示空指针的位置 { BinTree T; char ch; if((ch=getchar())== ) return(NULL); //读入空格，返回空指针 else { T=(BinTNode *)malloc(sizeof(BinTNode)); // 生成结点 T-data=ch; T-lchild=CreatBinTree(); //构造左子树 T-rchild=CreatBinTree(); //构造右子树 return(T); } } void Preorder(BinTree T)//先序遍历 { if(T) { printf(%c,T-data); //访问结点 Preorder(T-lchild); //先序遍历左子树 Preorder(T-rchild); //先序遍历右子树 } } void Inorder(BinTree T)//中序遍历 { if(T) { Inorder(T-lchild); //先序遍历左子树 printf(%c,T-data)