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

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图43 程序清单54 测试94.1 测试数据910114.2 测试结果分析115 总结12参考文献131 课程设计目标与任务1.1 课程设计目标实现树与二叉树的转换1.2 课程设计任务 (1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析 对于一般树，树中孩子的次序并不重要，只要双亲与孩子的关系正确即可。但在二叉树中，左、右孩子的次序是严格区分的。所以在讨论二叉树和一般树的转换时，为不引起混淆，就约定按树上现有结点次序进行转换。树结构的建立是在数据逻辑结构基础上的数据类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。一个好的二叉树遍历算法应包含以下功能：1） 以递归和和非递归方法建立二叉树或完全二叉树；2） 实现二叉树的前序遍历、中序遍历、后序遍历；每种遍历算法皆以递归和非递归方法实现；2.2 存储结构设计1双亲的表示#difine MAX_TREE_SIZE 100Typedeft stuct PTNode TElemType data;PTNode;Typedef struct| PTNode nodesMAX_TREE_SIZE;Int r,n;PTree;2树的孩子表示Typedeft stuct CTNodeInt child;Struct CTNode*next;*ChildPtr;Typedeft stuctTElemType data;CTBox;Typedeft stuctCTBox nodesMAX_TREE_SIZE;Int n,r;CTree;3孩子兄弟的表示方法/树的二叉链表（孩子-兄弟）存储表示-Typedeft stuct CSNodeElemType data;Stuct CSNode *fistchild,*nextsibing;CSNode,*CSTree; 2.3 算法描述1 一般树转换为二叉树将一般树转化为二叉树的思路，主要根据树的孩子兄弟存储方式而来（1）加线。在各兄弟间用虚线相连。（2）抹线。对每个结点仅保留它与最左边孩子的连线，抹去该结点与其它孩子之间的连线。（3）旋转。把虚线改为实线从水平方向向下旋转45度，成右斜下方向。由于二叉树中各结点的右孩子都是原树中该结点的兄弟，而一般的根结点有没有兄弟结点，因此生成的二叉树的根结点没有右子树。在所生成的二叉树中某一结点的左孩子仍是原来树中该节点的长子，并且是它的左孩子。2二叉树还原为一般树二叉树还原为一般树，此时的二叉树必须是由转换而来的没有右子树的二叉树。（1）加线。某结点是双亲结点的左孩子，则该结点的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点的双亲结点的双亲结点用虚线连接。（2） 抹线。把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟，抹去的连线是兄弟间的关系。2.4 程序流程图一般树的存储结构有以下几种：双亲结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。树的初始化函数，建树函数，输出树函数，树的前序遍历函数，树的后序遍历函数，树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单。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-2 二叉树信息界面图4.1-3 结束界面4.2 测试结果分析由于二叉树都可用二叉链表作为存储结构，则以二叉表作为媒介课导出树与二叉树之间的一个对应的一个对应的关系。也就是说给定一棵树，可以找到唯一的一颗二叉树与之对应，从物理结构来看，他们的二叉链表是相同的，只是解释不同而已。从树的二叉链表表示的定义可知，任何一颗和树对应的二叉树，其右子树必为空。5 总结树是数据结构的重要章节，而二叉树又是树的核心，掌握二叉树的创建，运用递归法和非递归法能够遍历二叉树。实现树与二叉树之间的转换，以及森林与二叉树的转换。运用链表结构来表示树，可以清楚实现有效的存储结构来表示树。参考文献(1)严蔚敏 吴伟民 编数据结构( C语言版) 清华大学出版社(2)严蔚敏 编数据结构习题集清华大学出版社(3)谭浩强 编C+面向对象程序设计 清华大学出版社#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); /输出根结