二叉树实验报告-16

二叉树题目:二叉树遍历问题班级：2011级软件一班姓名：宁雪锋学号：1125115017完成日期：2012/11/25需求分析1)程序流程:定义一个二叉树，分别以btreenode*left，btreenode*right代表二叉树中的左右子树。从键盘读入一个字符串（广义二叉树）到数组中，并以该数组来建立二叉树首先判断二叉树非空，如果非空，则进行以下操作：先序递归与非递归遍历二叉树，输出访问到的元素中序递归与非递归遍历二叉树，输出访问到的元素后序递归与非递归遍历二叉树，输出访问到的元素按层遍历二叉树，输出访问到的元素清空二叉树，回收内存2)程序实现的功能通过递归与非递归的先中后三种遍历和一种层遍历来实现对输入的广义表的遍历输出，输出的形式为字符，和输入的形式相同3）测试数据：二．概要设计ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=空，则R=,称BinaryTree为空二叉树若D≠空，则R={H}H是如下二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱(2)若D-{root}≠空则存在D-{root}={D1,Dr}，且D1∩Dr=空(3)若D1≠空则D1中存在惟一的元素x1，<root，x1>∈H，且存在Dr上的关系Hr∈H；H={<root，x1>，<root，xr>，H1,Hr}基本操作:初始化置空二叉树initbtree(btreenode*&bt)通过输入的字符串（广义表）建立二叉树createbtree(btreenode*&bt,char*a)判断二叉树是否为空，输入类型为bool型emptybtree(btreenode*bt)递归先序遍历preorder(btreenode*bt)递归中序遍历inorder(btreenode*bt)递归后序遍历posorder(btreenode*bt)非递归先序遍历FxianBianli(btreenode*bt)非递归中序遍历FzhongBianli(btreenode*bt)非递归后序遍历FhouxuBianli(btreenode*bt)三、详细设计创建二叉树通过读取输入的字符串广义表，然后进行判断处理while(a[i]) { switch(a[i]){ case'': break;//空格不作任何处理 case'(': if(top==maxsize-1){ cout<<"栈空间太小，请增加maxsize的值！"<<endl; exit(1); } top++;s[top]=p;k=1; break; case')': if(top==-1){ cout<<"二叉树管广义表字符串错!"<<endl;exit(1); } top--; break; case',': k=2;break; default: p=newbtreenode; p->data=a[i]; p->left=p->right=NULL; if(bt==NULL)bt=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; }递归先序遍历如果二叉树非空if(bt!=NULL){ cout<<bt->data<<''; preorder(bt->left); preorder(bt->right); }递归后序遍历和中序遍历与递归先序遍历相似，在此不作详细说明非递归先序遍历使用栈的先进后出特性实现 do { while(p) { cout<<p->data<<""; if(p->right!=NULL) Stack[top++]=p->right; p=p->left; } if(top>=0) p=Stack[--top]; } while(top>=0);非递归中序遍历与先序遍历大同小异非递归后序遍历使用时得先定义需要的结构structTreeStack{ btreenode*link; intF;};这个较为复杂，参考于数据类丛书do { while(p) { stack[top++].link=p; stack[top].F=0; p=p->left; } if(top>0) { sign=stack[top].F; p=stack[--top].link; if(sign==0) { stack[++top].link=p; stack[top].F=1; p=p->right; } else { cout<<p->data<<""; p=NULL; } } } while(top>0);四、调试分析1.在调试过程中，个人推荐还是程序编写一个调试一个为好，方便找出错误2.对于inti；i<n；i++这种的变量，一定得细心编写，减少在这方面出错的概率，而且这地方出错有点让人忽略，浪费过多调试的时间3.对于非递归后序遍历，需要多编程加以熟悉，个人感觉比较难，像丛书给出的那样，心思一定要缜密才能写出那样的程序五、用户使用说明输入一个字符串，即广义表，例如a(b(,c),d(e,f))程序执行即可输出各种遍历的顺序输出六、测试结果输入：a(b(,c),d(e,f))输出：七、附录具体代码如下所示：#include<iostream>usingnamespacestd;typedefcharelemtype;structbtreenode{ elemtypedata; btreenode*left; btreenode*right;};voidinitbtree(btreenode*&bt){ bt=NULL;}voidcreatebtree(btreenode*&bt,char*a){ constintmaxsize=20; btreenode*s[maxsize]; inttop=-1; bt=NULL; btreenode*p; intk,i=0;//用k作为处理节点的左子树和右子树的标记 //k=1处理左子树，k=2处理右子树 while(a[i]) { switch(a[i]){ case'': break;//空格不作任何处理 case'(': if(top==maxsize-1){ cout<<"栈空间太小，请增加maxsize的值！"<<endl; exit(1); } top++;s[top]=p;k=1; break; case')': if(top==-1){ cout<<"二叉树管广义表字符串错!"<<endl;exit(1); } top--; break; case',': k=2;break; default: p=newbtreenode; p->data=a[i]; p->left=p->right=NULL; if(bt==NULL)bt=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; }}boolemptybtree(btreenode*bt){ returnbt==NULL;}//遍历算法voidpreorder(btreenode*bt){ if(bt!=NULL){ cout<<bt->data<<''; preorder(bt->left); preorder(bt->right); }}voidinorder(btreenode*bt){ if(bt!=NULL){ inorder(bt->left); cout<<bt->data<<''; inorder(bt->right); }}voidposorder(btreenode*bt){ if(bt!=NULL){ posorder(bt->left); posorder(bt->right); cout<<bt->data<<''; }}//非递归先序遍历voidFxianBianli(btreenode*bt){ inttop=0; btreenode*Stack[100],*p; p=bt; do { while(p) { cout<<p->data<<""; if(p->right!=NULL) Stack[top++]=p->right; p=p->left; } if(top>=0) p=Stack[--top]; } while(top>=0);}//非递归中序遍历voidFzhongBianli(btreenode*bt){ inttop=0; btreenode*Stack[100],*p; p=bt; do { while(p) { Stack[top++]=p; p=p->left; } if(top>0) { p=Stack[--top]; cout<<p->data<<""; p=p->right; } } while(top>0||top==0&&p);}//定义后序遍历所需结构structTreeStack{ btreenode*link; intF;};//非递归后续遍历voidFhouxuBianli(btreenode*bt){ inttop=0,sign; btreenode*p; TreeStackstack[100]; p=bt; do { while(p) { stack[top++].link=p; stack[top].F=0; p=p->left; } if(top>0) { sign=stack[top].F; p=stack[--top].link; if(sign==0) { stack[++top].link=p; stack[top].F=1; p=p->right; } else { cout<<p->data<<""; p=NULL; } } } while(top>0);}voidlevelorder(btreenode*bt){ constintmaxsize=30; //定义队列 btreenode*q[maxsize]; intfront=0,rear=0; btreenode*p; if(bt!=NULL){ rear=(rear+1)%maxsize; q[rear]=bt; } while(front!=rear){ front=(front+1)%maxsize; p=q[front]; cout<<p->data<<''; if(p->left!=NULL){ rear=(rear+1)%maxsize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%maxsize; q[rear]=p->right; } }} voidprintbtree(btreenode*bt){ if(bt!=NULL){ cout<<bt->data; if(bt->left!=NULL||bt->right!=NULL){ cout<<'('; printbtree(bt->left); if(bt->right!=NULL) cout<<","; printbtree(bt->right); cout<<")"; } }}voidclearbtree(btreenode*&bt){ if(bt!=NULL){ clearbtree(bt->left); clearbtree(bt->right); deletebt; bt=NULL; }}voidmain(){ btreenode*bt; initbtree(bt); charb[50];//存放二叉树广义表的字符数组 cout<<"输入二叉树用广义表表示的字符串："<<endl; cin.getline(b,sizeof(b));//从键盘输入字符串存放到数组b中 createbtree(bt,b); printbtree(bt);cout<<endl; cout<<"遍历输出如下所示\n"<<endl; cout<<"前序：";preorder(bt);cout<<end