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

计算机科学与工程系PAGEPAGE6计算机科学与工程系实验（三）实验名称二叉树的遍历软件环境Windows98/2000,VC++6.0或turboC硬件环境PⅡ以上微型计算机实验目的理解二叉树的逻辑特点，掌握二叉链表存储结构，掌握二茬树遍历算法的递归与非递归实现实验内容（应包括实验题目、实验要求、实验任务等）二叉树的遍历利用二叉链表作为存储结构建立一棵二叉树，每个结点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，结点数不少于5个。要求分别以先序、中序和后序进行遍历，输出遍历结果。并编写一递归算法，交换该二叉树中所有结点的左、右孩子。实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：创建二叉链表的结点存储结构及数据的输入输出函数因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。数据的输入函数indata()当输入的字符不为‘0’时，以尾插法将数据插入单链表。数据的输出函数直接输出单链表。生成二叉链表利用先序遍历生成二叉链表：用单链表s记录输入的数据若单链表s为空，则二叉链表结点为空，否则根节点=s，利用递归调用分别生成根节点的左子树和右子树返回二叉链表先序遍历、中序遍历、后序遍历二叉链表先序遍历：访问根节点，左子树，右子树的顺序中序遍历：访问左子树，根节点，右子树的顺序后序遍历：访问左子树，右子树，根节点的顺序利用递归调用分别用以上三种顺序遍历二叉链表。交换二叉链表的左右孩子当二叉链表的结点左孩子或者右孩子都不为空时，利用递归调用，分别交换左子树很右孩子的左右孩子，最后将根节点的左右孩子指针交换。主函数调用生成二叉链表的函数，从键盘输入二叉链表的各个结点分别调用先序遍历、中序遍历、后序遍历二叉链表函数，输出所有结点交换二叉链表的左右孩子重复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编程中出现的问题：输入的二叉链表左右子树必须对称，如果不对称，交换二叉树的左右子树后，程序出错，不知道出错在哪，没有调试成功。附录（可包括源程序清单或其它说明）#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string>usingnamespacestd;typedefstructLNode{//二叉链表数据存储结构 chardata; structLNode*next;}LNode,*LinkList;typedefstructBiTNode{//二叉链表节点存储结构 LinkListdata; structBiTNode*lchild; structBiTNode*rchild;//左右孩子指针}BiTNode,*BiTree;voidoutdata(LinkListL){//输出数据 LinkListp; p=L->next; while(p!=NULL){ cout<<p->data; p=p->next; } cout<<"";}LinkListindata(){//输入数据 LinkListL,p,r; charx; r=L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; cin>>x; 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);//建立左子树 CreateBiTree(T->rchild);//建立右子树 } returnT;}voidPreOrder(BiTreeroot){//先序遍二叉树 if(root==NULL)return; outdata(root->data); PreOrder(root->lchild); PreOrder(root->rchild);}voidInOrder(BiTreeroot){//中序遍历二叉树 if(root==NULL)return; InOrder(root->lchild); outdata(root->data); InOrder(root->rchild);}voidPostOrder(BiTreeroot){//后序遍历二叉树 if(root==NULL)return; PostOrder(root->lchild); PostOrder(root->rchild); outdata(root->data);}voidexchange(BiTree&root){//交换二叉树的左右孩子 BiTreetemp; if(root->lchild!=NULL||root->rchild!=NULL){ exchange(root->lchild); exchange(root->rchild); temp=root->lchild; root->lchild=root->rchild; root->rchild=temp; }}voidmain(){ BiTreeT; cout<<"请输入水果名作为数的每个节点，空节点请输入0，每个单词后以0结尾"<<endl; CreateBiTree(T); cout<<"先序遍历二叉树："; PreOrder(T); cout<<endl<<"中序遍历二叉树："; InOrder(T); cout<<endl<<"后序遍历二叉树："; PostOrder(T); cout<<endl<<"交换二叉树的左右孩子"; exchange(T); cout<<endl<<"先序遍历二叉树："; PreOrder(T); cout<<endl<<"中序遍历二叉树："; InOrder(T); cout<<endl<<"后序遍历二叉树："; PostOrder(T); cout<<endl;}运行结果：天津理工大学计算机科学与工程系实验报告20XX至2