数据结构课程设计之-树与二叉树的转换.doc

1一程序设计要求与目的二存储结构设计三算法设计(流程图)四详细设计(源代码)五调试与分析六实验总结七参考文献第一章程序设计要求与目的题目:树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。第二章存储结构设计引入头文件:#include<>#include<>#include<>设置常量:#defineMAX_TREE_SIZE100一般树的存储结构有以下几种:双亲结点,孩子结点,孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下:/*树的双亲表示结点结构定义*/typedefstruct{intdata;intparent;//双亲位置域}PTNode;/*双亲表示法树结构*/typedefstruct{PTNodenode[MAX_TREE_SIZE];intcount;//根的位置和节点个数}PTree;/*树的孩子兄弟表示结点结构定义*/2typedefstructnode{intdata;structnode*firstchild;structnode*rightsib;}BTNode,*BTree;第三章算法设计(流程图)流程图:3退出程序层次遍历开始双亲法建树按照格式输入各个结点输出树的结点情况1主菜单前序遍历(递归)后序遍历(递归)前序遍历(非递归)后序遍历(非递归)输出遍历结果副菜单退出程序23540069第四章详细设计(源代码)详细设计共有以下函数的实现:4树的初始化函数(双亲法和孩子结点法两种),建树函数,输出树函数,树的前序遍历函数(递归和非递归两种),树的后序遍历函数(递归和非递归两种),树的层次遍历函数,一般树和二叉树的转换函数。主菜单和副菜单。主函数。具体代码如下://初始化树(双亲表示法)voidinit_ptree(PTree*tree){tree->count=-1;}//初始化树结点(孩子兄弟表示法)BTNodeGetTreeNode(intx){BTNodet;=x;==NULL;returnt;}//树的前序遍历(递归)voidpreorder(BTNode*T){if(T!=NULL){printf("%d",T->data);preorder(T->firstchild);preorder(T->rightsib);}}//树的前序遍历(非递归)voidpreorder2(PTreeT){inti;for(i=0;i<;i++){printf("%d",[i]);}}5//树后序遍历(递归)voidinoeder(BTNode*T){if(T!=NULL){inoeder(T->firstchild);printf("%d",T->data);inoeder(T->rightsib);}}//树后序遍历(非递归)voidinoeder2(PTreeT){inti;for(i=-1;i>=0;i--){printf("%d",[i]);}}//层次遍历voidlevel(PTreeT){inti;for(i=0;i<;i++){printf("%d",[i]);}}//水平输出二叉树voidPrintBTree(BTNode*root,intlevel){inti;if(root!=NULL){PrintBTree(root->rightsib,level+1);for(i=1;i<=8*level;i++)printf("");6printf("-------%d\n",root->data);PrintBTree(root->firstchild,level+1);}}//输出树voidprint_ptree(PTreetree){inti;printf("序号结点双亲\n");for(i=0;i<=;i++){printf("%8d%8d%8d",i,[i].data,[i].parent);printf("\n");}}/*用双亲表示法创建树*/PTreeCreatTree(PTreeT){inti=1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf("输入第%d结点:\n",i);scanf("%d,%d",&fa,&ch);printf("\n");=ch;=fa;++;[].data=;[].parent=