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

衡阳师范学院《数据结构》课程设计题 目： 树与二叉树的转换系 别： 计算机科学系专 业： 计算机科学与设计班 级： 1302学生姓名： 戴志豪学 号： 13190217指导老师： 赵磊完成日期： 2015年1月3号第1页共22页目录.3.3.51...52.6..3.7..4.7..5.7..6.8..7...9.10.10.11.14.20第2页共22页一.需求分析本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。二．概要设计对于本次设计，需要用到树的建立 ,树与二叉树的转换算法先序后序二叉树的递归算法 ;先序后序非递归算法 ;层次序遍历算法1树的建立用链表实现创建一个树结点的结构体， 从键盘输入数据， 存入数组。把下标为 2*i+1 的值存入左孩子，为2*i+2 的存入右孩子。 BiNodecreat() ，BiNodestree_creat(char*a,intk) 。开始Y参数数组是否空或N把数组的值赋给结点的数返回空指针递归的给左子树赋值参数变为 a[2i+1]递归的给右子树赋值参数变为 a[2i+2]返回根指针结束一般树转化成二叉树转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。voidexchange()，classTree3先序遍历树的递归算法若二叉树为空，则空操作；否则（ 1）访问根结点；（ 2）先序遍历左子树；（ 3）先序遍历右子树。voidPreOrder(BiNoderoot) 。第3页共22页开始Y判断结点是否N访问根结点按前根遍历方式遍历左子树按前根遍历方式遍历左子树结束后序遍历树的递归算法若二叉树为空，则空操作；否则（ 1）后序遍历左子树；（ 2）后序遍历右子树。（ 3）访问根结点；voidPostOrder(BiNoderoot) 。第4页共22页开始Y判断结点是否N按后根遍历方式 遍历左子树按后根遍历方式 遍历右子树访问根结点结束先序遍历树的非递归算法若二叉树为空，则空操作；否则（ 1）先将根节点进栈， 在栈不为空时循环； (2)出栈p，访问*p若其右孩子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。后序遍历树的非递归算法采用一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点，如此重复操作，直到栈空为止。层次序的非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot) 。第5页共22页三．详细设计树的建立：PTreeCreatTree(PTreeT){inti=1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf(" 输入第%d结点:\n",i);scanf("%d,%d",&fa,&ch);printf("\n");p.data=ch;p.parent=fa;T.count++;T.node[T.count].data=p.data;T.node[T.count].parent=p.parent;}printf("\n");printf(" 创建的树具体情况如下 :\n");print_ptree(T);returnT;一般树转换成二叉树BTNode*change(PTreeT){inti,j=0;BTNodep[MAX_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++){p[i]=GetTreeNode(T.node[i].data);}for(i=1;i<T.count;i++){ip=&p[i];is=&p[j];while(T.node[i].parent!=is->data)第6页共22页{j++;is=&p[j];}if(!(is->firstchild)){is->firstchild=ip;ir=ip;}else{ir->rightsib=ip;ir=ip;}}Tree=&p[0];returnTree;}3先序遍历树的递归算法 ：voidpreorder(BTNode *T){if(T!=NULL){printf( "%d",T->data);preorder(T ->firstchild);preorder(T ->rightsib);}}4.先序遍历树的非递归算法voidpreOrder2(BinTree*root) //非递归先序遍历{stack<BinTree*>s;BinTree*p=root;while(p!=NULL||!s.empty()){while(p!=NULL){cout<<p->data<< "";s.push(p);p=p->lchild;}第7页共22页if(!s.empty()){p=s.top();s.pop();p=p->rchild;}}}后序遍历树的递归算法voidinoeder(BTNode *T){if(T!=NULL){inoeder(T ->firstchild);printf( "%d",T->data);inoeder(T ->rightsib);}}6后序遍历树的非递归算法voidpostOrder2(BinTree*root) //非递归后序遍历{stack<BTNode*>s;BinTree*p=root;BTNode*temp;while(p!=NULL||!s.empty()){while(p!=NULL) //沿左子树一直往下搜索， 直至出现没有左子树的结点{BTNode*btn=(BTNode*)malloc( sizeof (BTNode));btn->btnode=p;btn->isFirst= true;s.push(btn);p=p->lchild;}if(!s.empty()){temp=s.top();s.pop();if(temp->isFirst== true) //表示是第一次出现在栈顶{temp->isFirst= false;s.push(temp);p=temp->btnode->rchild;第8页共22页}else //第二次出现在栈顶{cout<<temp->btnode->data<< "";p=NULL;}}}}层次序树的非递归算法voidinitqueue(linkqueue&q) // 初始化一个带头结点的队列{q.front=q.rear=(queueptr)malloc(sizeof(queuenode));q.front->next=NULL;}voidenqueue(linkqueue&q,bitreesp) // 入队列{queueptrs;intfirst=1;s=(queueptr)malloc(sizeof(queuenode));s->ch=p;s->next=NULL;q.rear->next=s;q.rear=s;}voiddequeue(linkqueue&q,bitrees&p) // 出队列{intdata;queueptrs;s=q.front->next;p=s->ch;data=p->data;q.front->next=s->next;if(q.rear==s)q.rear=q.front;free(s);printf("%d\t",data);}intqueueempty(linkqueueq) // 判断队列是否为空{if(q.front->next==NULL)return1;return0;第9页共22页}voidtraverse(bitreesbt) // 按层次遍历树中结点{linkqueueq;bitreesp;initqueue(q);p=bt;enqueue(q,p);while(queueempty(q)!=1){dequeue(q,p);if(p->lchild!=NULL)enqueue(q,p->lchild);if(p->rchild!=NULL)enqueue(q,p->rchild);}四．}设计与调试分析1.二叉树遍历中用到的最重要的一个思想就是递归调用， 这次作业使我们对递归有了深入的理解，程序调试比较顺利。2.用栈同样可以实现二叉树的遍历， 这是我们认识到解决问题可以由多种不同的途径， 应随时将以前学过的只是灵活应用起来，解决新问题。3.因为遍历二叉树的基本操作是访问结点， 所以无论哪一种遍历方式， 对含有n个结点的二叉树，其时间复杂度为 O（n），所需辅助空间最大容量为树的深度，最坏为 n，所以空间复杂度为O（n）。4.因该程序对应不同的遍历定义了不同的结构， 使每种结构的通用性降低， 可以往在递归和非递归中使用同一种结构这一方面做进一步的思考。五．用户手册运行程序，首先出现主界面。主界面有七个选项。选项一、以双亲法创建一棵树。选项二、此选项可以对所创建的树采用递归算法进行前序遍历。选项三、此选项可以对所创建的树采用递归算法进行后序遍历。选项四、此选项可以对所创建的树采用非递归算法进行先序遍历。选项五、此选项可以对所创建的树采用非递归算法进行后序遍历。第10页共22页选项六、此选项可以退出程序。六．测试结果程序开始一般树转换成二叉树的情况第11页共22页副菜单选择：选择 9继续操作运用各种遍历形式遍历树第12页共22页第13页共22页副菜单选择 0结束程序第14页共22页七．附录（源程序）#include<stdio.h>#include<malloc.h>#include<stdlib.h>//设置常量：#defineMAX_TREE_SIZE100//一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示结点结构定义 */typedefstruct{intdata;intparent; //双亲位置域}PTNode;/*双亲表示法树结构 */typedefstruct{PTNodenode[MAX_TREE_SIZE];intcount; //根的位置和节点个数}PTree;/*树的孩子兄弟表示结点结构定义 */typedefstructnode{intdata;structnode*firstchild;structnode*rightsib;}BTNode,*BTree;//初始化树(双亲表示法)voidinit_ptree(PTree*tree){tree->count=-1;}//初始化树结点 (孩子兄弟表示法 )BTNodeGetTreeNode(intx){BTNodet;t.data=x;t.firstchild=t.rightsib=NULL;returnt;第15页共22页}//树的先序遍历 (递归)voidpreorder(BTNode*T){if(T!=NULL){printf("%d",T->data);preorder(T->firstchild);preorder(T->rightsib);}}//树的先序遍历 (非递归)voidpreorder2(PTreeT){inti;for(i=0;i<T.count;i++){printf("%d",T.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]);}第16页共22页}//层次遍历voidlevel(PTreeT){inti;for(i=0;i<T.count;i++){printf("%d",T.node[i]);}}//水平输出二叉树voidPrintBTree(BTNode*root,intlevel){inti;if(root!=NULL){PrintBTree(root->rightsib,level+1);for(i=1;i<=8*level;i++)printf("");printf("-------%d\n",root->data);PrintBTree(root->firstchild,level+1);}}//输出树voidprint_ptree(PTreetree){inti;printf(" 序号 结点 双亲\n");for(i=0;i<=tree.count;i++){printf("%8d%8d%8d",i,tree.node[i].data,tree.node[i].parent);printf("\n");}}/*用双亲表示法创建树 */PTreeCreatTree(PTreeT){第17页共22页inti=1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf("输入第%d结点:\n",i);scanf("%d,%d",&fa,&ch);printf("\n");p.data=ch;p.parent=fa;T.count++;T.node[T.count].data=p.data;T.node[T.count].parent=p.parent;}printf("\n");printf("创建的树具体情况如下 :\n");print_ptree(T);returnT;}/*一般树转换成二叉树 */BTNode*change(PTreeT){inti,j=0;BTNodep[MAX_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++){p[i]=GetTreeNode(T.node[i].data);}for(i=1;i<T.count;i++){ip=&p[i];is=&p[j];while(T.node[i].parent!=is->data){j++;is=&p[j];}第18页共22页if(!(is->firstchild)){is->firstchild=ip;ir=ip;}else{ir->rightsib=ip;ir=ip;}}Tree=&p[0];returnTree;}/*主菜单*/voidMenu(){printf("=================主菜单=======================\n");printf("***输入1-------------以双亲法创建一棵一般树***\n");printf("***输入2-------------树的先序遍历(递归)*******\n");printf("***输入3-------------树的后序遍历(递归)*******\n");printf("***输入4-------------树的先序遍历(非递归)*****\n");printf("***输入5-------------树的后序遍历(非递归)*****\n");printf("***输入6-------------层次序的非递归遍历*******\n");printf("***输入0-------------退出程序*****************\n");printf("==============================================\n");printf("请输入执行的指令:");}/*副菜单*/voidMenu2(){printf("***************** 副菜单*******************\n");printf("***9------------- 返回主菜单继续操作 *******\n");printf("***0------------- 退出程序*****************\n");}/*主函数*/intmain(){inti=0,c1,c2;PTreeT;第19页共22页BTNode*Tree;init_ptree(&T);loop:Menu();scanf("%d",&c1);switch(c1){case 1:printf("建立一般树,依次输入各个结点情况 :\n");printf("输入结点方式 :双亲数据 ,整型数据 (第一个结点双亲数据为 -1,最后以-1,-1结束)\n例子:-1,1 1,3\n");T=CreatTree(T);Tree=change(T);printf("一般树转换成二叉树后的情况 :\n");PrintBTree(Tree,i);getchar();break;case 2:printf("树的前序遍历(递归):\n");preorder(Tree);printf("\n");break;case 3:printf("树的后序遍历(递归):\n");inoeder(Tree);printf("\n");break;case 4:printf("树的前序遍历(非递归):\n");preorder2(T);printf("\n");break;case 5:printf("树的后序遍历(非递归):\n");inoeder2(T);printf("\n");break;case 6:printf("树的层次遍历:\n");第20页共22页level(T);printf("\n");break;case 0:exit(1);break;}Menu2();scanf("%d",&c2);if(c2==9)gotoloop;elseif(c2==0)exit(1);}八．课程设计心得通过本次程序设计，让我更深层次地了解到了树各种函数的运用， 如何运用各种存储结构创建树，以及在实验中还涉及到递归的运用， 递归的思想省去了复杂的算法设计。在实验中不可避免的出现了大大小小的问题， 在调试中领悟各种算法的真谛，同样的错误在下次遇到时就可以避免了 ,也让我懂得了自己动手比去做去看书要好的多，还有编程运行的时候都是不能够粗心大意的。基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究第21页共22页单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系