北航计软实验报告实验二.docx

《北航计软实验报告实验二.docx》由会员分享，可在线阅读，更多相关《北航计软实验报告实验二.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告二叉树实验名称班 学 姓 成级号名绩实验概述：【实验目的及要求】掌握二叉树的存储结构【实验原理】(1)二叉树的链式存储结构二叉树的每一个结点i有三个域：值域V (i),左链域L (i),右链域R (i)o分别用 三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。(2)按层次输出所有结点设置一个容量足够大的循环队列(可以用一个首尾相接的一维数组模拟)。初始时，将 根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出， 且依次将此结点的左右链指针入队。这个过程一直进行到队列空为止。设循环队列数组为 cq (1：m),其头尾指针分别为front与rear,则

2、按层次输出所有结点的算法如下：IF HBT = 0 THEN RETURN “THIS TREE IS EMPTY”Front rear- mADD (cq, HBT, front, rear)WHILE front 丰rear DO(DEL (cq, i, front ,rear )OUTPUT ( L，V,R (i)IF L(i)，0 THEN ADD (cq, L( i), front, rear)IF R(i)W0 THEN ADD (cq, R( i), front, rear)RETURN在这个算法中的ADD和DEL分别为入队和退队运算的两个过程，其算法(不考虑溢出情 况)如下：A

3、DD ( cq, i, front, rear)rear - rear + 1IF rear = m + 1 THEN rear _ 1cq (rear) - iRETURNDEL (cq, i, front, rear )front J front + 1IF front = m+ 1 THEN font _ 1i J cq (front)RETURN(3)输出所有叶子结点设置一个容量足够大的栈S (可以用一个一维数组模拟它，栈底在数组的第一个元素 处)。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出 次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退

4、出一个结点序号重新 进行这个过程，直至栈空为止。其算法如下：IF HBT = O THEN RETURN “THIS TREE IS EMTPY ”top. 0PUSH ( S, HBT, top)WHILE top W。DO(POP (S, i, top)IF (L (i) =0) and (R (i) =0) THEN OUTPUT V (i)ELSE (IF R (i) =0 THEN PUSH (S, R (i), top)IF L (i) 00 THEN PUSH (S, L (i), top)RETURN(4)将所有左右子树值交换这个问题的处理和输出所有叶子结点的问题很类彳以，只要

5、将非叶子结点的左右指针交换 即可，其算法如下：IF HBT = 0 THEN RETURN UTHIS TREE IS EMPTY” top . 0PUSH (S, HBT, top)WHILE top *0 DO (POP (S, i, top)IF (L (i) WO) or (R (i) *0) THEN (L (i) R (i)IF L (i) W0 THEN PUSH (S, L (i), top)IF R (i) =0 THEN PUSH (S, R (i), top) ) ) RETURN【实验环境】(使用的软硬件)硬件：PC 软件：VC+6.0实验内容:【实验方案设计】1 .对

6、给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2 .按层次输出所有结点。3 .输出所有叶子结点。4 .将所有左右子树值交换。【实验过程】（实验步骤、记录、数据、分析）（-）实验步骤1 .分别编制实验内容中题2、3、4的三个子程序。2 .以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3 .自行设计一棵二叉树，重复步骤2。4 .整理程序清单与所有结果，并写出实验报告。（二）程序清单#include#includestruct t

7、ree（int num;struct tree left;struct tree bright;；int a50=0;struct tree *build(int i)(struct tree *n;n=(struct tree)malloc(sizeof(struct tree);n-num=ai;if(a2*i!=0) n-left=build(2*i);elsen-left=NULL;if(a2*i+l!=0)n-right=build(2*i+1);elsen-right=NULL;retum(n);)struct tree *head;int build_binary_tree()(

8、FILE *fi;int i=l;char file_name20;printf(”请输入存放满二叉树数据的文件名称:“)； scanf(H%sH,file_name);fi=fopen(file_name,nrn);if(fi=NULL)(printf(文件读取失败，名为“%s”的文件不存在！ nfile_name); return(O); else( while(!feof(fi) (fscanf(fij%dt&ai); i=i+l;)fclose(fi);head=build(l);printf(文件读取成功，已用链式存储方式构建二叉树。) return(l);#define m 100

9、void add(struct tree *cq,struct tree *n,int upfront,int *prear)(*prear=*prear+l;if(*prear=m+l)*prear=l;cq*prear=n;)void del(struct tree *cq,struct tree *ptemp,int upfront,int *prear) (* pfron t=* pfront+1;if(*pfront=m+l)*pfront=l;*ptemp=cq Upfront;)void func_2(struct tree *head)(if(head=0)printf(此二叉

10、树为空! nn);else(struct tree *cqm,*temp,*ptemp二&temp;int front=m,rear=m,pfront=&front,*prear=&rear;printfC按层次输出所有节点:nn);add(cq,head,pfront,prear);while(front!=rear)(del(cq,ptemp,pfront,prear);printf(n%d,temp-num);if(temp-left!=NULL)(printf(左节点:d,temp-left-num);add(cq,temp-left,pfront,prear);)elseprintf

11、(无左节点)if(temp-right!=NULL)(printf(右节点:d”,temp-right-num);add(cq,temp-right,pfront,prear);)elseprintf(无右节点)printfC* ”)； printf(nnn); printf(nnH); ) )void push(struct tree *S,struct tree *n,int *ptop)(*ptop=*ptop+l; S*ptop=n;)void pop(struct tree *S,struct tree *ptemp,int *ptop)(*ptemp二S*ptop;*ptop=*p

12、top-l;)void func_3(struct tree *head)(if(head=0)printf(此二叉树为空! rT);else(int i=l;struct tree *Sm,*temp,*ptemp=&temp;int top=0,*ptop=⊤printf(”(3)此二叉树的所有叶子结点为:n”)；push(S,head,ptop);while(top!=0)(pop(S,ptemp,ptop);if(temp-left=NULL)&(temp-right=NULL) printf(n%dn,temp-num);else(if(temp-right!=NULL) p

13、ush(S,temp-right,ptop);if(temp-left! =NULL)push(S,temp-left,ptop);)printf(nnnn);)void func_4(struct tree *head)(if(head=0)printf(此二叉树为空! nn);else(int i=l;struct tree *Sm,*temp,*ptemp二&temp,exchange;int top=0,*ptop=⊤printf(执行所有左右子树值交换操作。n操作过程显示如下：n) push(S,head,ptop);while(top!=0)(pop(S,ptemp,pto

14、p);if(temp-left! =NULL) 11 (temp-right! =NULL)(exchange=temp-left;temp-left=temp-right;temp-right=exchange;printf(交换结点“ %d ”的左子树与右子树】emp-num);if(temp-left!=NULL)push(S,temp-left,ptop);if(temp-right! =NULL) push(S,temp-right,ptop);)printf(nnn);)func_2(head);)main()(int judge;while(l)(judge=build bina

15、ry tree();if(judge=l)(system(npause);func_2(head);func_3(head);func_4(head); break;(三)运行结果，青输入存放满二叉树数据的文件名称:tree .txt文件读取成功，已用链式存储方式构建二叉树。，psfHomeDoc5ients不啊啊大二上计psfHomeDocuments不啊啊大二上计软上机.0 1 口软上机实验shiyan2用作为当前目录阂以上路径启动了 CMD.EXE.UNC路径木受支持。默认值设为Windows目录。请按任意键继续. .(2)按层次输出所有节点：15左结点：98右结点：698左结点：2。右

16、结点：1。6左结点：45无右结点2。左结点：3。右结点：4。1。无左结点无右结点45无左结点右结：603。无左结点无右结点帆无左结点无右结点60左结点：70无右结点 再无左结点无右结点(3)此二叉树的所有叶子结点为: 30401070(4)执行所有左右子树值交换操作。操作过程显示如下：交换结点“15”的左子树与右子树交换结点 交换结点 交换结点 交换结点 交换结点“98”的左子树与右子树“20”的左子树与右子树 “6”的左子树与右子树“45”的左子树与右子树“60”的左子树与右子树(2)按层次输出所有节点: 15左结点：6右结点:98 6无左结点右结点：45 98左结点：1。右结点：2。 45左结点：6。无右结点 1。无左结点无右结点 2。左结点：4。右结点：3。 6。无左结点右结点：70 4。无左结点无右结点 3。无左结点无右结点 7。无左结点无右结点Press any key to continue【小结】通过本次试验,我掌握了掌握二叉树的存储结构，并且能够使用数组和链表存储二叉树, 掌握了按层次输出结点、输出叶子节点、将所有左右子树值交换等内容。指导教师评语及成绩:成绩:指导教师签名: 批阅日期：