树与二叉树的转换实现18.docx

《树与二叉树的转换实现18.docx》由会员分享，可在线阅读，更多相关《树与二叉树的转换实现18.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现2014年12月29日2. 3算法描述创立一个树的结构体，从键盘输入数据存入数组；创立一个二叉树的结构 体，把树队列中出来的数存入数组中。CTreeNode *CreateSTree (), int addQueue BTree (QueueBTree *&q, BTreeNode *btroot)。遍历树的递归算法，假设树为空，那么空操作，否那么(1)访问根节点；(2) 依次遍历孩子节点；(3)遍历结束；void preorderTree(CTreeNode *ctroot初始化树队列，树队列元素入队、出队；void initQu

2、eueCTree(QueueCTree *&q), int addQueueCTree(QueueCTree *&q, CTreeNode *ctroot), CTreeNode *delQueueCTree (QueueCTree *&q)。初始化二叉树队列，初始化二叉树元素入队、出 队；void initQueueBTree(QueueBTree *&q), int addQueueBTree(QueueBTree *&q, BTreeNode *btroot), BTreeNode *delQueueBTree(QueueBTree *&q)。树与二叉树的转化算法，转换时结点的第一个孩子

3、变为它的左孩子，兄弟 结点变为它的右孩子；void TreeToBTree (CTreeNode *ctroot, BTreeNode *&btroot)o将树转换为二叉树的方法：(1)将树的兄弟之间加上一条线。(2)对于 每个结点，除了其左孩子以外，去除与其余孩子之间的关系。(3)以树的根节 点为轴心，将整棵树顺时针转45度角。图2.6树转换二叉树实现方法72. 4程序流程图程序流程图是一个程序算法的简单表达，程序需要实现的功能都能显示出来。图为树转换为二叉树的程序流程示意图。.图2.7树转换二叉树流程图2. 5测试程序说明该程序是为将数据结构中的树转换为二叉树结构，实现数据在结构转换中 的

4、交替传递功能。运行程序，依次输入树的总结点数量，根节点，第二个结点及其父亲结点, 第三个结点及其父亲结点，直到输入所有结点。计算机会根据程序代码自动分配存储空间，将数据分配到树或二叉树结点 的相应位置，最后在屏幕上显示出来。将程序运行结果和预期结果相比拟，分析程序漏洞、错误，发现问题所在, 致力改良程序。使程序更加合理，更加简便。3程序清单ttincludc #include ttinclude #define MAX_TREE_SIZE 100typedef struct(int data;int parent;双亲位置域PTNode;/ *双亲表示法树结构*/typedef struct(

5、PTNode nodeMAX_TREE_SIZE;int count;根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node int data;struct node irstchild;struct node *rightsib;BTNode, *BTree;初始化树(双亲表示法)void init_ptree(PTree *tree)(tree-count=-l;)初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)10BTNode t;t.data=x;t.firstchild=t. rightsib=NULL

