树与二叉树的转换.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换2. 5测试程序说明程序开始：建立一棵一般树：输入指令1输入结点方式：双亲数据（整型），结点数据（整型）以-1结束 如：-1,1 1,2 -1,-1一般树创立完的具体情况：把一般树转换为二叉树后：11副菜单项选择择：选择9继续操作 运用各种遍历形式遍历树：12副菜单项选择择：选择0结束程序3程序清单#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX_TREE_SIZE 100/-树的双亲表君储结构typedef struct PTNode结点结构int data;int parent;双亲位置域PTNode; 树的双亲表示结点的结构定义typedef struct PTree树结构PTNode node MAX_TREE_SIZE;int count;根的位置和结点数PTree; 双亲表示树的结构typedef struct nodeint data;struct node * firstchild;struct node * rightsib;BTNode,* BTree;树的孩子兄弟表示结构结点的定义void init_ptree(PTree * tree)tree->count=-l;树的初始化(双亲)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"J->data);preorder(T->firstchild);preorder(T->rightsib);)树的前序遍历(递归)void preorder2(PTree T)int i;for(i=0;i<T.count;i+)printf("%d"/T.nodei);)树的前序遍历(非递归)void inorder(BTNode * T)if(T!=NULL)inorder(T->firstchild);printf("%d",T->data);inorder(T->rightsib);)树后续的遍历(递归)void inorder2(PTree T)int i;for(i=T.count-l;i>=0;i-)printf("%d"/T.nodei);)树的后序遍历(非递归)void level(PTree T)int i;for(i=0;i<T.count;i+)printf("%d"/T.nodei); 层次遍历)void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree(root->rightsib,level+l);for(i=l;i<=8*level;i+)printf("");printf("%dnN,root->data);PrintBTree(root->firstchild,level+l);) 水平输出二叉树void print_ptree(PTree tree)int i;printf(" 序号结点 双亲n“)；for(i=0;i<=tree.count;i+)printf(',%8d%8d%8d",i,tree.nodei.dataztree.nodei.parent); printf("n");) 输出树PTree CreatTree(PTree T)int i=l;int fa,ch;PTNode p;for(i=l;ch!=-l;i+)printf("请输入第d结点:n”,i);scanf("%d,%d，&fa,&ch);printf("n");p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent;)printf("n");printf。,创立的树具体如下:n");print_ptree(T);return T; 用双亲法表示树BTNode * change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;i<T.count;i+)pi=GetTreeNode(T.nodei.data);for(i=l;i<T.count;i+)ip=&pi；is=&pj；while(T.nodei.parent !=is->data)j+；is=&pj；)if(!(is->firstchild) is->firstchild=ip;ir=ip；)Tree=&p0;return Tree; 一般树转换成二叉树void Menu()printf("主菜单nH);printf(“输入 1以双亲法创立一棵一般树n")；printf(“输入 2树的前序遍历（递归）n");printf("输入 3树的后序遍历（递归）n");printf("输入 4树的前序遍历（非递归）n");printf("输入 5树的后序遍历（非递归）n");printf(“输入 6层次序的非递归遍历n")；printf("输入 0退出程序n");printf("n");)void Menu2() printf(" printf("n");printf(“输入 9 printf(“输入 0printf(“请输入要执行的指令n“);副菜单n");返回主菜单操作n");退出程序n");)void main()int i=0,cl,c2;PTree T;BTNode * Tree;init_ptree(&T);loop:Menu();scanf("%d",&cl);switch(cl)case 1: printf("建立一般树，依次输入各个结点情况)printf("输入结点的方式：双亲数据，整型数据(第一个结点双亲数据为-1, 最后以-1, -1结束n例如：-1, 11, 3)");T=CreatTree(T);Tree=change(T);printf("一般树转换成二叉树的情况：n");PrintBTree(TreeJ);getchar();break;case 2: printf("树的前序遍历(递归)：nH);preorder(Tree);printf("n");break;case 3: printf。,树的后序遍历(递归)：n");inorder(Tree);printf("n");break;case 4: printfC,树的前序遍历(非递归)：n");preorder2(T);printf("n");break;case 5: printf(“树的后序遍历(非递归)：n");inorder2(T);printf("n");break;case 6: printf(“树的层次遍历：n");level(T);printf("n");break;case 0:exit ； break;Menu2();scanf("%d",&c2);if(c2=9)goto loop;else if(c2=0) exit ；)4测试4.1测试数据（1）编写和执行程序，输出主菜单，如图4-1T所示。12 3 4 5 6 0入入入入人人入E'M号瞿序程 三双的的的的次出单(菜建历历历典 序普递#dj 秋 般dn/>>归归 递递历请输入要执行的指令建立一亲数据次输入各个结点情况输入结点的方式：双亲数据，整型数据（第一个结点双结束例如:-1, 1 1, 3）请输入第1结点:-1.1图4-1-1程序运行结果（2）程序运行后输入指令1如图4-1-1所示，然后根据提示依次输入各个结点-1, 11,2 2, 3 3,4 3, 5 4,6 -1,-1 如图 4-1-2 所示。Im " E:vc -h 4-3erDebu qe r.exew.亲数据为T，最后以T，T结束 例如：-1, 11, 3）请输入第1结点:-1.1请输入第2结点：1,2请输入第3结点：2,3请输入第4结点：3,4请输入第5结点：3,5请输入第6结点：4,6请输入第7结点：-1，一1创立曾亶具罐里下q主图4-1 -2输入各个结点（3）车刖入名口点以-1,1开始，以-1, -1 2口束，输出树的2口点和双亲如图4-1-3所不。创立世树具他地下： 序号结点双杀01-11212323434535646-1-1般树转换成二叉树的情况:1 2副菜单9 0人入返退回出.a- tnp s 主程4-1 -3创立树（4）选择功能9返回主菜单，继续选择功能键执行命令, 前序遍历（递归）如图4-1-4所示。4-1 -3创立树（4）选择功能9返回主菜单，继续选择功能键执行命令, 前序遍历（递归）如图4-1-4所示。选择功能键2,输出树的, E:贺据报告 Debugfdd.exe,9 0 入入 公那么刖99 0 入入 公那么刖9返退主程回出12 3 4 5 6 0入入人入人人入笔创院亲一号瞿序程 三嗡的的的次出- I, 建历历历皆普递归归遮遍历4MJ 秋 般33请输入要执行的指令2树的前序遍历（递归）：12346副菜单顿人9返回主菜单操作输入0退出程后图4-1-4输出树的遍历（5）选择功能9返回主菜单，继续选择功能键执行命令，选择功能键5,输出树的 后序遍历如图4-1-5所示。供盘报告'Debugfdd.exe/对的层次遍历:123456副菜单4MJ 秋 般33归归递递历膏递- 1 建历历历典主程回出返退9 0人入PMZ-OH bl-k-rr-Tr 9更创髀法序 以亲口卷疆序程 3双的的的的次出量 青输入要执行的指令胸的后序遍历（非递归）：U654321I副菜单P输入9返回主是单操作输入。追出程序图4-1-5树的后序遍历（6）选择功能9返回主菜单，继续选择功能键执行命令，选择功能,6,输出树的层 序遍历，如图4-1-6所示。报告Debugfdd,exe" . ,.返退回出单 主程12 3 4 5 6 0 入人入入人人入 R»S.if nr I HzK. .» I i 1 、.1 1 % - - nnn- - nnn- - nnn - oon nnn "二；二 1X4.膏递 建历历历着 单创 法序 以亲一卷瞿序程 3双任的的的次出归递历4MJ 杈 般33E 青输入要执行的指令 他的层次遍历： 1123456 ,副菜单1输入9返回主菜单操作嗡入。退出程序4-1-6树的层序遍历4. 2测试结果分析(1)输入结点生成二叉树，根据二叉链式存储结构生成的二叉树链式存储结 构，二叉树的结点由一个数据元素和分别指向左右子树的两个分支组成，所以二叉 树链表中的结点至少有3个域：数据域，左、右指针域。如图4-2-1所示。A 2图4-2-1二叉链表(2)树与二叉树的转换，由于二叉树和树都可用二叉链表作为存储结构，那么以 二叉链表作为媒介可导出树与二叉树的之间一个对应关系。也就是说，给定一棵树, 可以找到惟一的一棵二叉树与之对应，从物理结构看，它们的二叉链表是相同的， 只是解释不同而已。二叉树的表示如图4-2-2所示。6图4-2-2二叉树的表示题目树与二叉树的转换考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:5总结通过一周的学习，让我学会了如何去运用所学的知识，把实际与课本结合起来。 根据自己的题目能够考虑问题更加全面，不再只是凭意识和简单的语句来堆砌出一 段程序。自己也能够找出最合适的算法去实现树与二叉树的转换。在学习过程中，我看到了许多自己的缺乏，只是注重如何编写函数能够完成所 需要的功能，似乎没有明确方法。这次实验让我意识到了自己的缺乏，我也在不断 地改正自己，让自己的水平不断地提高。通过这次实验，我对编程更加感兴趣，相信在越来越多的尝试之后，自己会不 断地提高和进步。参考文献1 .数据结构（C语言版）严蔚敏清华大学出版社20022 .数据结构-C语言描述王路群中国水利水电出版社20073 .数据结构实验教程（C语言版）王国钧 清华大学出版社20094 .数据结构题集严蔚敏，吴伟民编 清华大学出版社2002目录31课程设计目标与任务31.1 课程设计目标41.2 课程设计任务42分析与设计42. 1题目需求分析42.2存储结构设计4221树的双亲表存储表示41.1.2 树的孩子链表存储表示51.1.3 二叉树的顺序存储表示51.1.4 二叉树的二叉链表存储表示62.3 算法描述72.3.1 前序遍历二叉树的递归算法72.3.2 后序遍历二叉树的递归算法72.3.3 前序非递归算法72.3.4 后序非递归算法72.3.5 层次序遍历算法82.3.6 树与二叉树的转换算法82.4 程序流程图82.5 测试程序说明103程序清单114测试164. 1测试数据164. 2测试结果分析19参考文献211课程设计目标与任务课程设计目标（1） 了解和掌握树的相关概念、遍历和存储表达方法。（2） 了解和掌握二叉树的概念及性质、遍历和算法的实现。（3）能够编码实现树与二叉树之间的转换，具备初步的独立分析和设计能力。（4）在实际应用中学会运用树，能够理解、设计、分析和应用程序。（5）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本 方法和技能。2. 2课程设计任务（1）实现树与二叉树的转换；（2）能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显 示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计编辑算法，实现树与二叉树转换，利用双亲表示法和树的孩子链表来实现树的 遍历算法，以及树的表示及其遍历操作，并建立树与二叉树的对应关系。2.1 题目需求分析1 .根据给定二叉树的先序遍历结果，构造出该二叉树；按先序次序输入二叉树 中结点的值（一个字符），空格字符表示空树。2 .给出该二叉树的递归前序和后序遍历结果。用栈实现非递归前序、后序的遍 历的。还有对树的层序遍历以及树与二叉树的转换。3 .以字符输入，假设要实现终端结点，最后以回车键建入数据。3. 2存储结构设计二叉树是另一种树结构，他的特点是每个结点至多有两棵子树，并且，二叉树 的子树有左右之分，其次序不能颠倒。3.1.1 树的双亲表存储表示假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下：#define MAX_TREE_SIZE 100typedef struct PTNode 结点结构TEIemType data;Int parent;双亲结构PTNode;typedef struct树结构PTNode nodesMAX_TREE_SIZE;INT R,N;根的位置和结点数PTree;222树的孩子链表存储表示把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构, 那么n个结点有n个孩子链表。而n个头指针又组成一个线性表，为了便于查找，可 采用顺序存储结构，这种存储结构可形式地说明如下：typedef struct CTNode 孩子结点intchild;struct CTNode *next;*ChildPtr;typedef struct TEIemType data;ChildPtr firstchild;孩子链表头指针CTBox;typedef structCTbox nodesMAX_TREE_SIZE;int n,r;结点数和根的位置CTree;二叉树的顺序存储表示按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至 右存储完全二叉树上的结点元素，二叉树的顺序存储表示说明如下：#define MAX_TREE_SIZE 100二叉树的最大结点数typedefTEIemType SqBiTreeMAX_TREE_SIZE; /0 号单元存储根结点 SqBiTree bt;2.2.3 二叉树的二叉链表存储表示设计不同的结点结构可构成不同形式的链式存储结构。二叉树的结点由一个数 据元素和分别指向其左右子树的两个分支构成，二叉链表的定义和局部基本操作的 函数说明如下：typedef struct BiTNodeTEIemType data; struct BiTNode *lchild,*rchild; 右孩子指针 BiTNode/BiTree;/-基本操作的函数原型说明-Status CreateBiTree(BiTree &T);按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示二叉树ToStatus PreOrderTraverse(BiTre T,Status(*VisitXT日emType e);采用二叉链表存储结构，Visit是对结点操作的应用函数。先序遍历二叉树T,对每个结点调用函数Visit 一次且仅一次。一旦Visit ()失败，那么操作失败。Status lnOrderTraverse(BiTre T,Status(*Visit)(T日emType e);采用二叉链表存储结构，Visit是对结点操作的应用函数。中序遍历二叉树T,对每个结点调用函数Visit 一次且仅一次。一旦Visit ()失败，那么操作失败。Status PostOrderTraverse(BiTre T,Status(*Visit)(T日emType e);采用二叉链表存储结构，Visit是对结点操作的应用函数。后序遍历二叉树T,对每个结点调用函数Visit 一次且仅一次。一旦Visit （）失败，那么操作失败。Status LevelOrderTraverse(BiTre T,Status(*Visit)(T日emType e);采用二叉链表存储结构，Visit是对结点操作的应用函数。层序遍历二叉树T,对每个结点调用函数Visit 一次且仅一次。一旦Visit （）失败，那么操作失败。2. 3算法描述分别设计二叉树的递归算法、非递归算法层序遍历算法来实现树与二叉树转换的算法。2.1.1 前序遍历二叉树的递归算法前序遍历二叉树的递归算法，假设二叉树为空，那么算法结束，否那么（1）访问根结点，（2）前序遍历左子树，（3）前序遍历右子树。void preorder(BTNode * T)后序遍历二叉树的递归算法后序遍历二叉树的递归算法，假设二叉树非空，那么空操作；否那么遍历左子树;遍历右子树；（3）访问根结点。void inorder(BTNode * T)前序非递归算法前序非递归算法，BTNode根指针，假设BTNode!二NULL对于非递归算法，引入栈 模拟递归工作栈，初始时栈为空。void preorder2(PTree T)后序非递归算法后序非递归算法，BTNode是要遍历树的根指针，后序遍历要求在遍历完左右子 树后，再访问根。需要判断根结点的左右子树是否均遍历过。void inorder2(PTree T)层次序遍历算法层次序遍历算法，按照树的层次从左到右访问树的结点，层序遍历用于保存结 点的容器是队列。void level(PTree T)树与二叉树的转换算法树与二叉树的转换算法，转换时结点的第一个孩子变为他的左孩子，兄弟结点 变为他的右孩子。BTNode * change(PTree T)2.4程序流程图程序执行时首先访问主菜单，有六个功能双亲法建树、前序遍历（递归）、后 序遍历（递归）、前序遍历（非递归）、后序遍历（非递归）层次遍历，双亲表示法 建树按格式输入各个结点，输出树的结点情况。程序流程图如下:2-4-1流程图