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

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; /定义队列的头指针、尾指针cha

5、r ch; /结点的data域值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) /rear为偶数，s为双亲左孩子qfront-lchild=s;else /rea

6、r为奇数，s为双亲右孩子qfront-rchild=s;if(rear%2=1)front+; /出队cinch;return root;void lorder(bitree *t) /按层次遍历二叉树bitree *q100,*p; /q代表队列int f,r; /f、r类似于队列头指针、尾指针q1=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()b

7、itree *t;t=create(); /建立二叉连表lorder(t); /按层次遍历二叉树将一棵二叉树的所有左右子树进行交换#includetypedef char elemtype;struct bitreeelemtype data;bitree *lchild,*rchild;bitree *create() /建立二叉树bitree *root,*s,*q100;int front=1,rear=0;char ch;root=NULL;cout请输入结点值，（,为虚结点，#结束）ch;while(ch!=#)s=NULL;if(ch!=,)s=new bitree;s-data=

8、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 *root) /先序遍历bitree *p;p=root;if (p!=NULL)coutdatalchild);preorder(p-rchild);void inorder(bitre

9、e *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-rchild);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);cout