二叉树及其运算

1、云南大学数学与统计学实验教学中心 yv. /树作为一种非线性结构在软件设计中是应用及为广泛的数据结构，而对树的基本操作的基础 又集中于遍历操作上，本实习在课堂讨论的三种遍历方法的基础上，要求同学自行设计不同的遍 历方法并是实现，此外，还要求实现二叉树的一些其它运算。实验报告 yv. /树作为一种非线性结构在软件设计中是应用及为广泛的数据结构，而对树的基本操作的基础 又集中于遍历操作上，本实习在课堂讨论的三种遍历方法的基础上，要求同学自行设计不同的遍 历方法并是实现，此外，还要求实现二叉树的一些其它运算。课程名称：数据结构与算法学期：2011-2012学年第二学期成绩：指导教师：学生姓名：学生学

2、号：上亠实验名称：一叉树的建立及其基本运算的实现实验要求：必做实验学时：8学时声实验编号：5实验日期：第9-12周完成日期：2010-6-9学院：数学与统计学院专业:信息与计算科学年级：4 2010级N一、实验目的二、实验内容1、以二叉链表作为二叉树的存贮结构，以交互方式非递归的创建一棵给定的二叉树。2、根据所给定的二叉链表表示的二叉树，分层打印这棵二叉数上的各结点。 要求每层先打印层号，然后再从左到右打印该层中各结点的值。3以树状形式打印这棵二叉树。例：如下的树树状打印的结果为B 尖A eD EDFB4、用非递归方式，后序遍历一棵给定的二叉树，并用上述建立的二叉树为例，打印出其后 序遍历的结

3、果。三、实验环境Windows XP程序设计语言C四、实验过程1.实验要求：（1丿每一小问题的程序设计以一个C的函数对应，若要增加问题要求，只要增加函数即可。 算法要考虑通用性，对给定的不同输入可以创建不同的二叉树，并进行相应有运算。（2）二叉链表的类型定义采用课堂所用的。 测试数据：对如下给定的二叉树进行测试：F7F7实现提示：（1）实验内容的 1，2 两题的求解思路是类似的，均可采用分层遍历树的思想来实现。 实现算法时应引入一个指针队列以记录已建立或已遍历过的结点。对 2，考虑到 分层打印，可以在队列中加入空指针 NULL 作为层次的间隔。（2）对实验内容 3 可在课堂讲的 6 种遍历方法

4、中省略的 3 种中考虑。附加要求:、求出给定给定二叉树中结点的个数并输出。求出给定给定二叉树中叶结点的个数并输出。Q.自己设计一个带有创新意义的与树有关的题目，并给出程序解答。2.实验设计的（各）流程图：（以下内容请同学认真填写）3程序设计的关键代码及解释：（注意对程序代码给出必要的注解，保证可读性） #include#include#include#define null 0 typedef struct BiTree char data; struct BiTree *lchild,*rchild;BiTree,*BT;BT CreatBitree(BT Tree, BT Q)int fr

5、ont=0,rear=0; char ch1,ch2; BT p,q;printf(若节点为空请用代替n); printf(请输入根节点：”)；ch1=getchar(); p=(BiTree *)malloc(sizeof(BiTree);p-data =ch1; Tree=p;Qrear=Tree; rear+; while(front != rear) q=Qfront; front+;printf(请输入%c的左孩子chi和右孩子ch2 :,q-data); getchar();ch1=getchar(); ch2=getchar(); if(chi !=)p=(BiTree *)ma

6、lloc(sizeof(BiTree); p-data =ch1; q-lchild=p; Qrear+=p;else q-lchild=null; if(ch2 !=) p=(BiTree *)malloc(sizeof(BiTree); p-data =ch2; q-rchild=p; Qrear+=p;else q-rchild=null;return Tree;void LevelTravers(BT Tree, BT Q)BT q;int front=0,rear=0,i=0;Qrear+=null;Qrear+=Tree;printf(nnn);while (front != re

7、ar)q=Qfront+; if(q!=null) printf(%2c,q-data); if(q-lchild != null)Qrear+=q-lchild; if(q-rchild != null)Qrear+=q-rchild; elseQrear+=null;if(q=null&Qfront=null) return; printf(nLEVEL %2d:,+i);printf(nvoid NodeCounter(BT Tree,BT Q)int front=0,rear=0;BT q;Qrear+=Tree;while(front!=rear)q=Qfront+;if(q-lch

8、ild !=null)Qrear+=q-lchild;if(q-rchild !=null)Qrear+=q-rchild; putchar(n); printf(nprintf(树的节点为：)；for(front=0;front!=rear;front+)q=Qfront; printf(%2c,q-data);printf(n 树的节点总数为 %dn,rear);void LevesCounter(BT Tree,BT Q)int front=0,rear=0;int i=0;BT q;Qrear+=Tree; while(front!=rear) q=Qfront+; if(q-lchi

9、ld !=null) Qrear+=q-lchild; if(q-rchild !=null) Qrear+=q-rchild;printf(nprintf(树的叶子为：”)； for(front=0;front!=rear;front+) q=Qfront;if(q-lchild =null&q-rchild =null) printf(%2c,q-data); i+;nn);nn);1/f1/fprintf(n 叶子节点总数为 %dn,i);printf(nnn);void PrintTree(BT Tree, int i)int j;if(Tree-rchild)PrintTree(Tr

10、ee-rchild,i+1); for(j=1;jdata); if(Tree-lchild)PrintTree(Tree-lchild,i+1);void PostOrderTraverse(BT Tree, BT Q) int top =0;int tag20; BT q; q = Tree;printf(nprintf(后序非递归遍历的结果为：”); dowhile (q != null)top+;Qtop=q;tagtop =0; q=q-lchild;if(top0) q=Qtop; if(tagtop=1) i printf(%2c,q-data); top-;q=null; el

11、se tagtop=1; q=q-rchild;while(q !=null II top !=0); printf(n); main()BT root=NULL,Q50; int i=1;root=CreatBitree(root, Q); LevelTravers(root,Q);putchar(n); NodeCounter(root,Q); LevesCounter(root,Q); PrintTree(root,i);PostOrderTraverse(root,Q);4.实验（程序运行）结果的粘贴：（必需是你的程序运行结果截图）五、实验总结1遇到的问题及分析：（请结合你的试验过程认

12、真总结）对树的操作，递归遍历很容易理解，把递归转化成非递归，我感觉还是有一些难度，拿遍历来说，递 归的时候只用考虑根，左孩和右孩，非递归的时候往往要借助队列跟栈，而且要站在整体的角度上来考 虑这个问题。2解决方案（列出遇到的问题和解决办法，列出没有解决的问题）：遇到的问题： 解决分层打印没什么思路，只是老师提示要用队列解决办法： 后来看了精品那本书，跟同学讨论，并在纸上模拟运行，通过了再上级调试的 没有解决的问题： 1）附加要求里面要求自己设计创新的题目，我跟同学思考来用模拟小球掉落的正态 分布，我们用系统产生的随机数的奇偶性决定往左还是往右，不过模拟的结果不太理想，小球总是会掉落在两端，所以就没有在实验报告上给出。3体会和收获。根据老师给的思路，实现起