6、;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= (BTNode *)malloc(sizeof(BTNode);ir= (BTNode *)malloc(sizeof(BTNode);Tree=(BTNode malloc(sizeof(BTNode);for (i=0;iT. count;i+)(pi=GetTreeNode(T. nodei.

7、data);)for (i=l;idata)(j+；is=&pj;if(!(is-firstchild)11is-firstchild=ip;ir=ip;)else(ir-rightsib=ip;ir=ip;)Tree=&pO;return Tree;)/*主菜单*/void Menu() printf (二二二二二二=二二二二二二二主菜单=n)；printf (*输入1以双亲法创立一棵一般树*n);printf (*输入 0退出程序*n);printf (=;printf (请输入执行的指令:);)/*副菜单*/void Menu2 ()(printf (*副菜单*n);printf (*9

8、返回主菜单继续操作*n);printf (*0退出程序*11);)/*主函数*/void main ()12int i=0, cl, c2;PTree T;BTNode *Tree;init_ptree(&T);loop:Menu ();scanf&cl);switch (cl)(case 1:printf (建立一般树,依次输入各个结点情况:n);T=CreatTree(T);Tree=change(T);printf (一般树转换成二叉树后的情况：n);getchar ();break;case 0:exit (1);break;)Menu2 ();scanf&c2);if(c2=9)go

9、to loop;else if(c2=0)exit (1);)134测试4.1测试数据将树设为5个结点，其结点数据分别为1、2、3、4.-l,o其树结构如图4.1, 测试结果如图4. 2。图4.1测试数据4. 2测试结果分析一般树转换为二叉树后:输入第4结点:2,4输入第5结点:一工，一1创立的树具体情况如下:序号 0 1 2 3 4结占*-口 八、1234-1双杀-1 112-1般树转换成二叉树后的情况:i 4泠回主楚单继续操作*图4. 2实验结果145总结本次课程设计任务主要是树与二叉树的转换，这期间学会了树的建立，二叉 树的性质，能熟练掌握树与二叉树的转换。通过这次的学习，我发现不能做到

10、知识的连贯，导致设计程序的过程中有些 地方达不到理想的要求，只能不熟练地编完程序，有时程序不能编译出来。这次的上机练习让我发现其中的缺乏，在同学和老师的帮助下，完本钱次的 任务，使我弥补了知识的空白，同时明白只有动手实践，才有可能完成想要的结 果，只有不断练习，才能做一个合格的程序员。15参考文献1严蔚敏.数据结构（C语言版）.清华大学出版社.20022王路群.数据结构-C语言描述.中国水利水电出版社.20073王国钧.数据结构实验教程（C语言版）.清华大学出版社.20094严蔚敏，吴伟民编.数据结构题集.清华大学出版社.20025苏仕华.数据结构课程设计.清华大学出版社.20026徐孝凯.数

11、据结构简明教程.清华大学出版社.199516题目树与二叉树转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标11.1 课程设计目标11.2 课程设计基本要求11.3 课程设计内容12分析与设计22.1题目分析22. 3算法描述72.4程

12、序流程图83程序清单104测试144.1测试数据144. 2测试结果分析145总结15参考文献161课程设计目标1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教 学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设 计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工 作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利

13、用基本调 试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1. 2课程设计基本要求严格按照题意要求，独立进行设计，不能随意更改。假设确因条件所限，必须 要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作 计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设 计报告，做好设计总结。1.3课程设计内容设计树与二叉树转换的相关函数库，以便在程

14、序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形 方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计2.1 题目分析树是一种重要的非线性数据结构，掌握二叉树的两种基本的存储结构，及各 种操作的算法实现(建立、遍历)以及应用是非常重要的。树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外 的所有结点都有且只有一个直接前趋。二叉树的特点是：每个结点至多有两棵子树(即二叉树中不存在度大于2 的结点)，并且，二叉树的子树有左右之分，其次序

15、不能颠倒。(1) 树转换成二叉树如果F=T1, T2,.，Tm是树，那么可按如下规那么转换成一棵二叉树B= (root, LB, RB) o假设F为空，即m=0,那么b树为空树；假设F非空，即m!=0,那么B的根root即为森林中第一棵树的根root (T1); B的左子树LB是从T1中根结点的子树Fl= T11,T22,转换而成的二 叉树；其右子树RB是从树二T1,T2,.，Tm转换而成的二叉树。(2) 二叉树转换成树如果B= (root, LB, RB) F=T1, T2,.，Tm是一棵二叉树，那么可按如下规 那么转换成树 F=T1,T2,-.,Tmo假设B为空，那么F为空。假设B非空，那

16、么F中第一棵树T1的根ROOT (T1)即为二叉树的B的根root； T1中根结点的子树F1是由B的左子树LB转换而成的树；F中除tl之外的其余 树组成的森林F, =T1, T2,.，Tm是由B的右子树RB转换而成的森林。2. 2存储结构设计.树的存储结构有很多种形式。下面介绍常用的三种常用的存储结构：(1)双亲数组表示法这种存储结构是利用每个结点(根结点除外)只有唯一双亲的特点，用一维 数组来存储一棵一般的树。，如图2.1即为一棵树及其双亲表示。在这种结构中, 寻找一个结点双亲的时候，只要访问它的parent域，即可得到它的双亲的存储 位置。但是，要寻找一个结点的孩子时，那么需遍历整个数组。

17、图2.1 双亲表示法(2)结点定长的孩子链表表示法如下列图2. 2所示，一个三叉树，可以用三叉链表储存。其结构特点是：一个 数据域和三个指针域，指针域用于指向节点的各个孩子节点。图2.2孩子链表表示法(3)孩子一兄弟二叉链表表示法孩子一兄弟链表作为存储结构，其特点是：一个数据域和两个指针域。其中 一个指针指向它的第一个孩子节点，另一个指向它的兄弟结点。如图2. 3所示:图2. 3兄弟二叉链表表示法1 .二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实 现是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点 间的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间

18、。所以顺序存 储结构只适用于存满二叉树和完全二叉树。abcde0000fg123456789 10 11图2. 4顺序存储结构设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可 知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，那么表 示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方 便找到双亲，那么在结点结构中增加一个指向其双亲结点的指针域。利用这种结点 结构所得二叉树的存储结构分别称为二叉链表和三叉链表。图2.5链式储存结构实现树与二叉树的转换，写入程序需要引入头文件，头文件是程序顺利 实现必不可少的程序代码，该程序的头文件如下：incl

19、ude ttinclude ttinclude ttdefine MAX_TREE_SIZE 100利用双亲的位置域，树的孩子兄弟表示结点结构定义来表示树，定义根的 位置和结点个数。typedef struct(int data;int parent;双亲位置域PTNode;/*双亲表示法树结构*/typedef struct!PTNode nodeMAX_TREE_SIZE;int count;根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode, *BTree;