《数据结构与算法实验报告-二叉树》由会员分享，可在线阅读，更多相关《数据结构与算法实验报告-二叉树（13页珍藏版）》请在金锄头文库上搜索。
1、沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 二叉树 班 级 软本 111 学 号 2011417104 姓 名 吴月芬 地 点 F 座 606 指导教师 姜柳 祝世东 实 验 日 期 : 2012 年 10 月 25 日 1一、实验目的1掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2掌握用指针类型描述、访问和处理二叉树的运算。二、实验环境Turbo C 或是 Visual C+三、实验内容与要求1输入字符序列，建立二叉链表。2按先序、中序和后序遍历二叉树（递归算法） 。3按某种形式输出整棵二叉树。4求二叉树的高度。5求二叉树的叶结点个数。
2、6交换二叉树的左右子树。7借助队列实现二叉树的层次遍历。8在主函数中设计一个简单的菜单，调试上述算法，要求 1-3 必做，4-7 为选做。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质 5 来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素） 。图 4.1 所示二叉树的输入数据顺序应该是：（1,a） ，（2,b） ， （3,c ） ， （4,d） ， （ 6,e） ， （7,f） ， （9,g） ， （13,h ） 。另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似
3、。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。这时，图 4.1 所示二叉树的输入数据顺序应该是：abd#g#ce#h#f# 。若当前数据不为“#” ，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。2四、实验过程及结果分析（一）二叉树1.二叉树的综合程序源代码如下所示：#include #include #define NULL 0struct bitreechar data;struct bitree * lchild, * rchild;struct bitree * createbitree_1(struct bitre
4、e * t)int ch;scanf(%d,&ch);if(ch=0)t=NULL;elset-data=ch;t-lchild=(struct bitree *)malloc(sizeof(struct bitree);t-lchild=createbitree_1(t-lchild);t-rchild=(struct bitree *)malloc(sizeof(struct bitree);t-rchild=createbitree_1(t-rchild);return t;struct bitree * createbitree_2(struct bitree * t)int ch;3
5、scanf(%d,&ch);if(ch=0)t=NULL;elset-lchild=(struct bitree *)malloc(sizeof(struct bitree);t-lchild=createbitree_2(t-lchild);t-data=ch;t-rchild=(struct bitree *)malloc(sizeof(struct bitree);t-rchild=createbitree_2(t-rchild);return t;void preorder_1(struct bitree * T)if(T!=NULL)printf(%dtt,T-data);preor
6、der_1(T-lchild);preorder_1(T-rchild);void preorder_yezi(struct bitree * T)if(T!=NULL)if(T-lchild=NULL&T-rchild=NULL)/只输出叶子节点printf(%dtt,T-data);preorder_1(T-lchild);preorder_1(T-rchild);4void inorder_1(struct bitree * H)if(H)inorder_1(H-lchild); printf(%dtt,H-data);inorder_1(H-rchild);void preorder_
7、2 (struct bitree * p)struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;printf(%dtt,p-data);p=p-lchild;if(top!=-1)p=stop;top-;p=p-rchild;void preorder_yezi_2 (struct bitree * p)5struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;if(p-lchild=NUL
8、L & p-rchild=NULL)/只输出叶子节点printf(%dtt,p-data);p=p-lchild;if(top!=-1)p=stop;top-;p=p-rchild;void inorder_2 (struct bitree * p)struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;p=p-lchild;if(top!=-1)6p=stop;top-;printf(%dtt,p-data);p=p-rchild;void menu_1()printf(nt* * * *
9、* * 菜 单 * * * * * * *n);printf(t1.树的建立n);printf(t2.树的遍历n);printf(t0.退 出n);void menu_2(int n)if(n=1)printf(nt* * * * * * 菜 单 * * * * * * *n);printf(nt1.树的递归的先序建立n);printf(nt2.树的递归的中序建立n);printf(nt3.树的非递归的先序建立n);printf(nt4.树的非递归的中序建立n);if(n=2)printf(nt* * * * * * 菜 单 * * * * * * *n);printf(nt1.树的递归的先序
10、遍历n);printf(nt2.树的递归的中序遍历n);printf(nt3.树的非递归的先序遍历n);printf(nt4.树的非递归的中序遍历n);printf(nt5.树的递归的先序遍历叶子节点n);7printf(nt6.树的非递归的先序遍历叶子节点n);void main()struct bitree * H;int n,m;H=(struct bitree *)malloc(sizeof(struct bitree);domenu_1();scanf(%d,&n);if(n2|n0)printf(ntt 您的输入有误！);else if(n!=0)menu_2(n);scanf(%
11、d,&m);if(n=1)if(m=1)H=createbitree_1(H);if(m=2)H=createbitree_2(H);if(n=2)if(m=1)preorder_1(H);if(m=2)inorder_1(H);if(m=3)preorder_2(H);if(m=4)inorder_2(H);8if(m=5)preorder_yezi(H);if(m=6)preorder_yezi_2(H);while(n!=0);2.运行过程二叉树递归的先序建立过程如图 1.1 所示。图 1.1 先序建立二叉树二叉树的递归的先序遍历如图 1.2 所示。9图 1.2 递归先序遍历二叉树的递归的中序遍历如图 1.3 所示。图 1.3 递归的中序遍历二叉树的非递归的先序遍历如图 1.4 所示。10图 1.4 非递归的先序遍历二叉树的非递归的中序遍历如图 1.5 所示。图 1.5 非递归的中序遍历二叉树的递归的先序遍历叶子节点如图 1.6 所示。11图 1.6 递归的先序遍历叶子节点二叉树的非递归的先序遍历叶子节点如图 1.7 所示。图 1.7 非递归的先序遍历叶子节点结束程序操作如图 1.8 所示。图 1.8 结束程序12五、成绩评定优 良 中 及格 不及格出 勤内 容格 式创 新效 果总 评指导教师： 年 月 日
