当前位置:范文大全 > 调查报告 > 2020年新版树和二叉树实验报告 二叉树实验分析

2020年新版树和二叉树实验报告 二叉树实验分析

时间:2021-10-15 13:21:57 浏览次数:

精品资料

 精品资料

 树和二叉树

 、实验目的掌握二叉树的结构特征,以及各种存储结构的特点及适用范围。

 掌握用指针类型描述、访问和处理二叉树的运算。

 、实验要求

 认真阅读和掌握本实验的程序。

 上机运行本程序。

 保存和打印出程序的运行结果,并结合程序进行分析。

 按照二叉树的操作需要,重新改写主程序并运行,打印出文件清单和运 行结果。

 、实验内容

 输入字符序列,建立二叉链表。

 按先序、中序和后序遍历二叉树(递归算法)。

 按某种形式输出整棵二叉树。

 求二叉树的高度。

 求二叉树的叶节点个数。

 交换二叉树的左右子树。

 借助队列实现二叉树的层次遍历。

 在主函数中设计一个简单的菜单,分别调试上述算法。

 为了实现对二叉树的有关操作,首先要在计算机中建立所需的二叉树。

 建立 二叉树有各种不同的方法。一种方法是利用二叉树的性质 5来建立二叉树,

 输入数据时要将节点的序号(按满二叉树编号)和数据同时给出: (序号,

 数据元素0)。另一种方法是主教材中介绍的方法,这是一个递归方法,与 先序遍历有点相似。数据的组织是先序的顺序,但是另有特点,当某结点的 某孩子为空时以字符“#”来充当,也要输入。若当前数据不为“#”则申请一 个结点存入当前数据。递归调用建立函数,建立当前结点的左右子树。

 四、 解题思路

 1、 先序遍历:O访问根结点,G先序遍历左子树,C3先序遍历右子树

 2、 中序遍历:O中序遍历左子树,C2访问根结点,。中序遍历右子树

 3、 后序遍历:O后序遍历左子树,C2后序遍历右子树,C3访问根结点

 4、 层次遍历算法:采用一个队列 q,先将二叉树根结点入队列,然后退队列, 输出该结点;若它有左子树,便将左子树根结点入队列;若它有右子树,便将右 子树根结点入队列,直到队列空为止。因为队列的特点是先进后出,所以能够达 到按层次遍历二叉树的目的。

 五、 程序清单

 #in clude<stdio.h>

 #in clude<stdlib.h>

 #defi ne M 100

 typedef char Etype; //定义二叉树结点值的类型为字符

 型

 //树结点结构typedef struct BiTNode

 //树结点结构

 Etype data;

 struct BiTNode *lch,*rch;

 }BiTNode,*BiTree;

 BiTree que[M];

 int fron t=0,rear=0;

 //函数原型声明

 BiTNode *creat_bt1();

 BiTNode *creat_bt2();

 void preorder(BiTNode *p);

 void ino rder(BiTNode *p);

 void postorder(BiTNode *p);

 void enq ueue(BiTree);

 BiTree delqueue();

 void levorder(BiTree);

 int treedepth(BiTree);

 void prtbtree(BiTree,i nt);

 void excha nge(BiTree);

 in t leafco un t(BiTree);

 void pain tleaf(BiTree);

 BiTNode *t;

 int coun t=0;

 //主函数

 void mai n() {

 char ch;

 int k;

 do{

 prin tf("\n\n\n");

 prin tf("\n=================== 主菜单===================");

 prin tf("\n\n 1.建立二叉树方法 1");

 prin tf("\n\n 2.建立二叉树方法 2");

 prin tf("\n\n 3?先序递归遍历二叉树”);

 prin tf("\n\n 4?中序递归遍历二叉树”);

 prin tf("\n\n 5.后序递归遍历二叉树”);

 printf("\n\n 6.层次遍历二叉树”);

 prin tf("\n\n 7.计算二叉树的高度”);

 prin tf("\n\n 8.计算二叉树中叶结点个数 ”);

 prin tf("\n\n 9.交换二叉树的左右子树 ”);

 printf("\n\n 10.打印二叉树”);

 printf("\n\n 0.结束程序运行”);

 prin tf("\n============================================");

 printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");

 printf("

 printf("二叉树的叶结点为:");pai ntleaf(t);

 精品资料

 {printf("后序遍历二叉树

 {printf("后序遍历二叉树:");

 精品资料

 sea nf("%d",&k);

 switch(k)

 {

 case 1:t=creat_bt1( );break; //调用性质5建立二叉树算法

 case 2:pri ntf("\n 请输入二叉树各结点值:");fflush(stdi n);

 t=creat_bt2();break; //调用递归建立二叉树算法

 case 3:if(t)

 {printf("先序遍历二叉树:");

 preorder(t);

 prin tf("\n");

 }

 else printf(” 二叉树为空!\n");

 break;

 case 4:if(t)

 {printf("中序遍历二叉树:");

 ino rder(t);

 prin tf("\n");

 }

 else printf("二叉树为空!\n");

 break;

 case 5:if(t)

 postorder(t);

 prin tf("\n");

 }

 else printf(” 二叉树为空!\n");

 break;

 case 6:if(t)

 {printf("层次遍历二叉树:");

 levorder(t);

 prin tf("\n");

 }

 else printf("二叉树为空! \n");

 break;

 case 7:if(t)

 {printf("二叉树的高度为:%d",treedepth(t));

 prin tf("\n");

 }

 else printf("二叉树为空! \n");

 break;

 case 8:if(t)

 {printf("二叉树的叶子结点数为: %d\n",leafcount(t));

 prin tf("\n");

 精品资料

 精品资料

 printf("\n再见!按回车键,返回…

 printf("\n再见!按回车键,返回… \n");

 精品资料

 else printf(” 二叉树为空! \n");

 break;

 case 9:if(t)

 {printf("交换二叉树的左右子树: \n");

 excha nge(t);

 prtbtree(t,0);

 prin tf("\n");

 }

 else printf("二叉树为空! \n");

 break;

 case 10:if(t)

 \n");{printf("逆时针旋转90度输出的二叉树:

 \n");

 prtbtree(t,0);

 prin tf("\n");

 }

 else printf("二叉树为空! \n");

 break;

 case 0:exit(0);

 } //switch

 }while(k>=1 &&k<=10);

 ch=getchar();

 } //main

 //利用二叉树性质 5,借助一维数组 V建立二叉树

 BiTNode *creat_bt1()

 { BiTNode *t,*p,*v[20];i nt i,j;Etype e;

 /*输入结点的序号i、结点的数据e*/

 printf("\n请输入二叉树各结点的编号和对应的值(如 1,a):");

 sca nf("%d,%c",&i,&e);

 while(i!=0&&e!='#') {

 p=(BiTNode*)malloc(sizeof(BiTNode));

 p->data=e;

 p->lch=NULL;

 p->rch=NULL;

 v[i]=p;

 if(i==1)

 t=p; //序号为1的结点是根

 else

 {

 j=i/2;

 //当i

 //当i为0, e为#时,结束循环

 //序号为偶数,作为左孩子

 else v[j]_>rch=p;

 //序号为奇数,作为右孩子

 }

 printf("\n请继续输入二叉树各结点的编号和对应的值: ”);

 scan f("%d,%c",&i, &e);

 }

 return(t);

 }//creat_bt1;

 //模仿先序递归遍历方法,建立二叉树

 BiTNode *creat_bt2()

 {

 BiTNode *t;

 Etype e;

 scan f("%c", &e);

 if(e==' #')t=NULL; //对于#值,不分配新结点

 else{

 t=(BiTNode *)malloc(sizeof(BiTNode));

 t->data=e;

 t->lch=creat_bt2();

 //左孩子获得新指针值

 return(t);

 t->rch=creat_bt2();

 //右孩子获得新指针值

 } 〃creat_bt2

 //先序递归遍历二叉树 void preorder(BiTNode *p)

 {if(P){

 prin tf("%3c",p->data);

 preorder(p_>lch); preorder(p->rch);

 }

 } //preorder

 〃中序递归遍历二叉树

 void ino rder(BiTNode *p)

 {if(p){

 ino rder(p->lch);

 prin tf("%3c",p->data);

 ino rder(p->rch);

 }

 } //ino rder

 //后序递归遍历二叉树

 void postorder(BiTNode *p)

 { if(p){ postorder(p->lch);

 postorder(p->rch);

 prin tf("%3c",p->data);

 }

 } //postorder void enq ueue(BiTree T)

 {

 if(fron t!=(rear+1)%M)

 {rear=(rear+1)%M;

 que[rear]=T;}

 }

 BiTree delqueue()

 {

 if(fron t==rear)return NULL;

 fron t=(fro nt+1)%M;

 return(que[fro nt]);

 }

 //层次遍历二叉树

 //层次遍历二叉树

 {

 BiTree p;

 if(T)

 {enq ueue(T);

 while(fro nt!=rear){

 p=delqueue( );

 prin tf("%3d",p->data);

 if(p->lch!=NULL)e nqueue(p->lch); if(p->rch!=NULL)e nq ueue(p->rch);

 }

 }

 } int treedepth(BiTree bt)

 {

 int hl,hr,max;

 if(bt!=NULL)

 { hl=treedepth(bt->lch); hr=treedepth(bt->rch); max=(hl>hr)?hl:hr; return (max+1);

 }

 else return (0);

 } void prtbtree(BiTree bt,i nt level)

 形

 {int j;

 if(bt)

 //计算二叉树的高度〃

 //计算二叉树的高度

 〃逆时针旋转90度输出二叉树树

 for(j=0;j<=6*level;j++)pri ntf(" ”);

 prin tf("%c\n",bt->data);

 prtbtree(bt->lch,level+1);

 }

 }

 void excha nge(BiTree bt) // 交换二叉树左右子树

 {BiTree p;

 if(bt)

 {p=bt->lch;bt->lch=bt->rch;bt->rch=p;

 excha nge(bt->lch);excha nge(bt->rch);

 }

 }

 in t leafcou nt(BiTree bt) // 计算叶结点数

 {

 if(bt!=NULL)

 {leafc oun t(bt->lch);

 leafc oun t(bt->rch);

 if((bt->lch==NULL) &&(bt->rch==NULL))

 coun t++;

 }

 return(co unt);

 void pai ntleaf(BiTree bt) // 输出叶结点 {if(bt!=NULL)

 {if(bt->lch==NULL&&bt->rch==NULL)

 prin tf("%3c",bt->data);

 pain tleaf(bt->lch);

 pain tleaf(bt->rch);

 }

 }

 图11.2所示二叉树的输入数据顺序应该是: abd#g###ce#h##f##

 图11.2 二叉树示意图

 运行结果:

 =================王采单

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 1

 请输入二叉树各结点的编号和对应的值(如 1,a): 1,a

  TOC \o "1-5" \h \z 请继续输入二叉树各结点的编号和对应的值: 2, b

 请继续输入二叉树各结点的编号和对应的值: 3,c

 请继续输入二叉树各结点的编号和对应的值: 4,d

 请继续输入二叉树各结点的编号和对应的值: 6,e

 请继续输入二叉树各结点的编号和对应的值: 7,f

 请继续输入二叉树各结点的编号和对应的值: 9,g

 请继续输入二叉树各结点的编号和对应的值: 13,h

 请继续输入二叉树各结点的编号和对应的值:

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 3

 先序遍历二叉树:abdgcehf

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 4

 中序遍历二叉树:

 dgbaehcf

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 5

 后序遍历二叉树:

 gdbhefca

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 6

 层次遍历二叉树: 97 98 99100101102103104

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 7

 二叉树的高度为:4

 ”);王采单

 ”);

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 8

 二叉树的叶子结点数为:3

 二叉树的叶结点为: g h f

 ===================王采单

 ");

 建立二叉树方法 1

 建立二叉树方法 2

 先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 9

 交换二叉树的左右子树:

 d

 g

 b

 a

 e

 h

 c

 ===================王采单

 ");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 10

 逆时针旋转90度输出的二叉树:

 d

 g

 b

 a

 e

 h

 c

 ”);王采单

 ”);

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 2

 请输入二叉树各结点值: abd#g###ce#h##f##

 ===================主菜单===================");

 建立二叉树方法 1

 建立二叉树方法 2

 3?先序递归遍历二叉树

 4?中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 0.结束程序运行

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 0

 请按任意键继续 ?

 六、 调试心得及收获

 建立二叉树有两种方法:一种方法是利用二叉树的性质 5来建立二叉树;另一种 方法是主教材中介绍的方法,这是一个递归方法,与先序遍历有点相似。建立后, 通过先序、中序、后序遍历,对二叉树有了进一步的理解与掌握。对二叉树中各 种计算也更了解了!

 七、 其他所想到的一个二叉树,有许多部分构成,每一个部分都需要精心编写,才能对其进行操作, 不至于出错

 Welcome To

 Download !!!

 欢迎您的下载,资料仅供参考!