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

《数据结构课程设计之-树与二叉树的转换》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、纲要一程序设计要求与目的二存储结构设计三算法设计（流程图）四详细设计（源代码）五调试与分析六实验总结七参考文献14第一章程序设计要求与目的题目：树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。第二章存储结构设计引入头文件：#include#include#include设置常量：#defineMAX_TREE_SIZE100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结

2、构如下：/*树的双亲表示结点结构定义*/typedefstruct{intdata;intparent;//双亲位置域}PTNode;/*双亲表示法树结构*/typedefstruct{PTNodenode[MAX_TREE_SIZE];intcount;//根的位置和节点个数}PTree;/*树的孩子兄弟表示结点结构定义*/typedefstructnode{intdata;structnode*firstchild;structnode*rightsib;}BTNode,*BTree;14第三章算法设计（流程图）流程图：退出程序层次遍历开始双亲法建树按

3、照格式输入各个结点输出树的结点情况1主菜单前序遍历（递归）后序遍历（递归）前序遍历（非递归）后序遍历（非递归）输出遍历结果副菜单退出程序2354006914第四章详细设计（源代码）详细设计共有以下函数的实现：树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数(递归和非递归两种）,树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单。主函数。具体代码如下：//初始化树(双亲表示法)voidinit_ptree(PTree*tree){tree->count=-1;}//初始化树结点(孩

4、子兄弟表示法)BTNodeGetTreeNode(intx){BTNodet;t.data=x;t.firstchild=t.rightsib=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

5、node[i]);}}//树后序遍历(递归)voidinoeder(BTNode*T){if(T!=NULL){inoeder(T->firstchild);printf("%d",T->data);inoeder(T->rightsib);}}//树后序遍历(非递归)voidinoeder2(PTreeT){inti;for(i=T.count-1;i>=0;i--){printf("%d",T.node[i]);}}//层次遍历voidlevel(PTreeT){inti;for(i=0;i

6、e[i]);}}//水平输出二叉树voidPrintBTree(BTNode*root,intlevel){inti;if(root!=NULL){14PrintBTree(root->rightsib,level+1);for(i=1;i<=8*level;i++)printf("");printf("-------%d",root->data);PrintBTree(root->firstchild,level+1);}}//输出树voidprint_ptree(PTreetree){inti;printf("序号结点双亲");for(i=0;

7、i<=tree.count;i++){printf("%8d%8d%8d",i,tree.node[i].data,tree.node[i].parent);printf("");}}/*用双亲表示法创建树*/PTreeCreatTree(PTreeT){inti=1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf("输入第%d结点:",i);scanf("%d,%d",&fa,&ch);printf("");p.data=ch;p.parent=fa;T.count++;T.node[T.count].

8、data=p.data;T.node[T.count].paren