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

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计题目11.2 课程设计目的及基本要求12 分析与设计22.1 题目需求分析22.3 算法描述32.4 程序流程图33 程序清单54 测试94.1 测试数据94.2 测试结果分析125 实验总结13参考资料131 课程设计目标与任务1.1 课程设计题目 设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.2 课程设计目的及基本要求 通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根据实际问题的具体情况，结合数据结构课程中的基本理论金额基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2 分析与设计2.1 题目需求分析树结构的建立是在数据逻辑结构基础上的数据类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。一个好的二叉树遍历算法应包含以下功能：1） 以递归和和非递归方法建立二叉树或完全二叉树；2） 实现二叉树的前序遍历、中序遍历、后序遍历；3） 每种遍历算法皆以递归和非递归方法实现；2.2 存储结构设计引入头文件：#include#include#include设置常量：#difineMAX_TREE_SIZE一般树的存储结构有以下几种：双亲节点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示结点结构定义*/TypedefstructInt data;Int parent; /双亲位置域PTNode;/*双亲表示法树结构*/TypedefstructPTNode nodeMAX_TREE_SIZE;Int count; /根的位置和结点个数PTree；/*树的孩子兄弟表示结点结构定义*/Typedefstruct node Int data;Struct node*firstchild;Struct node*rightsib;BTNode;*BTree;2.3 算法描述首先建立头结点，并保存数据，然后根据递归方法，分别建立其左右孩子结点，且左右孩子结点的指针域指向空。以递归方法建立二叉树，每次建立一个结点后，将其左右孩子指针域置空，成为叶子结点。然后通过前序遍历、中序遍历、后序遍历实现数据最优，方便数据的使用。2.4 程序流程图流程图如下：图2.4-1程序流程图3 程序清单#include using namespace std; #define m 3 typedef char ElemType; typedef struct Node ElemType data; struct Node* childm; Node,*Tree; typedef struct BiTNode ElemType data; struct BiTNode*lchild,*rchild; BiTNode,*BiTree; typedef struct stack /栈结构定义 BiTree data100; /data 元素类型为 指针 int top; /栈顶指针 seqstack; / 按前序遍历 创建一棵度数为3的树的递归算法 void createtree(Tree &p) int i; char ch; if(ch=getchar()=#) p=NULL; /建立一棵空树 else p=(Tree)malloc(sizeof(Node); /用new 怎么建立 p-data=ch; for(i=0;ichildi); BiTree TreetoBiTree(Tree &p) int i; if(p=NULL) return NULL; BiTNode* q=(BiTNode*)malloc(sizeof(ElemType) ;/创建根节点 - q-data =p-data; q-lchild=NULL; q-rchild=NULL; if(p-child0!=NULL) q-lchild=TreetoBiTree(p-child0);/把树的第一个孩子赋给二叉树的左孩子 BiTNode* r=q-lchild; if(p-child1!=NULL) for(i=1;ichildi!=NULL) r-rchild=TreetoBiTree(p-child i); r=r-rchild; else return q; else if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); r=r-rchild; else return q; else if(p-child1!=NULL) q-lchild=TreetoBiTree(p-child1);/把树的第二个孩子赋给二叉树的左孩子 BiTNode* r=q-lchild; if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); else return q; else if(p-child2!=NULL) q-lchild=TreetoBiTree(p-child1);/把树的第三个孩子赋给二叉树的左孩子 return q; Tree BiTreetoTree(BiTree &q) int i; if(q=NULL)return NULL; Node* p=(Node*)malloc(sizeof(ElemType); p-data=q-data;/根赋值 for(i=0;ichildi=NULL; if(q-lchild!=NULL) p-child0=BiTreetoTree(q-lchild); BiTNode* r=q-lchild ; for(i=1;irchild!=NULL) p-childi=BiTreetoTree(r-rchild ); r=r-rchild ; return p; void push(seqstack* s,BiTree p) /进栈 s-data+s-top=p; BiTree pop(seqstack* s) /出栈 if(s-top!=-1) /非递归遍历中，top初始值为-1 s-top-; return (s-datas-top+1); else return NULL; void PreOrderPrint(BiTree &q) if(q!=NULL) printf(%c,q-data); PreOrderPrint(q-lchild); PreOrderPrint(q-rchild); /二叉树中序遍历 非递归 算法 void inorder1(BiTree p) seqstack s; s.top=-1; while(p!=NULL)|(s.top!=-1) while(p) push(&s,p); p=p-lchild; /子树根结点全部进栈 if(s.top!=-1) p=pop(&s); printf(%c,p-data); /输出根结点，其实也就是左孩子或右孩子(没有孩子的根结点是它父亲的左或右孩子） p=p-rchild; /进入右孩子访问 /树的前序遍历递归算法 void preorder(Tree p) /P为指向树根的指针 int i; if(p!=NULL) /树不为空 printf(%c,p-data); /输出根节点的值 for(i=0;ichildi); /树的后序遍历的递归算法 void postorder(Tree p) int i; if(p!=NULL) for(i=0;ichildi); printf(%c,p-data); /输出根节点的值 /树的层次遍历 void level(Tree t) Tree queue20; /存放等待访问的节点队列,每个元素都是指针型 int f=0,r=0,i; /f,r 分别是队头,队尾指针 Tree p; queue0=t; while(fdata); /访问队头元素 for(i=0;ichildi) +r; queuer=p-childi; void main() printf(tt*n); printf(tt 树转化为二叉树 n); printf(tt*n); Tree T; Tree T1; BiTree p; printf(=输入要创建的树=:n); createtree(T);/创建 一棵树 printf(n树的先序遍历:); preorder(T); printf(n树的后序遍历:); postorder(T); printf(n树的层序遍历:); level(T); printf(n); printf(n=树转换为二叉树=n); p=TreetoBiTree(T); printf(n遍历二叉树:); PreOrderPrint(p); 4 测试4.1 测试数据图4.1-1开始界面图4.1-1选择功能界面图4.1-3二叉树信息界面图4.1-4结束界面4.2 测试结果分析 首先根据指令，输入信息，生成一个树后，再将生成的树转化成二叉树，然后输出二叉树的结构图，二叉树的前序遍历结果以及二叉树的深度和节点孩子数。5 实验总结这次实验也以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法了。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。理解典型数据结构的性质是非常有用的，它往往是编写程序的关键。这次实验让我看到了自己的不足，还是不太用模板类。还有许多关于C+的一些比较具体的东西还不太懂，比如说指针。这次试验还让我意识到只有不断在机子上调试程序，自己的水平才能得到提高。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。参考资料(1)严蔚敏 吴伟民 编数据结构( C语言版) 清华大学出版社(2)严蔚敏 编数据结构习题集清华大学出版社#include using namespace std; #define m 3 typedef char ElemType; typedef struct Node ElemType data; struct Node* childm; Node,*Tree; typedef struct BiTNode ElemType data; struct BiTNode*lchild,*rchild; BiTNode,*BiTree; typedef struct stack /栈结构定义 BiTree data100; /data 元素类型为 指针 int top; /栈顶指针 seqstack; / 按前序遍历 创建一棵度数为3的树的递归算法 void createtree(Tree &p) int i; char ch; if(ch=getchar()=#) p=NULL; /建立一棵空树 else p=(Tree)malloc(sizeof(Node); /用new 怎么建立 p-data=ch; for(i=0;ichildi); BiTree TreetoBiTree(Tree &p) int i; if(p=NULL) return NULL; BiTNode* q=(BiTNode*)malloc(sizeof(ElemType) ;/创建根节点 - q-data =p-data; q-lchild=NULL; q-rchild=NULL; if(p-child0!=NULL) q-lchild=TreetoBiTree(p-child0);/把树的第一个孩子赋给二叉树的左孩子 BiTNode* r=q-lchild; if(p-child1!=NULL) for(i=1;ichildi!=NULL) r-rchild=TreetoBiTree(p-child i); r=r-rchild; else return q; else if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); r=r-rchild; else return q; else if(p-child1!=NULL) q-lchild=TreetoBiTree(p-child1);/把树的第二个孩子赋给二叉树的左孩子 BiTNode* r=q-lchild; if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); else return q; else if(p-child2!=NULL) q-lchild=TreetoBiTree(p-child1);/把树的第三个孩子赋给二叉树的左孩子 return q; Tree BiTreetoTree(BiTree &q) int i; if(q=NULL)return NULL; Node* p=(Node*)malloc(sizeof(ElemType); p-data=q-data;/根赋值 for(i=0;ichildi=NULL; if(q-lchild!=NULL) p-child0=BiTreetoTree(q-lchild); BiTNode* r=q-lchild; for(i=1;irchild!=NULL) p-childi=BiTreetoTree(r-rchild ); r=r-rchild ; return p; void push(seqstack* s,BiTree p) /进栈 s-data+s-top=p; BiTree pop(seqstack* s) /出栈 if(s-top!=-1) /非递归遍历中，top初始值为-1 s-top-; return (s-datas-top+1); else return NULL; void PreOrderPrint(BiTree &q) if(q!=NULL) printf(%c,q-data); PreOrderPrint(q-lchild); PreOrderPrint(q-rchild); /二叉树中序遍历 非递归 算法 void inorder1(BiTree p) seqstack s; s.top=-1; while(p!=NULL)|(s.top!=-1) while(p) push(&s,p); p=p-lchild; /子树根结点全部进栈 if(s.top!=-1) p=pop(&s); printf(%c,p-data); /输出根结点，其实也就是左孩子或右孩子