二叉树的基本操作实验

《二叉树的基本操作实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验三二叉树的基本运算、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容［问题描述］建立一棵二叉树，试编程实现二叉树的如下基木操作：1.按先序序列构造一棵二叉链表表示的二叉树T；2.对这棵二叉树进行遍历：先序、屮序、后序以及层次遍历，分别输出结点的遍历序列；3.求二叉树的深度/结点数目/叶结点数目；（选做）4.将二叉树每个结点的左右子树交换位置。（选做）从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），［测试数据］如输入：ABC*（i）DE（i）G（i）（J）（J）（其中巾表示空格字符）则输出结果为先序：A

2、BCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG［选作内容］采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。一实验分析本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。二概要设计功能实现1.intCreatBiTree(BiTree&T)用递归的方法先序建立二叉树，并用链表储存该二叉树2.intPreTravel(BiTree&T)前序遍历3.intMidTravcl(BiTrcc&T)屮序遍历4

3、.intPostTravel(B订ree&T)后序遍历5.intDepth(BiTree&T)//计算树的深度6.inthowmuch(B订reeT,inth)采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。7.intexchang(BiTree&T)交换左右子树，利用递归，当有左右孩子时才交换三详细设计#include#includetypedefstructBiTNode{chardata;structBiTNode*lchild,*rchil

4、d;}BiTNode,*BiTree;intCreatBiTree(BiTree&T){//先序法创建二叉树charch;if((ch=getchar())==,')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)exit(l);T->data=ch;CreatBiTree(T->lchild);CreatBfTree(Torchild);}return0;}intPreTravel(BiTree&T){//前序遍历if(T){printf(n%c'T->data);PreTravel(T->1chiId);PreTrav

5、el(T->rchild);}return0;}intMidTravel(BiTree&T){//屮序遍历if(T){MidTravel(T->lchild);printf("%c'T->data);MidTravel(T->rchild);}return0;1intPostTravel(BiTree&T){//后序遍历if(T){PostTravel(T->lchild);PostTravel(T->rchild);printf("%c'T->data);inthowmuch(B汀「eeTJnth){BiTNode*Q[1001;//树节点指针数组，用于存放遍历到的元素地址if

6、(T==NULL)print”空的二叉树”)；Q[0]=T;//存入树根inti,k=0;intj=l;//j为总节点for(i=0;ilchild!=NULL)//如果有左孩子,存入地址,j加一,否则没操作{QUJ=Q[i]->lchild;j++；}if(Q[i]->rchild!=NULL)//如果有右孩子,存入地址，j加一，否则没操作{QUl=Q[il->rchild；j++；}if(Q[i卜>lchild==NULL&&Q[i卜>「chi1d==NULL)k++;〃计算叶子数}if(h==O)printf(n%dH,j);elseif(

7、h==l)printf(“％d”,k);elseif(h==2){for(i=0;idata);}else{printfC参数错误”);}return0;}intDepth(BiTree&T)〃计算树的深度intIh,rh;if(NULL==T)else{Ih=Depth(T->lchild);rh=Depth(T->rchild);return(lh>rh?lh:rh)+1;}}intexchang(Bi