数据结构二叉树实验报告

1、数据结构实习题目二二叉树及其操作尹星晨（0806230331）一、问题描述利用先序建立一棵二叉树，数据以字符串形式从键盘输入。在此二叉树上完成如下操作：必做：（1 ）实现二叉树的前序、中序、后序遍历。（2 ）求出二叉树叶子结点的数目。（3 ）求二叉树的树高。（4 ）完成二叉树的左右子树交换，输出交换后的前序、中序遍历序列。选做：（1 ）给出二叉树的非递归后序遍历。（2 ）将二叉树扩充为中序线索树，写出非递归的中序遍历。（3 ）已知在两个数组中分别有前序和中序遍历序列，试建立该二叉树。二、算法描述1、整体思路：S1:建立二叉树；S2:递归遍历该二叉树；S3:二叉树的相关操作；S4:非递归后续遍历

2、；S5:中序线索化及输出；S6:由数组中的序列建立二叉树且输出；2、细节描述：1） 先序创建二叉树默认为键盘输入，当输入# 时，输入结束；当输入 时当前结点为空；当输入其他字符时，该字符保存入 当前结点的数据域。void C reate_B hTree （B hTree 灯）（charch;chch7 从键盘接收输入字符ifda3=ch;键盘接收的字符保存入数据域Create_B hTree（&.递归方法创建左孩子结点Create_B hTree & （*T）-rchHd）;#递归方法创建右孩子结点#创建结束2） 递归方法遍历二叉树以下涉及的遍历方法均采用递归遍历，非递归的先序，中序，后序遍历

3、将在第四小节中涉及。void NR_PreO ider(B inTree T)void NR_hO ider hTree T)void NR_PosK) xder hTiee T)/非递归方法的先序遍历w非递归方法的中序遍历0非递归方法的后序遍历若T树非空则遍历if(r)if(r)cout data力先序遍历NR_MOider(T -上 hfld);NR.PosiOider(r-i:hid);NR.PreO iderCT今上hM)递归cout(rchid);NR_PreO ider(T今：rchM)递归NR_M0 ider(T-rchiH);couKT-data力后序遍历)3） 二又树相关操作

4、这里涉及的关于二叉树的相关操作的方法均采用递归法a)计算二叉树叶子结点数目htLeafl11um (BhTree T)M计算二叉树T叶子结点数若树t非空则开始计算递归计算以左孩子结点为根的叶子数递归计算以右孩子结点为根的叶子数if +n=0)return 1 只有根结点else return m +n返回左右孩子的叶子总数/else return 0;/树空返回 0b) 求二叉树树高htHeight hTree T)M求二叉树T的高度高度为0ifCT=NULL) else(hthefeht=H ejght(r-khid)y递归法求以左孩子为根的树的高度htriie jght=H eightCr

5、rchild)递归法求以右孩子为根的树的高度返回最大值为树的高度若一边为空则无法交换return 1+ (hehtiheht? height: efeht)y7c)二叉树左右子树交换void exchange (B hTree T)M二叉树左右子树交换if(Tthid=NULL & Trchiii=NULL) return ehe(BhTreeXode *temp=NULL7定义临时结点铺助交换tem p=T-child;TkhiH=T-rchiH;交换左右结点Trchild=tem p;递归交换左孩子ifCTf 上hfld) exchange (r-ch2d)4递归交换右孩子4） 非递归后序

6、遍历采用栈辅助实现非递归后序遍历void PostO rder(B hTree T)用非递归后序遍历stack s;BhTreeXode *cur= T,visited = NULL;while ( s.em ptyO cur != NULL )whit (cur != NULL )s.push (cur);cur= cur-Ichiki;)cur= s.top 0;if(cuiSrchikl = visited currrchild = NULL ) coutKdata;s.popO;visited = cur;cur=NULL;)eke cur= currchiH;5)中序线索化typed

7、ef sttuctB hThiN ode chardata;structBhThiNode *rchiH;ht Itag.rtag;B hThiN ode,5 hThfTree ;B hThfTree pre;void C reat_B hThrTree hTree *T,B hlhrTree *p)(if(r)*p= (B jiThrTree)m albc (sEeofS hThiNode);而Hda1a=(*T)-data;C reat_B hThrTree 律T)-khiH,p);C reat_B hThrTree (& (*T)rchii,p);void hthread IB hThr

8、Tree p)中序线索化二叉树战)h thread(plchiH);iflp-l:hild) p-hag=0;else p-hag=l;if331chiH) p-rtag=0;else pHrtag=l;iflprc)if(prertag=l)pre-rch2d=p;if(p-liag=l)p7child=pre;6)pre=P；h thread rchild);B hThiTree hsucc hThfTree p)M寻找P结点的后继if(p-vrtag=l)retum prchild;efce(p=p-rchiki;white itag=O)p=p-khild;return p;void

9、T_hO ider hThrTree T)区中序遍历线索化后的二叉树B hThfTree p=T ;if)white(p-liag=0) p=pHkhild;do (coutdata;p=hsucc);whfle (p);由数组中已有的前序。中序序列建立二叉树void sete hTreeN ode p,char pre D,char h Q,htpl,intql,htp2,iitq2)为I,ql,p2,q2 分别为数组前序，中序的边界p=new BhTreeNode;p-data=pre (pl;建立根结点，输入数值htp2;while(iit!=prei)l)廿+;中序数组后移ifl:hi

10、d,pre,ii,pl + l,pl+vp2p2,t-l);递归iftt=q2)prchii=N U LL ; 无右子树ehe set(p-rchiH,pre,h,pl + rp2 + l,ql,ttl,q2);递归三、程序结构1 数据结构；typedef structB iiTreeN ode (E em Type data H 数据区structB inTreeN ode *lchild,*rchild J/ B hTreeN ode,*B nTree ;左右孩子结点typedef strictB hThiN ode / char data ; /数据区中序线索化时定义的结点左右孩子结点s

11、tmctB iiThiN ode * 1chiId, * rchild ; / int hag,rtag J1 标志B hThiN ode邓 hThrTree ;2、函数调用结构:Creat BinThrTreeInsucc T InOrderR PreOrder3、函数功能说明:功能区函数名功能描述创建二叉树C reate_B inTree 0创建二叉树（采用先序建立二叉树）遍历T raversalO递归遍历二叉树N R _P reO iderQ递归遍历二叉树_先序N R _ JiO iderQ递归遍历二叉树_中序N R_PostO rderO递归遍历二叉树_后序操作0 peiatbn 0二叉树基本操作Leaf*I um 0计算二叉树叶子结点数目H e 鱼ht。计算二叉树的树高Exchang Oe交换二叉树左右子树非递归R_PostO nderO非递归遍历二叉树_后序中序线索化C reat-B riThrTree 0创建修改后的含有标记的二叉树In thread 0中序线索化nsucc 0寻找当前结点的后继结点T_tiO iderO非递归遍历二叉树_中序由数组创建TxFiAnay 0由数组创建二叉树四