《二叉树的基本操作》课程设计.doc

《《二叉树的基本操作》课程设计.doc》由会员分享，可在线阅读，更多相关《《二叉树的基本操作》课程设计.doc（13页珍藏版）》请在三一办公上搜索。

1、课程设计二叉树的基本操作课程设计论文学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机 指导教师 教师职称 讲师 塔里木大学教务处制目录前言1正文12.1设计目的及意义12.2问题描述12.3 数据结构分析22.4算法设计及分析22.5算法测试及分析6总结7参考文献8附录9前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。通过一学期的学习，对数据结构这门学科有了了解。为了检验这学期所学的知识，不光要通过考试，还要对其中的知识点进行深一步的了解探讨和研究。所以做这个课程设计对知识点可以深度的研究。当数据的逻辑结构确定以

2、后，数据在物理空间中的存储方式，称为数据的存储结构。同一逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是二叉树。二叉树是树形结构的一个重要的类型，二叉树是n(n0)个结点的有限集，它或者是空集(n0),或者由一个根结点以及两棵互不相交的，分别称为左子树和右子树的二叉树组成。二叉树的顺序存储结构是把二叉树所有结点，按照一定的次序排序，存储到一片连续的存储单元中。但二叉树的顺序存储结构浪费空间并且插入、删除不方便。二叉树的链式存储每个结点至少包含三个域：数据域、左指针域、右指针域，不浪费空间。二叉树的存储结构和算法比较简单，特

3、别适合计算机处理，即使一般形式的树也可简单的转换为二叉树。现实中经常用到二叉树，因此本课程设计主要实现了二叉树的建立、三种遍历，计算二叉数的树深、统计叶子结点的个数等功能。正文2.1设计目的及意义课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。2.2问题描述二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树型结构组织的若干结点对应于一个线性序列。二叉树的遍历策略有四种先序遍历、中序遍历、后序遍历和层次遍历。(1)按先序次序输入二叉树中结点的值,构造二叉链表表示

4、的二叉树t；(2)对二叉树t作先序、中序、后序遍历的递归算法,输出结果；(3)计算二叉树t的深度,输出结果；(4)计算二叉树t的叶子结点个数2.3 数据结构分析本程序分为：7大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、求叶子结点的个数计算、中序遍历、后序遍历、深度、主函数。1、二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采用了每个结点中设置三个域，data：即值域，*lchild：左指针域和rchild：右指针域。2、二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。3、二叉

5、树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。4、二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。5、求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0。否则，就先别求出左右子树的深度并进行比较，取较大的+1就为二叉树的深度。6、二叉树的求叶子结点的个数计算；先分别求得左右子树中各叶子结点个数，再计算出两者之和即为二叉树的叶子结点数。7、主函数。主函数中分别调用各函数。2.4算法设计及分析算法流程图Main()CreateBiTree ()构造二叉树PreOrderTraverse()NRPre

6、Order（）分别输出递归与非递归先序遍历结果InOrderTrave（）NRInOrder（）分别输出中序递归与非递归遍历结果PostOrderTravesr()NRPostOrder（）分别输出递归与非递归的后序遍历结果求结点的中序前驱后继中序InOrderTraver（） 1、存储结构的建立由递归函数实现具体函数为：typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);

7、if(ch=#) t=NULL;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow);t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t;在创建的二叉树中，左右孩子都为字符型。char的作用是输入n个任意的字符，而且在输入n个字符后，必须输入n+1个#，才能得到本程序所有能够实现的功能。t=Null是将二叉树置空。if(!(t=(bitnode *)malloc(sizeof(bitnode)，采用动态申请新结点的方

8、式，不仅实现起来方便，而且还节省大量的存储空间。t-data=ch;值域t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);将二叉树中的每一个结点设置为：值域，左指针域，右指针。这一小段程序实现了二叉树的置空，二叉树的建立，二叉树的存储。2、前序遍历：先访问根结点，再访问左子树，最后访问右子树。具体函数为：void preordertraverse(bitree t)if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild);

9、3、中序遍历：先访问左子树，再访问根结点，最后访问右子树。具体函数为：void inordertraverse(bitree t) if (t) inordertraverse(t-lchild);printf(%c,t-data);inordertraverse(t-rchild); 4、后序遍历：先访问左子树，再访问右子树，最后访问根结点。具体函数为：void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); 5、求二叉树的深

10、度：先定义三个整形变量m,n.如果树为空，则height=0；否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。具体函数为：int height(bitree t)int m,n;if(t=NULL) return 0;else m=height(t-lchild);n=height(t-rchild);return (mn)?m+1:n+1;6、求叶子结点的个数：用leafcount变量表示叶子结点的总个数，用leafcount(t-lchild)、leafcount(t-rchild)分别表示访问的左右子树中叶子结点的个数。当树为空是此时讨论叶子结点个数

