(数据结构课程设计)二叉树(12页).doc

《(数据结构课程设计)二叉树(12页).doc》由会员分享，可在线阅读，更多相关《(数据结构课程设计)二叉树(12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-(数据结构课程设计)二叉树-第 11 页甘肃政法学院数据结构课程设计 题 目 二叉树遍历计算机科学 学院 信息管理与信息系统 专业 09 级信息管理与信息系统 班学 号：_200981020116姓 名：_唐占红_指导教师：_金 涛_成 绩：_完成时间：_2010 年 12 月摘 要二叉树是树形结构的一个重要的类型，二叉树是n（n=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的

2、次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。 现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。关键词 二叉树 遍历 深度目 录第一章 数据结构课程设计题目及解析3&1.1 数据结构课程设计题目3 设计题目解析3第二章 程序设计的目的和基本要求3&2.1 程序设计的目的3&2.2 程序设计的基本要求3第三章 程序设计的内容3算法设计的思想3&3.3.程序数据类型4程序模块分析5主要

3、的算法源代码8程序设计的结果14第四章 程序设计的优缺点及遇到问题14程序设计的优缺点14程序设计遇到的问题14第五章 程序设计的总结15心的总结15第六章 参考文献15第一章 数据结构课程设计题目及解析&1.1 数据结构课程设计题目题目：二叉树的建立&1.2 设计题目解析通过这个程序主要掌握三种遍历方案，包括前序遍历、中序遍历、后序遍历，以及怎么求二叉树的高度、总结点数、叶子总个数。并会将理论与现实结合在一起。第二章 程序设计的目的和基本要求&2.1 程序设计的目的掌握二叉树的概念和性质、任意二叉树存储结构和任意二叉树的基本操作，并会求二叉树的高度、二叉树总结点个数、二叉树叶子结点，以及熟练

4、掌握三种遍历，包括前序遍历、中序遍历、后序遍历。&2.2 程序设计的基本要求在设计程序时，一定要简单明了，程序设计的思想要完善，算法要清晰，能给其他读者一目了然的感觉。实现二叉树的建立；前序、中序和后序遍历；高度、总结点数、叶子结点数。第三章 程序设计的内容二叉树的建立基本思想是：依次输入的结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至输入“00”时为止。可设置一个指针类型的数组队列，保存已输入结点的地址。由于是按层次自左至右输入结点的，所以先输入的结点的孩子必定比后输入结点的孩子先进入队列

5、，因此可利用对头指针指向当前必须与其孩子结点必定建立链接的双亲结点，利用队尾指针指向当前的结点，即是当前必须与其双亲建立链接的双亲结点。若队尾指针为偶数，则表示当前输入的结点编号是偶数，队尾指针所指向的结点应作为左孩子与其双亲链接；否则队尾指针所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点或孩子结点为虚结点，则无须链接。若双亲结点与其两个孩子链接完毕，则做出队操作，使队头指针指向下一个等待链接的双亲结点。遍历二叉树是二叉树的一种重要的运算，所谓遍历是指沿某条搜索路径周游二叉树，对数中每个结点访问一次且仅访问一次。二叉树的定义是递归的，所以主要由三种遍历方案：1. 前序遍历二叉树若二叉

6、树非空，则依次进行如下操作：（1） 访问根结点；（2） 前序遍历左子数；（3） 前序遍历右子树。2. 中序遍历二叉树若二叉树非空，则依次进行如下操作：（1） 中序遍历左子树；（2） 访问根结点；（3） 中序遍历右子树。3. 后序遍历二叉树若二叉树非空，则依次进行如下操作：（1） 后序遍历左子树；（2） 后序遍历右子树；（3） 访问根结点。一个结点的子树个数称为该结点的度。一颗树的度是该树中结点的最大度数。度为零的结点称为叶子，二叉树结点的层数是从根开始算起的，树中结点的最大层数称为树的高度或深度。typedef int datatype; /* datatype可以为任何类型，这里假设为int

7、*/# define max 60 /*二叉树可能的最大长度，这里假设为60*/typedef struct node /*结构体*/char data; /*数据域*/struct node *lchild,*rchild; /*左右孩子指针*/bitree;（1） 二叉树的建立 bitree *creat() /*二叉树的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf(请输入要建立的树的下标和数值：);scanf(%d%c,&i,&ch);while(i!=0&ch!=0)s=(bitree *)malloc(sizeof(bitree

8、);s-data=ch;s-lchild=NULL;s-rchild=NULL;Qi=s;if(i=1) root=s;elsej=i/2;if(i%2=0) Qj-lchild=s;else Qj-rchild=s;scanf(%d%c,&i,&ch);return root;（2）二叉树的三种遍历void preorder(bitree *t) /*前序遍历*/if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);void inorder(bitree *t) /*中序遍历*/if(t)inorder(t-lchild);

