53二叉树的遍历以及树与二叉树的转换课程设计

课程设计（数据结构）院、系专业姓名学号指导教师2010年月日树的应用摘要：关键词：树；二叉树；转换；遍历；递归和非递归1．实验题目实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。2．实验分析2．1总体分析2.1.1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。2.1.2本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。2.1.3本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。2.2具体分析2.2.1二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1的值存入左孩子，为2*i+2的存入右孩子。BiNodecreat()，BiNodestree_creat(char*a,intk)。2.2.2先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiNoderoot)。2.2.3中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。voidInOrder(BiNoderoot)。2.2.4后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；voidPostOrder(BiNoderoot)。2.2.5先序非递归算法BiNode根指针，若BiNode!=NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取BiNode的右子树的根指针？voidF_PreOrder(BiNoderoot)2.2.6中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNode指针？voidF_inOrder(BiNoderoot)。2.2.7后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。voidF_PostOrder(BiNoderoot)。2.2.8层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。2.2.9树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。voidexchange()，classTree.3.实验步骤3.1流程图图1、二叉树的创建开始参数数组是否空或越界把数组的值赋给结点的数据域返回根指针结束返回空指针YN递归的给左子树赋值参数变为a[2i+1]递归的给右子树赋值参数变为a[2i+2]图2、前序递归遍历开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN图3、中序递归遍历开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图4、后序递归遍历开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图5、前序非递归遍历开始申请一个BiNode数组inttop=0判断结点是否空输出结点值s[++top]=root结点的值变为它的左孩子判数组是否空root=s[top--]root=root-rchild结束判数组或结点是否空NYNYN图6、中序非递归遍历开始申请一个BiNode数组]inttop=0判断结点是否空s[++top]=root结点的值变为它的左孩子判数组是否空输出结点值root=s[top--]root=root-rchild结束判数组或结点是否空NYYNNY开始申请一个StackElemType数组用一个临时变量存根的信息数组标志致零s[top].ptr=pp=p-lchildtop++判数组标志致是否为一数组标位致一p=s[top-1].ptrp=p-rchild结束NYYNYYN判数组是否空判树是否空输出结点的数据N判数组是否空图7、后序非递归遍历图8、层序遍历3.2代码：#includeiostreamusingnamespacestd;#includestdlib.h#includemath.h#definemaxsize100#includetree.h#defineLENsizeof(structbtree)intmax=1;typedefstructbtree//二叉树节点结构体{开始申请一个BiNode数组s[]申请两个整形变量数组首元赋为根结点s[2*i+1]=root-lchild；s[2*i+2]=root-rchildi++root=s[i]max=i输出数组结束N判断树是否空Ybtree*lchild,*rchild;chardata;}*BiNode;typedefstructStackElemType//栈的结构体{BiNodeptr;intflag;}StackElemType;BiNodep;//二叉树的建立BiNodestree_creat(char*a,intk){BiNoderoot;max++;if(a[k]=='\0'||kmaxsize)returnNULL;//判断树是否为空else{root=(BiNode)malloc(LEN);//动态申请节点root-data=a[k];root-lchild=stree_creat(a,2*k+1);//递归调用为左孩子赋值root-rchild=stree_creat(a,2*k+2);//递归调用为右子赋值returnroot;//返回根节点指针}}voidprint(BiNoderoot)//输出所创建的二叉树{BiNodeh[maxsize]={NULL};inttop=0,base=0,j=0,k=0,n=0,m=0;h[top]=root;j=log(max+1)/log(2)-1;if(pow(2,j+1)-1max)j++;cout你刚输入的是:\n;while(h[base]!=NULL)//把二叉树的值依次存入数组{h[++top]=h[base]-lchild;h[++top]=h[base]-rchild;base++;}for(top=0;h[k]!=NULL;top++)//按层输出{m=pow(2,j)-top;//计算每行输出的空格数if(top!=0)m=m-top;for(n=0;nm;n++)cout;for(base=0;basepow(2,top)&&h[k]!=NULL;base++)//控制每层输出的个数{if(h[k]-data=='0')cout[];//当为空时输出[]elsecouth[k]-data;k++;}cout\n;for(n=0;n(m-1);n++)cout;for(base=0;basepow(2,top)&&h[k]!=NULL;base++)cout/|;cout\n;}}//二叉树的后序遍历递归算法voidPostOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{PostOrder(root-lchild);PostOrder(root-rchild);if(root-data=='0');elsecout[root-data];}}//二叉树的中序遍历递归算法voidInOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{InOrder(root-lchild);if(root-data=='0');elsecout[root-data];InOrder(root-rchild);}}//二叉树的前序递归遍历算法voidPreOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{if(root-data=='0');elsecout[root-data];PreOrder(root-lchild);PreOrder(root-rchild);}}//二叉树的前序遍历非递归算法voidF_PreOrder(BiNoderoot){BiNodes[maxsize];//申请一个BiNode数组inttop=0;//采用顺序栈，并假定不会发生上溢do{while(root!=NULL)//当结点不为空时{if(root-data=='0');elsecout[root-data];s[++top]=root;//依次将结点压入栈root=root-lchild;//根赋值为它的左孩子}if(top0)//当节点为空但栈顶不为零时{root=s[top--];栈顶下移把栈顶元素负给根结点root=root-rchild;根赋值为它的右子}}while(root!=NULL||top0);}//中序非递归遍历算法voidF_inOrder(BiNoderoot){BiNodes[maxsize];//申请一个BiNode数组inttop=0;//采用顺序栈，并假定不会发生上溢do{while(root!=NULL)//当结点不为空时{s[++top]=root;//依次将结点压入栈root=root-lchild;//根赋值为它的左孩子}if(top0)//当节点为空但栈顶不为零时{root=s[top];把栈顶元素负给根结点if(root-data=='0');elsecout[root-data];//输出根结点root=s[top--];栈顶下移把栈顶元素负给根结点root=root-rchild;根赋值为它的右子}}while(root!=NULL||top0);}//后序非递归遍历算法voidF_PostOrder(BiNoderoot){;申请一个StackElemType数组BiNodep=root;inttop=0;do{while(p!=NULL)//当结点不为空时{s[top].flag=0;//标记位负为零s[top].ptr=p;//将树的结点依次压入栈中p=p-lchild;//树沿左子树下移top++;}while(s[top-1].flag==1)//当栈的最上面元素标记位为一时输出{if(s[top-1].ptr-data=='0')top--;elsecout[s[--top].ptr-data];}if(top0)//当节点为空但栈顶不为零时{s[top-1].flag=1;栈的最上面元素标记位赋值为一p=s[top-1].ptr;栈的最上面元素树结点赋给pp=p-rchild;树沿右子树下移}}while(top0);}//层序遍算法voidLevelOrder(BiNoderoot){BiNodes[maxsize];//申请一个BiNode数组intmax,i=0;s[0]=root;//数组首元赋为根结点while(root!=NULL)//当结点不空时{s[2*i+1]=root-lchild;//左孩子赋给下标为2*i+1的数组员s[2*i+2]=root-rchild;//右孩子赋给下标为2*i+1的数组员i++;root=s[i];//root变为当前数组元素的值max=i;}for(i=0;imax;i++){if(s[i]-data=='0