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

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

2、本课程设计，使学生进一步深化掌握C语言的基本知识；掌握数据结构基本方法和设计技巧，初步了解算法分析与设计概念；理解数据结构设计思想，初步具备运用数据结构方法进行程序设计的能力。能熟练应用VC+集成环境进行数据结构相关程序的编写、编译与调试，提高学生对本课程知识综合运用能力。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3课程设计要求根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构知识的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。1.4课程设计基本操作方法1按照系统用户手册及文档规范要求进行操作，养成查阅手册、文档的良好习惯；2对特殊疑难问题采用讨论、协作等方式进行解决，有意识地训练团队合作意识；3课

3、程设计报告应多包含在课程设计过程中出现的错误及解决方法。二、分析与设计树与二叉树的转换，应根据树的存储结构定义，即双亲表示和孩子-兄弟表示，以及二叉树的存储结构定义和遍历定义来进行，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同，根据以上基本可完成程序要求。2.1 题目分析本程序的功能是对二叉树进行递归前序遍历和后序遍历，还有对树的前序和后序遍历以及树与二叉树的转换。本程序要求用户以数值输入，若要实现终端结点，最后以回车键建入数据。本程序的结果将打印出输入树及树转换成二叉树，树的前序和后序遍历以及指定二叉树的前序、中序和后序遍历。2.2 存储结构设计首先进行头文件的设置#include #include #include #define MaxSize 100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：typedef char ElemType;typedef struct bnode/二叉树定义ElemType data;struct bnod

4、e *lchild;struct bnode *rchild; bTNode,bTree;/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMaxSize; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *nextchild;BTNode,*BTree;2.3 算法描述在将树转换为二叉树的过程中，对于每一个结点，仅保留一个子女结点（若存在）的链接指针在结点的firstchild域中，断开其他子女结点的链接指针；同时，把它的所有子女结点通过它们的右兄弟指针nextchild链接起来，在右旋45，即可得到树的对应二叉树表示，将树其转换为二叉树的算法过程如下： 图2- 1 树（1）加线：就是在所有兄弟结点之间加一条连线；图2- 2 加线（2）抹线：就是对树中的每个结点

5、只保留它与左孩子结点之间的连线，删除它与其它孩子结点之间的连线；图2- 3 抹线（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45，使之结构层次分明，如此即可得到对应的二叉树表示。一棵树可转换成唯一的一棵二叉树。图2- 4 旋转2.4 程序流程图程序运行进入菜单选择界面，根据相应的选择标号进行相应的操作，首先可选择选项1进行树的创建，然后可选择选项2或3对树的前序和后序遍历，选择选项4可创建指定二叉树然后可选择子菜单的相应选项对二叉树进行前序、中序和后序遍历，最后可选择0退出程序。退出程序选择1或0输 出 遍 历 结 果输出树的创建情况输出转换后的二叉树开 始菜单输入选项进行操作选择【1】创建树选择【2】树的前序遍历选择【3】树的中序遍历选择【4】树的后序遍历选择【0】退出系统选择【1】前序遍历选择【2】中序遍历选择【3】后序遍历选择1选择0图2- 5 流程图三、程序清单#include #include #include #define MaxSize 100typedef char ElemType;typedef struct bnode/二叉树定义ElemType da

6、ta;struct bnode *lchild;struct bnode *rchild; bTNode,bTree;/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMaxSize; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *nextchild;BTNode,*BTree;void insertBTNode(bTNode *&b,char *str)/由str串创建二叉链bTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while (ch!=0)/str未扫描完时循环 switch(ch) case (:top+;Sttop=p;k=1; brea

7、k;/为左结点case ):top-;break;case ,:k=2; break; /为右结点default:p=(bTNode *)malloc(sizeof(bTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /p指向二叉树的根结点b=p;else /已建立二叉树根结点switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void preOrder(bTNode *T)if(T!=NULL)printf(%c ,T-data);preOrder(T-lchild);preOrder(T-rchild);void zOrder(bTNode *T)if(T!=NULL)preOrder(T-lchild);printf(%c ,T-data);preOrder(T-rchild); void hOrder(bTNode *T)if(T!=NULL)preOrder(T-lchild);preOrder(T-rchild);printf(%c ,T-data);/树的相关操作void init_ptree(PTree *tree) tree-count=-1;BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.nextchild=NULL;return t;void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-nextchild);void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);

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