数据结构课程设计定稿---树与二叉树的转换实现

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评

2、成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1 课程设计目标11.2 课程设计基本要求11.3 课程设计内容12 分析与设计22.1 题目分析22.3 算法描述72.4 程序流程图83 程序清单104 测试144.1 测试数据144.2 测试结果分析145 总结15参考文献161 课程设计目标1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据

3、实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计基本要求严格按照题意要求，独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同

4、意的前提下进行。学生应制定设计工作计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设计报告，做好设计总结。1.3 课程设计内容设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目分析树是一种重要的非线性数据结构，掌握二叉树的两种基本的存储结构，及各种操作的算法实现（建立、遍历）以及应用是非常重要的。树结构的特点是：它的每一个结点都

5、可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。二叉树的特点是：每个结点至多有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能颠倒。（1）树转换成二叉树如果F=T1,T2,.,Tm是树，则可按如下规则转换成一棵二叉树B=（root，LB，RB）。若F为空，即m=0，则b树为空树； 若F非空，即m!=0，则B的根root即为森林中第一棵树的根root（T1）；B的左子树LB是从T1中根结点的子树F1= T11,T22,.,T1m1 转换而成的二叉树；其右子树RB是从树F=T1,T2,.,Tm转换而成的二叉树。（2）二叉树转换成树如果B=（r

6、oot，LB，RB）F=T1,T2,.,Tm是一棵二叉树，则可按如下规则转换成树F=T1,T2,.,Tm。若B为空，则F为空。若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树的B的根root；T1中根结点的子树F1是由B的左子树LB转换而成的树；F中除t1之外的其余树组成的森林F=T1,T2,.,Tm是由B的右子树RB转换而成的森林。2.2 存储结构设计1树的存储结构有很多种形式。下面介绍常用的三种常用的存储结构：（1）双亲数组表示法这种存储结构是利用每个结点（根结点除外）只有唯一双亲的特点，用一维数组来存储一棵一般的树。，如图2.1即为一棵树及其双亲表示。在这种结构中，寻找一个结点

7、双亲的时候，只要访问它的parent域，即可得到它的双亲的存储位置。但是，要寻找一个结点的孩子时，则需遍历整个数组。ABCDFJIHGE 图2.1 双亲表示法（2）结点定长的孩子链表表示法如下图2.2所示，一个三叉树，可以用三叉链表储存。其结构特点是：一个数据域和三个指针域，指针域用于指向节点的各个孩子节点。 图2.2 孩子链表表示法 （3）孩子兄弟二叉链表表示法孩子兄弟链表作为存储结构，其特点是：一个数据域和两个指针域。其中一个指针指向它的第一个孩子节点，另一个指向它的兄弟结点。如图2.3所示： 图2.3兄弟二叉链表表示法2. 二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现

8、是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储结构只适用于存满二叉树和完全二叉树。图2.4顺序存储结构Lchild data rchidLchild data parent rchild设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方便找到双亲，则在结点结构中增加一个指向其双亲结点的指针域。利用这种结点结构所得二叉树的存储结构分别称为二叉链表和三叉

9、链表。图2.5 链式储存结构实现树与二叉树的转换，写入程序需要引入头文件，头文件是程序顺利实现必不可少的程序代码，该程序的头文件如下：#include #include #include #define MAX_TREE_SIZE 100 利用双亲的位置域，树的孩子兄弟表示结点结构定义 来表示树，定义根的位置和结点个数。 typedef struct int data; int parent; /双亲位置域 PTNode; /*双亲表示法树结构*/ typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数 PTree; /*树

10、的孩子兄弟表示结点结构定义*/ typedef struct node int data; struct node *firstchild; struct node *rightsib; BTNode,*BTree;2.3 算法描述创建一个树的结构体，从键盘输入数据存入数组；创建一个二叉树的结构体，把树队列中出来的数存入数组中。CTreeNode *CreateSTree()，int addQueueBTree(QueueBTree *&q,BTreeNode *btroot)。遍历树的递归算法，若树为空，则空操作，否则（1）访问根节点；（2）依次遍历孩子节点；（3）遍历结束；void pre

