北航计软实验报告实验二

实验报告实验名称二叉树级_______班号______学名_____姓绩成实验概述【实验目的及要求】掌握二叉树的存储结构【实验原理】1二叉树的链式存储结构二叉树的每一个结点有三个域值域左链域右链域分别用三个一维数i Vi,L i,R io组表示它们，并用头指针指向二叉树的根结点HBT2按层次输出所有结点设置一个容量足够大的循环队列可以用一个首尾相接的一维数组模拟初始时，将根结点序号入队然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队这个过程一直进行到队列空为止设循环队列数组为cq1m,其头尾指针分别为与则按层次输出所有结点的算法如下front rear,IF HBT=0THEN RETURN“THIS TREEIS EMPTY”Front rear-mADD cq,HBT,front,rear丰WHILE frontrear DODELcq,i,front,rear⑴，⑴OUTPUTL V,R i，IF Li0THEN ADDcq,L i,front,rearIF RiW0THEN ADDcq,R i,front,rearRETURN在这个算法中的和分别为入队和退队运算的两个过程，其算法不考虑溢出情况ADD DEL如下ADDcq,i,front,rearrear-rear+1IF rear=m+1THEN rear_1cq rear-iRETURNDEL cq,i,front,rear frontJ front+1IF front=m+1THEN font_1i Jcq frontRETURN输出所有叶子结点3设置一个容量足够大的栈可以用一个一维数组模拟它，栈底在数组的第一个元素处S具体过程是从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止其算法如下IF HBT=O THEN RETURN“THIS TREEIS EMTPY”top.0PUSHS,HBT,topWHILE topW DOPOPS,i,topIF L i=0and R i=0THEN OUTPUTV iELSEIF R i=0THEN PUSH S,Ri,topIF L i00THEN PUSHS,L i,topRETURN将所有左右子树值交换4这个问题的处理和输出所有叶子结点的问题很类彳以，只要将非叶子结点的左右指针交换即可，其算法如下IF HBT=0THENRETURNUTHIS TREEIS EMPTY”top.0PUSHS,HBT,topWHILE top*0DO POPS,i,topIF Li WOor Ri*0THEN Li—R iIFLiW0THEN PUSHS,Li,topIF Ri=0THEN PUSHS,Ri,topRETURN【实验环境】使用的软硬件硬件软件PC VC++

6.0实验内容:【实验方案设计】对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算

1..按层次输出所有结点2输出所有叶子结点

3.将所有左右子树值交换

4.【实验过程】（实验步骤、记录、数据、分析）（-）实验步骤分别编制实验内容中题、、的三个子程序

1.234以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序

2.（）输入二叉树用链式结构存储；1（）调用题的子程序，并输出结果；22（）调用题的子程序，并输出结果；33（）调用题的子程序，并输出结果；44自行设计一棵二叉树，重复步骤

3.2整理程序清单与所有结果，并写出实验报告

4.

（二）程序清单#includestdio.h#includestdlib.hstruct tree（int num;struct treeleft;struct treebright;}；int a

[50]={0};struct tree*buildint istruct tree*n;n=struct tree^mallocsizeofstruct tree;n-num=a[i];ifa[2*i]!=0n-left=build2*i;elsen-left=NULL;ifa[2*i+l]!=0n-right=build2*i+1;elsen-right=NULL;retumn;struct tree*head;int build_binary_treeFILE*fi;int i=l;char file_name

