天津理工大学数据结构实验报告3.pdf

《天津理工大学数据结构实验报告3.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验（三）实验名称二叉树的遍历软件环境　　　　Windows98/2000,VC++6.0或turboC硬件环境PⅡ以上微型计算机实验目的　理解二叉树的逻辑特点，掌握二叉链表存储结构，掌握二茬树遍历算法的递归与非递归实现实验内容（应包括实验题目、实验要求、实验任务等）二叉树的遍历利用二叉链表作为存储结构建立一棵二叉树，每个结点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，结点数不少于5个。要求分别以先序、中序和后序进行遍历，输出遍历结果。并编写一递归算法，交换该二叉树中所有结点的左、右孩子。实验过程与实

2、验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：1.创建二叉链表的结点存储结构及数据的输入输出函数因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。1.1数据的输入函数indata()当输入的字符不为'0'时，以尾插法将数据插入单链表。1.2数据的输出函数直接输出单链表。2.生成二叉链表利用先序遍历生成二叉链表：2.1用单链表s记录输入的数据2.2若单链表s为空，则二叉链表结点为空，否则根节点=s，利用递归调用分别生成根节点的左子树和右子树

3、2.3返回二叉链表3.先序遍历、中序遍历、后序遍历二叉链表3.1先序遍历：访问根节点，左子树，右子树的顺序3.2中序遍历：访问左子树，根节点，右子树的顺序3.3后序遍历：访问左子树，右子树，根节点的顺序利用递归调用分别用以上三种顺序遍历二叉链表。4.交换二叉链表的左右孩子当二叉链表的结点左孩子或者右孩子都不为空时，利用递归调用，分别交换左子树很右孩子的左右孩子，最后将根节点的左右孩子指针交换。5.主函数5.1调用生成二叉链表的函数，从键盘输入二叉链表的各个结点5.2分别调用先序遍历、中序遍历、后序遍历二叉链表函数，输出所有结点5.3交换二叉

4、链表的左右孩子5.4重复5.2结论：　　输入各个结点：apple、pear、orange、banana、peach、grape、watermelon　　先序遍历输入与输入一致　　中序遍历输出：orange、pear、banana、apple、grape、peach、watermelon　　后序遍历输出：orange、banana、pear、grape、watermelon、peach、apple　　交换二叉树的左右孩子后　　先序遍历输出：apple、peach、watermelon、grape、pear、banana、orange编程中出现

5、的问题：输入的二叉链表左右子树必须对称，如果不对称，交换二叉树的左右子树后，程序出错，不知道出错在哪，没有调试成功。附录（可包括源程序清单或其它说明）#include#include#include#includeusingnamespacestd;typedefstructLNode{//二叉链表数据存储结构chardata;structLNode*next;}LNode,*LinkList;typedefstructBiTNode{//二叉链表节点存储结构Link

6、Listdata;structBiTNode*lchild;structBiTNode*rchild;//左右孩子指针}BiTNode,*BiTree;voidoutdata(LinkListL){//输出数据LinkListp;p=L->next;while(p!=NULL){cout<data;p=p->next;}cout<<"";}LinkListindata(){//输入数据LinkListL,p,r;charx;r=L=(LinkList)malloc(sizeof(LNode));L->next=NULL;cin>>x

7、;while(x!='0'){p=(LinkList)malloc(sizeof(LNode));p->data=x;p->next=NULL;r->next=p;r=p;cin>>x;}returnL;}BiTreeCreateBiTree(BiTree&T){//先序遍历生成二叉树LinkLists=indata();if(s->next==NULL)T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)exit(1);T->data=s;CreateBiTree(T->lchild

8、);//建立左子树CreateBiTree(T->rchild);//建立右子树}returnT;}voidPreOrder(BiTreeroot){//先序遍二叉树if(roo