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

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程所用设施12 分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述32.4 程序流程图63 程序清单74 测试114.1 测试数据114.2 测试结果分析135 总结14参考文献151 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结

2、构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。

3、1.3 课程所用设施PC机、VC6.0语言编辑、编译运行工具、文档编辑软件等2 分析与设计树是以分支关系定义的结构层次，树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织结构都可用树来形象表示；二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.1 题目分析根据树与二叉树转换的相关函数库，实现树与二叉树的转换，最好能借助语言环境实现图形显示功能，一边讲抽象的数据结构以图形的方式显示出来，将复杂的运行环境以动态的方式显示出来。认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。2.2 存储结构设计引入头文件：#include #include #include #define MAX_TREE_SIZE 100一般树的存储结构有以下几种，双亲结点，孩子结点，孩子兄弟结点，本实验运用到的是双亲结点和孩子兄弟结点，具体存储结构如下：typedef stru

4、ctint parent;/双亲位置域PTNode;/双亲表示法树结构typedef structint count;/根的位置和结点个数PTree;/树的孩子兄弟表示结点结构定义树的后序遍历（递归）void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d,T-data);inoeder(T-rightsib );2.3 算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数(递归和非递归两种）,树的层次遍历函数，一般树和二叉树的转换函数。将一棵树转换为二叉树的方法是：（1）树中所有相邻兄弟之间加一条连线。如图2.3.1图2.3.1树的相邻兄弟之间的连线(2)对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线。如图2.3.2图2.3.2树与第一个孩子之间的连线(3)以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。如图2.3.3图2.3.3树的结点的转动 (4)以下为树函数的相关功能函数,用

5、来实现对树的一些基本操作：初始化树结点(孩子兄弟表示法):BTNode GetTreeNode(int x)BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;return t;树的前序遍历(递归):void preorder(BTNode *T)if(T!=NULL)printf(%d,T-data );preorder(T-firstchild );preorder(T-rightsib );水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree (root-rightsib,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.node

6、i.parent);printf(n);2.4 程序流程图程序流程图是程序分析中最基本、最重要的分析技术，它是进行流程程序分析过程中最基本的工具。程序流程图是方法研究改进工作方法的有用工具，不论作业研究过程中运用何种技术，流程程序图总是必经的一步，它是应用最普遍的一种工具。图2.4.1程序流程图3 程序清单#include #include #include #define MAX_TREE_SIZE 100 /树的双亲表示结点结构定义typedef structint data;int parent; /双亲位置域PTNode; /双亲表示法树结构typedef structPTNode nodeMAX_TREE_SIZE;int count; /根的位置和结点个数PTree; /树的孩子兄弟表示结点结构定义typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;void init_ptree(PTree *tree)tree-count =-1; /初始化树结点(

7、孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;return t;/树的前序遍历(递归)void preorder(BTNode *T)if(T!=NULL)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-)printf(%d,T.nodei);/树的后序遍历void inoeder2(PTree T)int i;for(;i=T.count-1;i-)printf(%d,T.nodei);/水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree (root-rightsib,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+)pri

《树与二叉树转换的实现-数据结构算法课程设计》由会员博****1分享，可在线阅读，更多相关《树与二叉树转换的实现-数据结构算法课程设计》请在金锄头文库上搜索。