《数据结构二叉链表C++实现》由会员分享，可在线阅读，更多相关《数据结构二叉链表C++实现（6页珍藏版）》请在金锄头文库上搜索。
1、实验报告实验目的1. 掌握二叉树的数据类型描述及二叉树的特性。2. 掌握二叉树的链式存储结构(二叉链表)的建立算法。3. 掌握二叉链表上二叉树的基本运算的实现。实验内容1 .实现二叉树的层次递进。2 .将一颗二叉树的所有左右子树进行交换。实验与算法分析二叉树的遍历树叉树的层次遍历采用的是队列。本题用一个一维数组来代替队列，同时设置队列 的对头指针和队尾指针。算法分析：自定义3个函数：结构 struct bitree;建立二叉链表的函数bitree *create();按层次遍历二叉链表的函数void lorder(bitree *t)。结本勾struct bitree中包括数据域和两个指针域(
2、一个指向左孩子，另一个指向右孩 子)。建立二叉链表的函数bitree *create()中先建立一个空队列 (条件是front=1 ,rear=0)。然后建立二叉链表，用一个一维数组来代替队列，存放输入的结点；输入结点时，必须 按照完全二叉树的形式输入；如果非完全二叉树，则必须给定一些假象结点(虚结点)，使之完全符合完全二叉树形式。当我们输入“，”时表示虚结点(结点不存在)；输入结点值时，存在的结点则输入它对应的字符；最后以一个特殊字符#”作为输入的结束，表示二叉链表已经完成。层次遍历二叉链表的函数void lorder(bitree *t)中遍历结束条件为头指针下标大于尾指针下标。将一棵二叉
3、树的所有左右子树进行交换建立二叉机及先序 void preorder(bitree *root)、中序 void inorder(bitree *root)、后 序void postorder(bitree *root)3种遍历算法都写成子函数，然后分别在子函数中调用。 然后再建立一个实现左右子树交换的函数void leftTOright( bitree *r)。左右子树交换的遍历算法为：若二叉树为空，算法结束；否则：交换左子树的左子树和右子树；交换右子 树的左子树和右子树；交换左子树和右子树的位置。最后，是程序的主函数 main (),它包含 建立二叉链表，输出交换前二叉树的先序、 中序、后
4、序的结果，输出交换后二叉链表的先序、中序、后序的遍历结果。输出前后结果，方便比较顺序变化。四、 可执行程序及注释二叉树层次遍历#include typedef char elemtype;struct bitreeelemtype data;bitree *lchild,*rchild;bitree *create()/ 建立二叉连表bitree *q100; 定义q数组作为队列存放二叉链表中的结点，100为最大容量bitree *s;二叉链表中的结点bitree *root;二叉链表的根指针int front=1,rear=0;定义队列的头指针、尾指针char ch;结点的data域值roo
5、t=NULL;cout请输入结点值(不存在的结点用:表示，#表示结束)ch;while(ch!=#)输入值为#号，算法结束s=NULL;if(ch!=,)输入数据不为逗号，表示不为虚结点，否则为虚结点s=new bitree;s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;qrear=s;新结点或虚结点进队if(rear=1)root=s;elseif(s!=NULL)&(qfront!=NULL)if(rear%2=0)/rear为偶数，s为双亲左孩子qfront-lchild=s;else/rear为奇数，s为双亲右孩子qfront-rchild=s
6、;if(rear%2=1) front+;出队 cinch;return root;void lorder(bitree *t)/ 按层次遍历二叉树bitree *q100,*p; int f,r;/q代表队列f、r类似于队列头指针、尾指针qi=t; f=r=1;cout按层次遍历二叉机勺结果为：;while (f=r) p=qf;f+；出队coutdatalchild!=NULL) r+;入队qr=p-lchild; if(p-rchild!=NULL) r+;/入队qr=p-rchild; coutendl; void main() bitree *t; t=create();/建立二叉连
7、表lorder(t);按层次遍历二叉树c -C: EaoiAent s and EEttimwwAd-iniMt rat or1桌面DEbuEtTcF L cxc，:回 Iahc,iil国层次遍历二叉树的结果对a h c e iPress any key to continue将一棵二叉树的所有左右子树进行交换#includetypedef char elemtype;struct bitreeelemtype data;bitree *lchild,*rchild;bitree *create()/ 建立二叉树bitree *root,*s,*q100;int front=1,rear=0;
8、char ch;root=NULL;cout请输入结点值，(,为虚结点，#结束)ch;while(ch!=#)s=NULL;if(ch!=,)s=new bitree;s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;qrear=s;/ 进队if(rear=1)root=s;elseif(s!=NULL)&(qfront!=NULL)if(rear%2=0)qfront-lchild=s;elseqfront-rchild=s;if(rear%2=1) front+; 出队cinch;return root;void preorder(bitree *ro
9、ot)先序遍历bitree *p;p=root;if (p!=NULL)coutdatalchild);preorder(p-rchild);void inorder(bitree *root)中序遍历bitree *p;p=root;if(p!=NULL)inorder(p-lchild);coutdatarchild);void postorder(bitree *root)后序遍历bitree *p;p=root;if(p!=NULL)postorder(p-lchild);postorder(p-rchild);coutdatalchild);leftToright(root-rchi
10、ld);bitree *t=root-lchild;root-lchild=root-rchild;root-rchild=t;void main()bitree *root;root=create();/ 建立二叉树coutendlendl 左右子树交换前的遍历结果endl;cout先序遍历的结果endl;preorder(root);coutendl;cout中序遍历的结果endl;inorder(root);coutendl;cout后序遍历的结果endl;postorder(root);coutendl;leftToright(root);coutendlendl 左右子树交换后的遍历结果endl;cout先序遍历的结果endl;preorder(root);coutendl;cout中序遍历的结果endl;inorder(root);coutendl;cout后序遍历的结果endl;postorder(root);coutendl;)实验小结