9、printf(%c,t-data);inorder(t-rchild);void postorder(bitree *t) /*后序遍历*/if(t)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);（3）求二叉树的高度 int high(bitree *t) /*求二叉树的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rchild);return (lr?l:r)+1;（4）求二叉树的总结点数int nodes(bitree *a) /*求总结点数*

10、/int num1,num2;if(a=NULL) return 0;elsenum1=nodes(a-lchild);num2=nodes(a-rchild);return num1+num2+1;（5）求叶子结点数int leafs(bitree *b) /*求叶子结点数*/int n,m;if(b=NULL) return 0;else if(b-lchild=NULL&b-rchild=NULL) return 1;elsen=leafs(b-lchild);m=leafs(b-rchild);return n+m;（6）主函数 main(),功能是给出测试数据值，建立测试数据值的顺序

11、表，调用creat函数、preorder函数、inorder函数、postorder函数high、函数nodes函数、leafs函数实现问题要求。# includestdio.h /*头文件*/# includetypedef int datatype;# define max 60typedef struct node /*结构体*/char data;struct node *lchild,*rchild;bitree;bitree *creat() /*二叉树的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf( 请输入要建立的树的下标和

12、数值：);scanf(%d%c,&i,&ch);while(i!=0&ch!=0)s=(bitree *)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL;s-rchild=NULL;Qi=s;if(i=1) root=s;elsej=i/2;if(i%2=0) Qj-lchild=s;else Qj-rchild=s;scanf(%d%c,&i,&ch);return root;void preorder(bitree *t) /*前序遍历*/if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-r

13、child);void inorder(bitree *t) /*中序遍历*/if(t)inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);void postorder(bitree *t) /*后序遍历*/if(t)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);int high(bitree *t) /*求二叉树的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rchild);return (

14、lr?l:r)+1;int nodes(bitree *a) /*求总结点数*/int num1,num2;if(a=NULL) return 0;elsenum1=nodes(a-lchild);num2=nodes(a-rchild);return num1+num2+1;int leafs(bitree *b) /*求叶子结点数*/int n,m;if(b=NULL) return 0;else if(b-lchild=NULL&b-rchild=NULL) return 1;elsen=leafs(b-lchild);m=leafs(b-rchild);return n+m;void

15、main()int a,j,h,g;bitree *b;b=creat();while(1)printf( 选择 1 前序遍历n 选择 2 中序遍历n选择 3 后序遍历n 选择 4 求高度n 选择 5 求总结点数n 选择 6 求叶子结点个数n 选择 0 退出: );scanf(%d,&a);switch(a)case 1:printf( 该二叉树的前序遍历是：); preorder(b); printf(n); break;case 2:printf( 该二叉树的中序遍历是：); inorder(b); printf(n); break;case 3:printf( 该二叉树的后序遍历是：);

16、 postorder(b); printf(n); break;case 4:printf( 该二叉树的高度j=%dn,j);j=high(b); break;case 5:h=nodes(b); printf( 该二叉树的总结点数h=%dn,h); break;case 0:exit(0);第四章 程序设计的优缺点及遇到问题这个程序设计的算法清晰，思想明了，能清楚的实现二叉树的建立、三种遍历、高度、总结点数以及叶子结点数的运算。但是这个程序在设计过程时有些麻烦，而且三种遍历的算法自己不是太清楚，不能很清楚的描述三种遍历。在设计时主要三种遍历不是很清楚，所以还是很模糊，刚开始不能很准确的把三种

17、遍历的算法写出来，所以在这个问题上还要继续思考。在写菜单时不是很了解，后来在同学的帮助下把程序的菜单写出来了，自己还要努力学习写菜单。第五章 程序设计的总结 通过这次做数据结构的课程设计，我发现真正掌握一个知识点并不只是要从书上看，还要查一些相关资料，并且理论与现实结合在一起。这次做的是关于二叉树的课程设计，刚开始以为并不是很难，但真正做的时候才发现这一节的知识点很多，也有一些比较混淆的难点，比如二叉树的遍历就有三种情况，包括前序遍历、中序遍历、后序遍历。当然这次在做课程设计的时候遇到一些问题，不过得到大家的帮助，问题得到解决，也成功的完成了本次的课程设计。第六章 参考文献 【1】 严蔚敏，吴伟明.数据结构M.2版. 清华大学出版社,1992。 【2】 唐策善，数据结构用C语言描述.高等教育出版社。【3】 殷人昆.数据结构.北京：清华大学出版社，2001。K【4】 严蔚敏，吴伟民，数据结构习题集（C语言版）.北京清华大学出版社，1999。