11、orderTree(CTreeNode *ctroot初始化树队列，树队列元素入队、出队；void initQueueCTree(QueueCTree *&q)，int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot)，CTreeNode *delQueueCTree(QueueCTree *&q)。初始化二叉树队列，初始化二叉树元素入队、出队；void initQueueBTree(QueueBTree *&q)，int addQueueBTree(QueueBTree *&q,BTreeNode *btroot)，BTreeNode *delQ

12、ueueBTree(QueueBTree *&q)。树与二叉树的转化算法，转换时结点的第一个孩子变为它的左孩子，兄弟结点变为它的右孩子；void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)。将树转换为二叉树的方法：（1）将树的兄弟之间加上一条线。（2）对于每个结点，除了其左孩子以外，去除与其余孩子之间的关系。（3）以树的根节点为轴心，将整棵树顺时针转45度角。 图2.6 树转换二叉树实现方法2.4 程序流程图程序流程图是一个程序算法的简单体现，程序需要实现的功能都能显示出来。图为树转换为二叉树的程序流程示意图。主菜单开始 退出程序后序遍历

13、（递归）前序遍历（递归）双亲法建树层次遍历前序遍历（非递归）后序遍历（非递归）按照格式输出各个结点 输出树的结点情况输出遍历结果 副菜单 退出程序 图2.7 树转换二叉树流程图2.5 测试程序说明该程序是为将数据结构中的树转换为二叉树结构，实现数据在结构转换中的交替传递功能。运行程序，依次输入树的总结点数量，根节点，第二个结点及其父亲结点，第三个结点及其父亲结点，直到输入所有结点。计算机会根据程序代码自动分配存储空间，将数据分配到树或二叉树结点的相应位置，最后在屏幕上显示出来。将程序运行结果和预期结果相比较，分析程序漏洞、错误，发现问题所在，致力改良程序。使程序更加合理，更加简便。3 程序清单

14、#include #include #include #define MAX_TREE_SIZE 100 typedef struct int data; int parent; /双亲位置域 PTNode; /*双亲表示法树结构*/ typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数 PTree; /*树的孩子兄弟表示结点结构定义*/ typedef struct node int data; struct node *firstchild; struct node *rightsib; BTNode,*BTree;

