数据结构实验五课程数据结构实验名称二叉树的建立及遍历第页专业班级学号姓名实验日期:年月日评分一、实验目的１．学会实现二叉树结点结构和对二叉树的基本操作。
２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二、实验要求1．认真阅读和掌握和本实验相关的教材内容。
2．编写完整程序完成下面的实验内容并上机运行。
3.整理并上交实验报告。
三、实验内容1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。
2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉树进行遍历。
四、实验步骤（描述实验步骤及中间的结果或现象。
在实验中做了什么事情，怎么做的,发生的现象和中间结果)第一题#ｉnｃlude "sｔdafx.ｈ"#include＂ｉoｓtｒeam.h"#inclｕde"sｔｄliｂ.h"＃incｌudｅ"ｓｔdiｏ.ｈ"#include<staｃk＞using namｅspace ｓtd;#ｄefiｎｅNUＬＬ０＃define ＯK １#dｅfinｅOVERＦＬOW -1ｔypeｄｅｆint Status;typeｄef ｓtｒｕｃt nｏde{chaｒdａta;ﻩsｔｒuct node *lｃhild;struct nodｅ*rchilｄ;}＊ｂｉtree;int k＝0;int deptｈ(ｂｉｔｒee T)／/树的高度｛ﻩif(！Ｔ)reｔurｎ0；elseﻩ{ﻩｉnｔm=depｔh（T->lchiｌd）;int n＝depth(T->ｒchild);ﻩｒeturn （m＞n?m:n)+1;}｝//先序,中序建树sｔrucｔnodｅ*cｒeaｔe(chａr ＊pre,char *orｄ,int n){ﻩstruct node*T；intｍ;T=NUＬL;ﻩｉｆ(n<=０)ﻩ{ﻩretuｒｎＮULL；｝ﻩelsｅﻩ{ﻩm=0;ﻩﻩT＝nｅw(ｓtruct ｎode);Ｔ->ｄaｔａ=*pre;ﻩT－>lchild=T->rcｈilｄ=NULL;ﻩwｈile(ｏrd［ｍ]！＝*ｐre)ﻩｍ++；T－>lcｈiｌd=create(prｅ＋1,ord，ｍ);ﻩＴ-＞rｃhild=ｃｒｅatｅ(pre+m＋１,orｄ+ｍ＋１，n-m-１）;ｒｅtｕｒn T;｝}/／中序递归遍历vｏiｄinorｄｅｒ（ｓtruct node *T){if(！Ｔ)ﻩｒetuｒn；ﻩｅlseﻩ{ﻩｉnorder(T－>lcｈild）；cout<<Ｔ->datａ；ﻩﻩinｏrder（T->rｃhiｌｄ);ﻩ}}vｏid iｎpre(struｃt nｏde ＊T){ﻩiｆ（!Ｔ）retｕrn;ｅlsｅﻩ{ﻩﻩｃout<<T-＞data;inpre(T－>lchild）;ｉｎpre(Ｔ-＞rｃｈild ）；ﻩﻩﻩ}}voiｄｐoｓtｏrder(struct noｄe *T）{ｉf(!T)ﻩreturn;ﻩeｌｓｅﻩ{postoｒdｅｒ（Ｔ->lcｈiｌｄ)；ﻩｐｏstｏrｄｅr （T－＞rchiｌｄ); ﻩﻩcｏut<＜Ｔ->dａta;ﻩ}}/／先序非递归遍历ｖｏiｄinpｒe1（sｔｒuct node *T){ﻩstrucｔnｏdｅ*p;ﻩstrｕcｔnｏｄe *stack[２0]；iｎt toｐ=0;p=T;couｔ<<＂非递归先序";wｈile（ｐ｜|top!=０){ﻩﻩwｈｉlｅ（p)ﻩﻩ{ﻩstａck[tｏp+＋]=p；coｕｔ＜<p－＞data;ﻩﻩp＝p->lｃhild;ﻩ}ﻩﻩp=sｔacｋ[--top];ﻩﻩp＝p->rｃhild ；}}/／中序非递归遍历void inoｒder１(ｓtruｃt node ＊T) {ﻩstｒuct noｄｅ*p;ﻩstｒｕcｔnoｄe＊stack[2０];ﻩinｔｔｏｐ=0；p＝Ｔ;ﻩcｏut<＜"非递归中序";ﻩwｈilｅ(p｜|top!=０)ﻩ{wｈｉlｅ(p)ﻩ{staｃk［top+＋]＝p；ﻩﻩｐ＝ｐ->lchiｌd ;ﻩ}ﻩp＝sｔａｃk[-－tｏp]；cout＜<p->datａ;ﻩﻩｐ=p－>rcｈiｌd；ﻩ｝}／/主函数ｉnｔmain（）{ﻩｂiｔｒee T;cｈar pre[3０]，ｏrd[30］;ﻩｉｎｔｎ,ｍ;ｇets(prｅ);ﻩgets(ord）;n＝strlen（pｒｅ）;ﻩT=creatｅ(pｒe,ｏrｄ，ｎ);iｎpre(T）;ﻩcoｕt<<enｄｌ;ﻩpostｏrdeｒ(Ｔ);ｃout<<endl；inorder(T)；cｏut<<endl;inｐre1(T);ﻩcout<<ｅｎdl;inorder１(T）;cｏut<＜ｅnｄｌ；ｍ=dｅpｔh（T)；ｃｏｕt＜<＂二叉树高度为："<<m<<eｎdl;ﻩrｅｔurn ０；}第二题：#incｌudｅ＂ｓtdaｆｘ.h"#inｃlｕde＂iostｒｅam.h"#inｃｌuｄe"stdｌｉb．h＂#ｉncluｄe"ｓtdio.ｈ"＃inｃｌudｅ<stａcｋ>using nａmｅspace std;#define NＵLL 0#definｅOK １#definｅOVEＲFLOＷ-1typedef ｉｎｔStatus;typedeｆstruct nodｅ｛ﻩｃhar ｄata;ﻩsｔruct ｎｏde *lｃhild;sｔｒucｔnｏdｅ*rchild;}*bitｒｅe；Staｔus Create(bitｒee&Ｔ) //按先序次序输入二叉树中结点的值,！表示空树{cｈarｅ;coｕt<<"输入树的元素:"＜<ｅnｄｌ;cｉn＞>ｅ；if(e=＝＇!') T=NULL;eｌseﻩ｛if（!(Ｔ＝（noｄｅ*）ｍaｌｌoｃ(sizeｏf(node)）)) ﻩｅｘit(OVEＲFLOW);ﻩＴ->datａ=e;Crｅate（T->lchilｄ)；ﻩﻩCreａtｅ(T->rｃｈｉld)；}retｕrn OK;}//先序非递归遍历voiｄｉnpre（struct noｄe *T)｛sｔruｃt nｏde*p;ﻩｓtｒuｃt ｎoｄe *ｓtａck[2０];inｔｔop=0;ﻩp＝T;ｃｏuｔ＜<"非递归先序"；while(p｜|top！=0）ﻩ｛ﻩﻩwhile (p)ﻩﻩ{ﻩﻩstａck[top++]=p;ﻩｃout<<p－>ｄａtａ;ﻩﻩﻩp=p->lcｈｉｌd；ﻩﻩ}ﻩp=sｔack[－－tｏp］；ﻩﻩﻩp=p->rcｈiｌd ;ﻩ}}//主函数inｔmain()｛ﻩbiｔrｅe T；Create(Ｔ);cout<＜"输出的元素为："＜<endl;ﻩiｎｐre（T)；ｒetｕrn 0;｝五实验结果第一题:输入先序为-＋a*b％cd／ef 输入后序为ａ+ｂ*c%ｄ-e/f 得出结果:输入先序为abcd输入后序为bacｄ得出结果：第二题：六实验总结1 为什么头文件只用#incｌude <iｏsｔream> ｕｓiｎg ｎａmespacｅ std;不行,要把所写到的程序中所包含的头文件头写进去。
于是就在想,反正以后不管这些头文件有没用到头写进去,省得一大堆麻烦。
2 用先序建树的时候虽然只要输入一个字符串，但是要判断空树的情况。
比较麻烦。
我个人觉得用先序与中序联合建树比较简单。
因为这样只要输入先序与中序就可以建树了。
3对于三种遍历的过程,要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。
至于非递归的三种遍历,中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子,直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。
而非递归的先序遍历基本可以和中序一样，建立一个队列,在进栈的时候队列也进同样的元素，但是不与栈一起出栈。
而是在最后进栈出栈结束的时候,对队列进行出队列操作即可。
4 二叉树对于进行表达式的前缀，中缀和后缀的表示有明显的优势，既方便，又容易理解。
其先序,中序和后序分别对应这表达式的前缀，中缀和后缀。
５在建树与进行树的遍历的时候一定要理解其建树与遍历的整个过程。
不然就会连为什么这样做都不知道。
在遍历树的时候最常用到的就是栈的结构了（非递归)。
七:思考与提高1.如何计算二叉链表存储的二叉树中度数为1的结点数？答:ｉnt countleaｆ（bｉtree t，ｉｎt couｎｔ){ｉf（!(t－>lchｉlｄ） &&(ｔ->rｃhｉld）count++;ｅｌse if ((t->lchild）＆＆!(ｔ－＞ｒcｈiｌd))counｔ＋+;couｎｔlｅａf(ｔ－>lchild）;couｎtleaf(t->ｒchilｄ);rｅturn ｃｏunt;}2．已知有—棵以二叉链表存储的二叉树，rｏot指向根结点，ｐ指向二叉树中任一结点,如何求从根结点到p所指结点之间的路径?答:vｏid ｆoundp（bitreｅｔ){ｉf(t＝=p)｛Puｓh(ｓ，t->data);Ｐop(s，ｔ-＞daｔａ)；}foｕｎdp(t->lｃhilｄ);fｏｕndｐ(t->rchid）;}。