资源描述：
《用递归算法遍历二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途实验二用递归算法遍历二叉树[实验目的]学习掌握二叉树各种遍历方法的基本操作算法。［实验内容］建立一棵二叉树,并用递归算法分别用前序、中序和后序遍历之。[实验要点及说明]由于二叉树的定义是递归的,因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息,也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。前序遍历二叉树的操作定义为：若二叉树为空，则空操作;
2、否则（1）访问根结点；（2）前序遍历左子树；（3)前序遍历右子树。中序遍历二叉树的操作定义为：若二叉树为空,则空操作；否则(1)中序遍历左子树;(２）访问根结点；(3）中序遍历右子树。后序遍历二叉树的操作定义为：若二叉树为空,则空操作;否则(1）后序遍历左子树;(2）后序遍历右子树；(３)访问根结点。[实验要求与步骤］1．基本要求：采用递归算法实现前序、中序和后序遍历；2．测试数据:个人收集整理勿做商业用途1．实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点,使每个结点被访问一次且只被访问一次；2．按要求编写程序;3．上机
3、录入程序，并进行编辑、编译、调试，直到运行成功。[参考程序]#ｉｎclｕde＜ｓｔdio.h>＃ｄefine nｕll ０iｎｔcountｅｒ=0;ｔｙｐｅdefstruｃtｂtreenｏｄe{ｉnt ｄata;structbｔreenode＊lchｉld;sｔrｕｃｔ btrｅｅnoｄe＊rchild；｝ｂnode;bnoｄｅ*p;bnｏｄe *creａt(intx，bnode*lbt，ｂnodｅ *rbt)｛bｎｏde＊ｐ;p=(bnodｅ*)malloｃ（sizeof(bｎode）);p->dａｔａ＝x;ｐ->lｃhiｌｄ＝lb
4、t；p－＞rｃhilｄ=rbt;retｕｒn(p）;｝ｂnode*iｎs_lchild（ｂｎode*p,intx){ｂnodｅ＊q;ｉf（ｐ==null)priｎtf（"Ｉlleｇaliｎserｔ.");ｅlse{q＝(bnode*)malloｃ（sｉｚeｏf(bｎode））;q-＞datａ=x；q->ｌchiｌd＝ｎull;q->ｒchｉｌd=ｎulｌ;iｆ(p－>lｃhilｄ!=nｕll)q－＞rcｈｉｌｄ=p－>ｌｃhilｄ;p-＞lchｉld=q；｝个人收集整理勿做商业用途｝bnode*ins_rchilｄ（bnoｄe*p,ｉ
5、nt ｘ）{bnoｄe*q;if（p==nuｌl)printｆ(＂Ｉlｌegalinｓert.");else{q＝(bnode*)malｌoc(siｚeof(bnｏｄe）);q->ｄａta=x;q->ｌchild=null;q->rchilｄ=null；ｉf（ｐ->rｃhｉｌd!＝ｎｕll)ｑ－>ｌcｈild=p-＞ｒｃhild;p－>ｒchｉｌd＝q;}}ｖoidｐrorｄｅr（bnodｅ*p){if(p==null)returｎ；printf（"％dt%uｔ%dt％u＼ｔ%ｕ＼n",++countｅr,p,ｐ->ｄａｔa,p
6、-＞lchｉｌｄ,p->rchild)；if(p－>lcｈild!＝ｎull）pｒoｄer(ｐ->lｃｈiｌd);iｆ(p-＞rｃｈｉｌd!=nuｌl)proder(ｐ-＞rchｉld)；}vｏidpreordeｒ(bnｏde*p）{ｉf(p==nuｌｌ）return;ｐrｉnｔf(＂%d",ｐ->data)；if(p->ｌcｈild!＝ｎulｌ）pｒeoder(ｐ－＞lcｈild);if(p->rchild!=null)pｒｅｏｄeｒ（p－>rcｈiｌd);}voiｄ inordｅr（bｎode＊p){if(p==nｕll)reｔu
7、rｎ；ｉf(ｐ－>lchilｄ！=null)ｉnｏder(p-＞ｌｃhiｌｄ);prｉｎtf（＂%d"，ｐ-＞datａ);if（p－>ｒchｉlｄ!=ｎull)ｉｎｏdｅｒ(ｐ-＞ｒchild)；}vｏidｐostｏｒder(bnode＊p){iｆ(p==nuｌl)个人收集整理勿做商业用途return;if（ｐ->lchilｄ！＝null)postoder(p－>ｌchｉｌd)；iｆ(p->ｒchｉld!=nｕｌl)postｏder(p-＞rchｉld);ｐrintｆ("%d",p－>dａｔa)；}ｍaｉn(）｛ｂnｏde*bt,＊ｐ
8、,*q;ｉｎｔx;priｎｔf("Iｎpuｔroot:");scanf("%d",&ｘ);ｐ=crｅａt（x，nuｌl,nuｌl);bt=ｐ;ｓｃａnf("%d",&x）;wｈiｌe（x!=－1）{ｐ＝bｔ;q=p；wi
