数据结构与算法实验报告-二叉树.doc

沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 二叉树 班 级 软本111 学 号 2011417104 姓 名 吴月芬 地 点 F座606 指导教师 姜柳 祝世东 实 验 日 期 : 2012年10月25日 一、实验目的1 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2 掌握用指针类型描述、访问和处理二叉树的运算。二、实验环境Turbo C或是Visual C+三、实验内容与要求1 输入字符序列，建立二叉链表。2 按先序、中序和后序遍历二叉树（递归算法）。3 按某种形式输出整棵二叉树。4 求二叉树的高度。5 求二叉树的叶结点个数。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）。另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。这时，图4.1所示二叉树的输入数据顺序应该是：abd#g#ce#h#f#。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。 四、实验过程及结果分析（一）二叉树1.二叉树的综合程序源代码如下所示：#include #include #define NULL 0struct bitree char data; struct bitree * lchild, * rchild;struct bitree * createbitree_1(struct bitree * 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;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); preorder_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); void inorder_1(struct bitree * H) if(H) inorder_1(H-lchild); printf(%dtt,H-data); inorder_1(H-rchild);void preorder_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) struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;if(p-lchild=NULL & 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)p=stop;top-;printf(%dtt,p-data);p=p-rchild;void menu_1()printf(nt* * * * * * 菜 单 * * * * * * *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.树的递归的先序遍历n);printf(nt2.树的递归的中序遍历n);printf(nt3.树的非递归的先序遍历n);printf(nt4.树的非递归的中序遍历n); printf(nt5.树的递归的先序遍历叶子节点n);printf(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(%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);if(m=5)preorder_yezi(H);if(m=6)preorder_yezi_2(H);while(n!=0);2.运行过程二叉树递归的先序建立过程如图1.1所示。图1.1先序建立二叉树二叉树的递归的先序遍历如图1.2所示。图1.2递归先序遍历二叉树的递归的中序遍历如图1.3所示。图1.3递归的中序遍历二叉树的非递归的先序遍历如图1.4所示。图1.4非递归的先序遍历二叉树