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

第1页共21页衡阳师范学院《数据结构》课程设计题目：树与二叉树的转换系别：计算机科学系专业：计算机科学与设计班级：1302学生姓名：戴志豪学号：13190217指导老师：赵磊完成日期：2015年1月3号第2页共21页目录一．需求分析.…………………………………………………………………3二．概要设析………………………………………………………………….3三．详细设计………………………………………………………………….51.树的建立………………………………………………………………..52.一般树转化成二叉树…………………………………………………..63.先序遍历树的递归算法………………………………………………..74.后序遍历树的递归算法………………………………………………..75.先序遍历树的非递归算法……………………………………………..76.后序遍历树的非递归算法……………………………………………..87.层次序非递归的算法…………………………………………………..9四．设计与调试分析………………………………………………………….10五．用户手册………………………………………………………………….10六．测试结果………………………………………………………………….11七．附录（源程序）………………………………………………………….14八．总结……………………………………………………………………….20第3页共21页一.需求分析本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。二．概要设计对于本次设计，需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法;先序后序非递归算法;层次序遍历算法1树的建立用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1的值存入左孩子，为2*i+2的存入右孩子。BiNodecreat()，BiNodestree_creat(char*a,intk)。2一般树转化成二叉树转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。voidexchange()，classTree3先序遍历树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiNoderoot)。开始参数数组是否空或越界把数组的值赋给结点的数据域返回根指针结束返回空指针YN递归的给左子树赋值参数变为a[2i+1]递归的给右子树赋值参数变为a[2i+2]第4页共21页4后序遍历树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；voidPostOrder(BiNoderoot)。开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN第5页共21页5先序遍历树的非递归算法若二叉树为空，则空操作；否则（1）先将根节点进栈，在栈不为空时循环；(2)出栈p，访问*p若其右孩子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。6后序遍历树的非递归算法采用一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点，如此重复操作，直到栈空为止。7层次序的非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN第6页共21页三．详细设计1树的建立：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;2一般树转换成二叉树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;iT.count;i++){p[i]=GetTreeNode(T.node[i].data);}for(i=1;iT.count;i++){ip=&p[i];is=&p[j];while(T.node[i].parent!=is-data)第7页共21页{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)//非递归先序遍历{stackBinTree*s;BinTree*p=root;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-lchild;}第8页共21页if(!s.empty()){p=s.top();s.pop();p=p-rchild;}}}5.后序遍历树的递归算法voidinoeder(BTNode*T){if(T!=NULL){inoeder(T-firstchild);printf(%d,T-data);inoeder(T-rightsib);}}6后序遍历树的非递归算法voidpostOrder2(BinTree*root)//非递归后序遍历{stackBTNode*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;第9页共21页}else//第二次出现在栈顶{couttemp-btnode-data;p=NULL;}}}}7层次序树的非递归算法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;第10页共21页}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.因该程序对应不同的遍历定义了不同的结构，使每种结构的通用性降低，可以往在递归和非递归中使用同一种结构这一方面做进一步的思考。五．用户手册运行程序，首先出现主界面。主界面有七个选项。选项一、以双亲法创建一棵树。选项二、此选项可以对所创建的树采用递归算法进行前序遍历。选项三、此选项可以对所创建的树采用递归算法进行后序遍历。选项四、此选项可以对所创建的树采用非递归算法进行先序遍历。选项五、此选项可以对所创建的树采用非递归算法进行后序遍历。第11页共21页选项六、此选项可以退出程序。六．测试结果程序开始一般树转换成二叉树的情况第12页共21页副菜单选择：选择9继续操作运用各种遍历形式遍历树第13页共21页第14页共21页副菜单选择0结束程序第15页共21页七．附录（源程序）#includestdio.h#includemalloc.h#includestdlib.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