树与二叉树转换实现.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现2014年12月29日3程序清单ftinclude <iostream> using namespace std;#define m 3typedef char ElemType;typedef struct Node ElemType data; struct Node* childm;Node, *Tree;typedef struct BiTNodeElemType data;struct BiTNode*lchild, *rchild;BiTNode, *BiTree;栈结构定义/data元素类型为指针栈顶指针创立一棵度数为3的树的递归算法typedef struct stack BiTree data100;int top; seqstack; /按前序遍历 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;i<m;i+) createtree(p->childi);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-> Ichi Id 二TreetoBiTree (p->child0);把树的第一个孩子赋给二叉树 的左孩子BiTNode* r=q->lchild;if(p->childl!=NULL)for(i=l;i<m;i+) if(p->childi!=NULL) r->rchild=TreetoBiTree(p->child i);r=r->rchild;elseelsereturn q;else if(p->child2!=NULL)r->rchild=TreetoBiTree(p->child 2);r=r->rchild; else return q; else if(p->childl!=NULL)q->lchild=TreetoBiTree(p->childl);把树的第二个孩子赋给二叉树 的左孩子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->childl);把树的第三个孩子赋给二叉树 的左孩子)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;i<m;i+)p->chiIdi=NULL; if (q->lchild!=NULL)p->child0=BiTreetoTree (q->Ichi Id);BiTNode* r=q->lchildfor(i=l;i<m;i+) if(r->rchild!=NULL) p->childi=BiTreetoTree(r->rchild );r=r->rchildreturn p; void push (seqstack* s,BiTreeP)/进栈出栈if (s->top!=-l) s->top一;return (s->datas->top+l);else return NULL; void PreOrderPrint(BiTree &q)非递归遍历中，top初始值为Ts->data+s->top=p; BiTree pop(seqstack* s)if(q!=NULL) printf (/z%c/z, q->data);PreOrderPrint(q->lchild);PreOrderPrint(q->rchild);)二叉树中序遍历 非递归算法 void inorderl(BiTree p) seqstack s;s. top=一1;while(p!=NULL)| (s. top!=-l) while (p)push (&s, p);p=p->lchild; 子树根结点全部进栈 if (s. top!=-l) p=pop(&s);printfr%cz/,p->data); 输出根结点，其实也就是左孩子或右孩子(没有孩子的根结点是它父亲的左或右孩子)p=p->rchild;进入右孩子访问) 树的前序遍历递归算法void preorder (Tree p) P为指向树根的指针int i; if (p!=NULL)int i; if (p!=NULL)树不为空 printf(%c, p->data);for (i=0;i<m;i+) 历preorder(p->chiIdi);) 树的后序遍历的递归算法 void postorder(Tree p) int i; if(p!=NULL) for (i=0;i<m;i+) 遍历postorder(p->chiId i);printf(%c, p->data);) 树的层次遍历void level (Tree t) 输出根节点的值依次递归实现各子树的前序遍依次递归实现个子树的后序输出根节点的值Tree queue20;存放等待访问的节点队列,每个元素都是指针型int f=0, r=0, i;/f, r分别是队头，队尾指针Tree p;queue0=t;while (f<=r) p=queuef;f+; printf (/z%c/z, p->data);访问队头元素for(i=0;i<m;i+)/将刚被访问的元素的所有子女 节点依次进if(p->childi)+r; queuer=p->child i; void main ()树转化为二叉树n);printf (ttTree T; Tree T1;BiTree p; printf (二二二二二输入要仓U建的树二二二二二:n)；createtree(T);创立一棵树printf (n树的先序遍历：);preorder ；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 选择功能界面C:Windowssystem 32cmd.exe数 为历行 图遍构的 结前深盘 的的的一、一、T、二一 秋.秋林- 叉叉叉叉出 12 3 4 5请选择需要的功能*a按任意键返回.图4.1-2二叉树信息界面10SJ C:Windowssystem32cmd.exettuununnunnnnunnnnunuununnnunnnnuunnunnuunnunnnnnunnn12 3 4 5二叉树的信息心 I S 构的 结融体占树 寸、T、J 叉叉叉 二二二二退nnnnnnunnnnunnnnnnnnnnnuuuunnnnunuunnnununnnunnnnn请选择需要的功能（1-5：图4.1-3结束界面4. 2测试结果分析由于二叉树都可用二叉链表作为存储结构，那么以二叉表作为媒介课导出树与 二叉树之间的一个对应的一个对应的关系。也就是说给定一棵树，可以找到唯一 的一颗二叉树与之对应，从物理结构来看，他们的二叉链表是相同的，只是解释 不同而已。从树的二叉链表表示的定义可知，任何一颗和树对应的二叉树，其右 子树必为空。115总结树是数据结构的重要章节，而二叉树又是树的核心，掌握二叉树的创立，运 用递归法和非递归法能够遍历二叉树。实现树与二叉树之间的转换，以及森林与 二叉树的转换。运用链表结构来表示树,可以清楚实现有效的存储结构来表示树。12参考文献严蔚敏吴伟民编数据结构（c语言版）清华大学出版社严蔚敏编数据结构习题集清华大学出版社谭浩强编C+面向对象程序设计清华大学出版社13题目树与二叉树转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12分析与设计22.1题目需求分析22.2存储结构设计22. 3算法描述32.4程序流程图43程序清单54测试94.1 测试数据912 3 4 5构的 结前深思 的的的Y?; 成桃林或- 叉叉叉 二二二二退图遍孩数 为历玄请选择需要的功能*a*d*c*e*-b按任意键返回.C:Windowssystem32cmd.exeC：S.C:Windowssystem32cmd.exeit it it it tt tt n n m tt it ii it it n ti ti ti n ti u n it u mi ti u ti n tin it u uiiiiiiiiniiti n ttn n it it it n二叉树的信息数中心 I S 构的 结融体占树 的叉 寸、T、J 叔杈叔叔 叉叉叉 二二二二退 12 3 4 5nnnnnnunnnnunnnnnnnnnnnuuuunnnnunuunnnununnnunnnnn请选择需要的功能（1-5：114.2 测试结果分析115总结12参考文献131课程设计目标与任务1.1课程设计目标实现树与二叉树的转换1. 2课程设计任务（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计1.1 题目需求分析对于一般树，树中孩子的次序并不重要，只要双亲与孩子的关系正确即可。 但在二叉树中，左、右孩子的次序是严格区分的。所以在讨论二叉树和一般树的 转换时，为不引起混淆，就约定按树上现有结点次序进行转换。树结构的建立是在数据逻辑结构基础上的数据类型，二叉树那么是树结构中最 常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、 查找等。一个好的二叉树遍历算法应包含以下功能：1）以递归和和非递归方法建立二叉树或完全二叉树；2）实现二叉树的前序遍历、中序遍历、后序遍历；每种遍历算法皆以递归和非递归方法实现；2. 2存储结构设计1双亲的表示ttdifine MAX_TREE_SIZE 100Typedeft stuct PTNodeTElemType data;PTNode;Typedef structPTNode nodesMAX_TREE_SIZE;Int r, n;PTree;2树的孩子表示Typedeft stuct CTNodeInt child;Struct CTNode*next;*ChildPtr;Typedeft stuct TElemType data;CTBox;Typedeft stuct CTBox 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程序流程图一般树的存储结构有以下几种：双亲结点，孩子兄弟结点。本实验运用到的 是双亲结点和孩子兄弟结点。树的初始化函数，建树函数，输出树函数，树的前 序遍历函数，树的后序遍历函数，树的层次遍历函数，一般树和二叉树的转换函 数。主菜单和副菜单。