数据结构二叉链表c实现

《数据结构二叉链表c实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告一、实验目的1.掌握二叉树的数据类型描述及二叉树的特性。2.掌握二叉树的链式存储结构(二叉链表)的建立算法。3.掌握二叉链表上二叉树的基本运算的实现。二、实验内容1.实现二叉树的层次递进。2.将一颗二叉树的所有左右子树进行交换。三、实验与算法分析二叉树的遍历二叉树的层次遍历采用的是队列。本题用一个一维数组来代替队列，同时设置队列的对头指针和队尾指针。算法分析：自定义3个函数：结构structbitree；建立二叉链表的函数bitree*create()；按层次遍历二叉链表的函数voidlorder(bitree*t)。结构structbitree屮包括数据域

2、和两个指针域(一个指向左孩子，另一个指向右孩子)。建立二叉链表的函数bitree*create()中先建立一个空队列(条件是front=1,rear=0)0然后建立二叉链表，用一个一维数组來代替队列，存放输入的结点；输入结点时，必须按照完全二叉树的形式输入；如果非完全二叉树，则必须给定一些假象结点(虚结点),使Z完全符合完全二叉树形式。当我们输入“，”时表示虚结点(结点不存在)；输入结点值时，存在的结点则输入它对应的字符；最后以一个特殊字符“#”作为输入的结束,表示二叉链表已经完成。层次遍历二叉链表的函数voidlorder(bitree*t)中遍历结朿条件为头指针

3、下标大于尾指针下标。将一棵二叉树的所有左右子树进行交换建立二叉树及先序voidpreorder(bitree*root)>中序voidinorder(bitree*root)^丿匸序voidpostorder(bitree*root)3种遍历算法都写成子函数，然后分別在子函数+1调用。然后再建立一个实现左右子树交换的函数voidleftTOright(bitree*r)o左右子树交换的遍历算法为：若二叉树为空，算法结束；否则：交换左子树的左子树和右子树；交换右子树的左子树和右子树；交换左子树和右子树的位置。最后，是程序的主函数main(),它包含建立二叉链表，输出交

4、换前二叉树的先序、中序、后序的结果，输出交换后二叉链表的先序、中序、后序的遍历结果。输出前后结果，方便比较顺序变化。四、可执行程序及注释二叉树层次遍历#includetypedefcharelemtype;structbitreeelemtypedata;bitree*lchild9*rchild;bitree*create()〃建立二叉连表bitree*q[100];〃定义q数组作为队列存放二叉链表中的结点，100为最大容量bitree*s;〃二叉链表中的结点bitree*root;〃二叉链表的根指针intfront=l,rear=0;〃定

5、义队列的头指针、尾指针charch;〃结点的data域值root=NULL;coutvv“请输入结点值(不存在的结点用T表示，表示结束)H«endl;cin»ch;while(ch!=*#r)〃输入值为#号，算法结束{s=NULL;if(ch!=T)〃输入数据不为逗号，表示不为虚结点，否则为虚结点{s=newbitree;s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;q[rear]=s;〃新结点或虚结点进队if(rear==l)root=s;elseif((s!=NULL)&&(q[front]!=NULL)){i

6、f(rear%2==0)//rear为偶数，s为双亲左孩子q[front]->lchild=s;else//rear为奇数，s为双亲右孩子q[frontj->rchild=s;}if(rear%2==l)front++;〃出队cin»ch;}returnroot;}voidlorder(bitree*t)f〃按层次遍历二叉树ibitree*q[100],*p;intf.r;//q代表队列〃f、r类似于队列头指针、尾指针q[l]=t；f=r=l;cout«"按层次遍历二叉树的结果为：”；while(f<=r){p=q[fl;f++；〃出队cout«p->data«nH

7、;if(p->lchild!=NULL){r++;〃入队q[rj=p->lchild;}if(p->rchild!=NULL){r++;〃入队q[rj=p->rchild;}}cout«endl;}voidmain(){bitree*t;t=create();〃建立二叉连表lorder(t);〃按层次遍历二叉树c:Docu>eiitsandSettingsAd>inistrator桌面DebugText1.exe贋输入结点值（不存在的结点用T表示,纸表示结東）abc,ej.itt快层次遍历二叉树的结垄为：abceiPressanykeytoconti