15、/初始化树(双亲表示法) void init_ptree(PTree *tree) tree-count=-1; /初始化树结点(孩子兄弟表示法) BTNode GetTreeNode(int x) BTNode t; t.data=x; t.firstchild=t.rightsib=NULL; return t; /*一般树转换成二叉树*/ BTNode *change(PTree T) int i,j=0; BTNode pMAX_TREE_SIZE; BTNode *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode); is=(BT

16、Node *)malloc(sizeof(BTNode); ir=(BTNode *)malloc(sizeof(BTNode); Tree=(BTNode *)malloc(sizeof(BTNode); for(i=0;iT.count;i+) pi=GetTreeNode(T.nodei.data); for(i=1;idata) j+; is=&pj; if(!(is-firstchild) is-firstchild=ip; ir=ip; else ir-rightsib=ip; ir=ip; Tree=&p0; return Tree; /*主菜单*/ void Menu() pr

17、intf(=主菜单=n); printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入0-退出程序*n); printf(=n); printf(请输入执行的指令:); /*副菜单*/ void Menu2() printf(*副菜单*n); printf(*9-返回主菜单继续操作*n); printf(*0-退出程序*n); /*主函数*/ void main() int i=0,c1,c2; PTree T; BTNode *Tree; init_ptree(&T); loop: Menu(); scanf(%d,&c1); switch(c1) case 1: prin

18、tf(建立一般树,依次输入各个结点情况:n); T=CreatTree(T); Tree=change(T); printf(一般树转换成二叉树后的情况:n); getchar(); break; case 0: exit(1); break; Menu2(); scanf(%d,&c2); if(c2=9) goto loop; else if(c2=0) exit(1); 4 测试4.1 测试数据将树设为5个结点，其结点数据分别为1、2、3、4、-1,。其树结构如图4.1，测试结果如图4.2。1 32-14 图4.1 测试数据4.2 测试结果分析一般树转换为二叉树后：图4.2 实验结果5

19、总结本次课程设计任务主要是树与二叉树的转换，这期间学会了树的建立，二叉树的性质，能熟练掌握树与二叉树的转换。通过这次的学习，我发现不能做到知识的连贯，导致设计程序的过程中有些地方达不到理想的要求，只能不熟练地编完程序，有时程序不能编译出来。这次的上机练习让我发现其中的不足，在同学和老师的帮助下，完成本次的任务，使我弥补了知识的空白，同时明白只有动手实践，才有可能完成想要的结果，只有不断练习，才能做一个合格的程序员。参考文献1 严蔚敏.数据结构（C语言版）.清华大学出版社.20022 王路群.数据结构-C语言描述.中国水利水电出版社.20073 王国钧.数据结构实验教程（C语言版）. 清华大学出

20、版社.20094 严蔚敏,吴伟民编.数据结构题集.清华大学出版社.20025 苏仕华.数据结构课程设计.清华大学出版社.20026 徐孝凯.数据结构简明教程.清华大学出版社.1995#include #include #include #define MAX_TREE_SIZE 100 typedef struct int data; int parent; /双亲位置域 PTNode; /*双亲表示法树结构*/ typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数 PTree; /*树的孩子兄弟表示结点结构定义*/ ty

21、pedef struct node int data; struct node *firstchild; struct node *rightsib; BTNode,*BTree; /初始化树(双亲表示法) void init_ptree(PTree *tree) tree-count=-1; /初始化树结点(孩子兄弟表示法) BTNode GetTreeNode(int x) BTNode t; t.data=x; t.firstchild=t.rightsib=NULL; return t; /树的前序遍历(递归) void preorder(BTNode *T) if(T!=NULL)

22、printf(%d ,T-data); preorder(T-firstchild); preorder(T-rightsib); /树的前序遍历(非递归) void preorder2(PTree T) int i; for(i=0;ifirstchild); printf(%d ,T-data); inoeder(T-rightsib); /树后序遍历(非递归) void inoeder2(PTree T) int i; for(i=T.count-1;i=0;i-) printf(%d ,T.nodei); /层次遍历 void level(PTree T) int i; for(i=0

23、;irightsib,level+1); for(i=1;idata); PrintBTree(root-firstchild,level+1); /输出树 void print_ptree(PTree tree) int i; printf( 序号 结点 双亲n); for(i=0;i=tree.count;i+) printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent); printf(n); /*用双亲表示法创建树*/ PTree CreatTree(PTree T) int i=1; int fa,ch; PTNode p; for(i

24、=1;ch!=-1;i+) printf(输入第%d结点:n,i); scanf(%d,%d,&fa,&ch); printf(n); p.data=ch; p.parent=fa; T.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent; printf(n); printf(创建的树具体情况如下:n); print_ptree(T); return T; /*一般树转换成二叉树*/ BTNode *change(PTree T) int i,j=0; BTNode pMAX_TREE_SIZE; BTNod

25、e *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode); is=(BTNode *)malloc(sizeof(BTNode); ir=(BTNode *)malloc(sizeof(BTNode); Tree=(BTNode *)malloc(sizeof(BTNode); for(i=0;iT.count;i+) pi=GetTreeNode(T.nodei.data); for(i=1;idata) j+; is=&pj; if(!(is-firstchild) is-firstchild=ip; ir=ip; else ir-rightsib=ip; ir=ip; Tree=&p0; return Tree; /*主菜单*/ void Menu() printf(=主菜单=n); printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(