[20];printf”请输入存放满二叉树数据的文件名称:“；scanfH%sH,file_name;fi=fopenfile_name,nrn;if fi=NULL文件读取失败，名为“的文件不存在！printf%s”\n\file_name;returnO;}else while!feoffi fscanffij%dta[i];i=i+l;fclosefi;head=buildl;文件读取成功，已用链式存储方式构建二叉树printf returnl;#define m100void addstruct tree**cq,struct tree*n,int upfront,int*prear*prear=*prear+l;if*prear==m+l*prear=l;cq[*prear]=n;void delstruct tree**cq,struct tree**ptemp,int upfront,int*prear*pfron t=*pfront+1;if*pfront==m+l*pfront=l;*ptemp=cq[Upfront];void func_2struct tree*headifhead==0printf此二叉树为空!\nn;else二struct tree*cq[m],*temp,**ptemp temp;int front=m,rear=m,^pfront=front,*prear=rear;printfC⑵按层次输出所有节点:\nn;addcq,head,pfront,prear;whilefront!=reardelcq,ptemp,pfront,prear;printfn%d,,temp-num;iftemp-left!=NULL左节点％printf:d,temp-left-num;addcq,temp-left,pfront,prear;else无左节点printfiftemp-right!=NULL右节’点％printf:d”,temp-right-num;addcq,temp-right,pfront,prear;else无右节点printfprintfC**”；printfn\nn;}printfn\nH;void pushstruct tree**S,struct tree*n,int*ptop*ptop=*ptop+l;S[*ptop]=n;void popstruct tree**S,structtree**ptemp,int*ptop二*ptemp S[*ptop];*ptop=*ptop-l;void func_3structtree*headifhead==0此二叉树为空!printf\rT;elseint i=l;structtree*S[m],*temp,**ptemp=temp;int top=0,*ptop=top;此二叉树的所有叶子结点为:；printf”3\n”pushS,head,ptop;whiletop!=0popS,ptemp,ptop;iftemp-left==NULLtemp-right==NULL printfn%dn,temp-num;elseiftemp-right!=NULL pushS,temp-right,ptop;iftemp-left!=NULLpushS,temp-left,ptop;printfn\n\nn;void func_4structtree*headifhead==0printf此二叉树为空!\nn;elseint i=l;二structtree*S[m],*temp,**ptemp temp,exchange;int top=0,*ptop=top;⑷执行所有左右子树值交换操作操作过程显示如下printf\n\n pushS,head,ptop;whiletop!=0popS,ptemp,ptop;iftemp-left!=NULL11temp-right!=NULLexchange=temp-left;temp-left=temp-right;temp-right=exchange;交换结点的左子树与右子树】printf“%d”emp-num;iftemp-left!=NULLpushS,temp-left,ptop;iftemp-right!=NULL pushS,temp-right,ptop;}printfn\nn;func_2head;mainint judge;whileljudge=build binarytree;ifjudge=lsystemnpause;func_2head;func_3head;func_4head;break;三运行结果，青输入存放满二叉树数据的文件名称:tree.txt文件读取成功，已用链式存储方式构建二叉树，不啊啊大二上计\\psf\Home\Doc5ients\\\psf\Home\Documents\不啊啊\大二上计软\上机….01口软上机实验\shiyan2用作为当前目录阂以上路径启动了CMD.EXE.路径木受支持默认值设为目录UNC Windows请按任意键继续.•.按层次输出所有节点2左结点右结点15986左结点右结点9821左结点无右结点645左结点右结点234无左结点无右结点1无左结点右结45£60无左结点无右结点3帆无左结点无右结点左结点无右结点再无左结点无右结点6070执行所有左右子树值交换操作4操作过程显示如下交交换换结结点点“15”的的左左子子树树与与右右子子树树“98”交换结点的左子树与右子树“20”交换结点的左子树与右子树“6”交换结点的左子树与右子树“45”交换结点的左子树与右子树“60”此二叉树的所有叶子结点为:330401070按层次输出所有节点:左结点右结点无左结点右结点左结点右结点左结点无右2156:986459812456结点无左结点无右结点左结点右结点无左结点右结点无左结点无右结点无左结点无124367043右结点无左结点无右结点7Pressanykey tocontinue【小结】通过本次试验,我掌握了掌握二叉树的存储结构，并且能够使用数组和链表存储二叉树,掌握了按层次输出结点、输出叶子节点、将所有左右子树值交换等内容指导教师评语及成绩:成绩:指导教师签名:批阅日期。