二叉树的基本操作实验.doc

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

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

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

3、)前序遍历3.intMidTravel(BiTree&T)中序遍历4.intPostTravel(BiTree&T)后序遍历5.intDepth(BiTree&T)//计算树的深度6.inthowmuch(BiTreeT,inth)采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。H=0printf("%d",j)h==1真printf("%d",k)h==2for(i=0;idata)printf("参

4、数错误")真真真假假假假7.intexchang(BiTree&T)交换左右子树，利用递归，当有左右孩子时才交换三详细设计#include#includetypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intCreatBiTree(BiTree&T){//先序法创建二叉树charch;if((ch=getchar())=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTN

5、ode));if(!T)exit(1);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}return0;}intPreTravel(BiTree&T){//前序遍历if(T){printf("%c",T->data);PreTravel(T->lchild);PreTravel(T->rchild);}return0;}intMidTravel(BiTree&T){//中序遍历if(T){MidTravel(T->lchild);printf("%c",T->data);MidTra

6、vel(T->rchild);}return0;}intPostTravel(BiTree&T){//后序遍历if(T){PostTravel(T->lchild);PostTravel(T->rchild);printf("%c",T->data);}return0;}inthowmuch(BiTreeT,inth){BiTNode*Q[100];//树节点指针数组，用于存放遍历到的元素地址if(T==NULL)printf("空的二叉树");Q[0]=T;//存入树根inti,k=0;intj=1;//j为总节点for(i=0;i

7、){if(Q[i]->lchild!=NULL)//如果有左孩子，存入地址，j加一，否则没操作{Q[j]=Q[i]->lchild;j++;}if(Q[i]->rchild!=NULL)//如果有右孩子，存入地址，j加一，否则没操作{Q[j]=Q[i]->rchild;j++;}if(Q[i]->lchild==NULL&&Q[i]->rchild==NULL)k++;//计算叶子数}if(h==0)printf("%d",j);elseif(h==1)printf("%d",k);elseif(h==2){for(i=0;i

8、f("%c",Q[i]->data);}else{printf("参数错误");}return0;}intD