数据结构 二叉链表 C++实现.doc

《数据结构 二叉链表 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