欢迎来到天天文库
浏览记录
ID:56707881
大小:53.50 KB
页数:6页
时间:2020-07-05
《数据结构 二叉链表 C++实现.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验报告一、实验目的1.掌握二叉树的数据类型描述及二叉树的特性。2.掌握二叉树的链式存储结构(二叉链表)的建立算法。3.掌握二叉链表上二叉树的基本运算的实现。二、实验内容1.实现二叉树的层次递进。2.将一颗二叉树的所有左右子树进行交换。三、实验与算法分析二叉树的遍历二叉树的层次遍历采用的是队列。本题用一个一维数组来代替队列,同时设置队列的对头指针和队尾指针。算法分析:自定义3个函数:结构structbitree;建立二叉链表的函数bitree*create();按层次遍历二叉链表的函数voidlorder(bitree*t)。结构structb
2、itree中包括数据域和两个指针域(一个指向左孩子,另一个指向右孩子)。建立二叉链表的函数bitree*create()中先建立一个空队列(条件是front=1,rear=0)。然后建立二叉链表,用一个一维数组来代替队列,存放输入的结点;输入结点时,必须按照完全二叉树的形式输入;如果非完全二叉树,则必须给定一些假象结点(虚结点),使之完全符合完全二叉树形式。当我们输入“,”时表示虚结点(结点不存在);输入结点值时,存在的结点则输入它对应的字符;最后以一个特殊字符“#”作为输入的结束,表示二叉链表已经完成。层次遍历二叉链表的函数voidlorde
3、r(bitree*t)中遍历结束条件为头指针下标大于尾指针下标。将一棵二叉树的所有左右子树进行交换建立二叉树及先序voidpreorder(bitree*root)、中序voidinorder(bitree*root)、后序voidpostorder(bitree*root)3种遍历算法都写成子函数,然后分别在子函数中调用。然后再建立一个实现左右子树交换的函数voidleftTOright(bitree*r)。左右子树交换的遍历算法为:若二叉树为空,算法结束;否则:交换左子树的左子树和右子树;交换右子树的左子树和右子树;交换左子树和右子树的位置
4、。最后,是程序的主函数main(),它包含建立二叉链表,输出交换前二叉树的先序、中序、后序的结果,输出交换后二叉链表的先序、中序、后序的遍历结果。输出前后结果,方便比较顺序变化。四、可执行程序及注释二叉树层次遍历#includetypedefcharelemtype;structbitree{elemtypedata;bitree*lchild,*rchild;};bitree*create()//建立二叉连表{bitree*q[100];//定义q数组作为队列存放二叉链表中的结点,100为最大容量bitree*s;//
5、二叉链表中的结点bitree*root;//二叉链表的根指针intfront=1,rear=0;//定义队列的头指针、尾指针charch;//结点的data域值root=NULL;cout<<"请输入结点值(不存在的结点用‘,’表示,‘#’表示结束)"<>ch;while(ch!='#')//输入值为#号,算法结束{s=NULL;if(ch!=',')//输入数据不为逗号,表示不为虚结点,否则为虚结点{s=newbitree;s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;q
6、[rear]=s;//新结点或虚结点进队if(rear==1)root=s;else{if((s!=NULL)&&(q[front]!=NULL)){if(rear%2==0)//rear为偶数,s为双亲左孩子q[front]->lchild=s;else//rear为奇数,s为双亲右孩子q[front]->rchild=s;}if(rear%2==1)front++;//出队}cin>>ch;}returnroot;}voidlorder(bitree*t)//按层次遍历二叉树{bitree*q[100],*p;//q代表队列intf,r;/
7、/f、r类似于队列头指针、尾指针q[1]=t;f=r=1;cout<<"按层次遍历二叉树的结果为:";while(f<=r){p=q[f];f++;//出队cout<data<<"";if(p->lchild!=NULL){r++;//入队q[r]=p->lchild;}if(p->rchild!=NULL){r++;//入队q[r]=p->rchild;}}cout<8、includetypedefcharelemtype;structbitree{elemtypedata;bitree*lch
8、includetypedefcharelemtype;structbitree{elemtypedata;bitree*lch
此文档下载收益归作者所有