11、无意义；当树非空时分为：一、左右子数都不存在时，即叶子结点的个数为1；二、左右子树存在，就用分别访问出左右子树中叶子结点的个数，两者相加就为二叉树叶子结点的个数。具体函数为：int leafcount(bitree t) if(!t) return 0; /空数无叶子 else if(!t-lchild&!t-rchild) return 1; else return leafcount(t-lchild)+leafcount(t-rchild);7、主函数：包括：二叉树的数据结构bitree t、函数createbitree、height、leafcount、前序遍历preordertrav

12、erse、中序遍历inordertraverse、后序遍历postordertraverse。具体函数为：void main()bitree t;int w,v;printf(请输入建树字符序列:);t=createbitree(t);printf(先续遍历的结果是:);preordertraverse(t);printf(n);printf(中续遍历的结果是:);inordertraverse(t);printf(n);printf(后续遍历的结果是:);postordertraverse(t);printf(n);printf(二叉树的深度是:);w=height(t);printf(%d

13、n,w);printf(二叉树的叶子结点的数目为:);v=leafcount(t);printf(%d,v);printf(n);2.5算法测试及分析建立一个二叉树 遍历二叉树结点求二叉树所有结点数总结通过对二叉树的基本操作的学习，熟悉的掌握了二叉树的结构特性，掌握了二叉树的链式存储结构的特点和适用范围，通过二叉树的基本操作实现，思考一般树的基本操作的实现。熟悉掌握各种遍历各种二叉树的策略的递归和非递归算法。在对二叉树基本操作的学习过程中不断对其中的算法思想进行改进和修正，更熟悉的掌握关于二叉树的基本操作. 熟练掌握二叉树的结构特性，了解相应的证明方法。 熟悉二叉树的各种存储结构的特点及适用范

14、围。 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归和非速归算法，了解遍历过程中 栈 的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应

15、掌握 1 至 2 种建立二叉树和树的存储结构的方法。学会编写实现树的各种操作的算法。 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 理解前序序列和中序序列可唯一确定一棵二叉树的道理，理解具有相同的前序序列而中序序列不同的二叉树的数目与序列 12n 按不同顺序进栈和出栈所能得到的排列的数目相等的道理，掌握由前序序列和中序序列建立二叉树的存储结构的方法。参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.第1版.北京；清华大学出版社，2005年；58-64.2 严蔚敏，吴伟民.数据结构题集（C语言版）.第1版.北京；清华大学出版社，2005年；96-105.3 李春葆，章启俊.C+程序设计.

16、第1版.北京；清华大学出版社，2007年；56-31.4 谭浩强.C程序设计（第二版）.第6版.北京；清华大学出版社，2004年；9-15.5 陈一华等编.数据结构-使用C 语言.第一版.北京；电子科技大学出版社，1998年；12-14.6 许卓群数据结构第一版. 北京；高等教育出版社，1989年；14-18.7 严蔚敏，吴伟民数据结构题集（C语言版）第一版. 北京；清华大学出版社，1999；3-10.8 蔡明志数据结构（使用C语言）第二版. 北京；科学出版社，1997年；12-15.9 蔡自经，施伯乐数据结构教程第二版. 上海；复旦大学出版社，1984年，11-14.附录源代码:#inclu

17、de #include #include #define ok 1#define error 0#define overflow -1typedef char telemtype;typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=#) t=NULL;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overfl

18、ow);t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t; void preordertraverse(bitree t) if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild); void inordertraverse(bitree t)if (t) inordertraverse(t-lchild);printf(%c,t-data);inordertraverse(t-rch

19、ild); void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); int height(bitree t)int m,n;if(t=NULL) return 0;else m=height(t-lchild);n=height(t-rchild);return (mn)?m+1:n+1;int leafcount(bitree t)if(!t) return 0; /空数无叶子else if(!t-lchild&!t-rch

20、ild) return 1;else return leafcount(t-lchild)+leafcount(t-rchild); void main()bitree t;int w,v;printf(请输入建树字符序列:);t=createbitree(t);printf(先续遍历的结果是:);preordertraverse(t);printf(n);printf(中续遍历的结果是:);inordertraverse(t);printf(n);printf(后续遍历的结果是:);postordertraverse(t);printf(n);printf(二叉树的深度是:);w=height(t);printf(%dn,w);printf(二叉树的叶子结点的数目为:);v=leafcount(t);printf(%d,v);printf(n);