二叉树实验报告.docx

《二叉树实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》实验报告书实验内容：二叉树的基本运算院系：计算机学院班级：计算机科学与技术学号：20110&*******姓名：***前言　　　　计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，

2、必须具备较强的数据结构基础。　　数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容建立一棵二叉树，试编程实现二叉树的如下基本操作：1.按先序序列构造一棵二叉链表表示的二叉树T；2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3.求二叉树的

3、深度/结点数目/叶结点数目；(选做)4.将二叉树每个结点的左右子树交换位置。（选做）[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），[测试数据]如输入：ABCффDEфGффFффф（其中ф表示空格字符）　　则输出结果为先序：ABCDEGF　　中序：CBEGDFA　　后序：CGEFDBA层序：ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。四、算法设计本程序按照实验内容的要球从键盘上输入数据建立先序建立二叉树，并用递归的算法分

4、别实现了对二叉树的先序、中序、后序以及层次遍历。选做的题目实现了二叉树的左右子树交换。建立树时，如果遇到了空，就输入“#”。树的链式存储结构定义：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*Tree;先序序列建立二叉树：按下弄次序顺序读入字符：ABC##DE#G##F###(其中“#”代表为空)按先序次序输入二叉树中结点的值（一个字符），#代表为空树。构造二叉树链表表示二叉树T：intTree_creat(Tree&T)//先序建立二叉树{charx;cin>>x;if(x==

5、'#')T=NULL;else{T=newBiTNode;if(!T)exit(1);T->data=x;//生成要结点Tree_creat(T->lchild);//构造左子树Tree_creat(T->rchild);//构造右子树}return0;}二叉树的先序遍历输出：采用递归的算法利用函数preorder(TreeT),并先判断是否为空，如果不为空，指向左孩子，指向右孩子。voidpreorder(TreeT)//二叉树的先序遍历输出{if(T!=NULL){cout<data;preorder(T->lchild);preorder(T->rchild);}}中序遍

6、历输出：思想同先序，根结束，左孩子，右孩子访问顺序不一样：voidinorder(TreeT)//二叉树的中序遍历输出{if(T!=NULL){inorder(T->lchild);cout<data;inorder(T->rchild);}}后序遍历输出：posorder()voidposorder(TreeT)//二叉树的后序遍历输出{if(T!=NULL){posorder(T->lchild);posorder(T->rchild);cout<data;}}层次遍历输出：cengorder()voidcengorder(TreeT)//二叉树的层次遍历输出{qu

7、euep;p.d[0]=T;p.f=0;p.T=1;while(p.fdata;p.d[p.T++]=p.d[p.f]->lchild;p.d[p.T++]=p.d[p.f]->rchild;p.f++;}else{p.f++;}}cout<