数据结构实验指导书06

1实验六树与二叉树6.1实验目的：（1）掌握二叉树链表的结构和二叉树的建立过程；（2）掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能力。6.2实验要求：（1）复习课本中有关树与二叉树的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。6.3基础实验[实验1]二叉树的构造实验内容与要求:按先序序列构造一棵二叉链表表示的二叉树T；分析:二叉树是每个结点至多只有两棵子树，并有左、右之分，顺序不能任意颠倒的一种非线性结构。二叉树常用的存储结构是二叉链表形式，二叉链表由一个数据项data（用于存放结点的值）和两个指针项lchild、rchild（分别指向该结点的左、右子树）。结点及结构如图6-1所示：//------二叉树的二叉链表存储表示模型-------typedefstructBiTNode{TElemTypedata;StructBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;将此结构定义放在一个头文件BiTNode.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出二叉链表的初始化及常量的定义。实现提示按先序序列建立一棵二叉树，先构造根结点，再构造根的左、右子树；每一棵子树又都是一颗二叉树，所以构造一棵子树的过程与构造整棵二叉树的过程完全相同，按照先序序列，先构造根，再构造左子树，然后构造右子树；采用递归形式直到叶子结点为止。以下是算法描述：StatusCreateBiTree(BiTree&T)//按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树，//构造二叉链表表示的二叉树T。lchilddatarchild图6-1含有两个指针的二叉树的结点及结构datalchildrchild2scanf(&ch);if(ch=='＃')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;//生成根结点CreateBiTree(T-lchild);//生成左子树CreateBiTree(T-rchild);//生成右子树}returnOK;}//CreateBiTree参考程序：//头文件BiTNode.h的内容如下：#includestdio.h#includestdlib.h#includemalloc.h#defineMAX20#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT){charch;scanf(%c,&ch);if(ch=='#')T=NULL;/*#代表空指针*/else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)exit(OVERFLOW);/*申请结点*/T-data=ch;/*生成根结点*/T-lchild=CreateBiTree(T-lchild);/*构造左子树*/T-rchild=CreateBiTree(T-rchild);/*构造右子树*/}//以下是主程序shiyan6_1_1.c#includeBiTNode.hmain(){BiTreeT=NULL;3printf(\n请读入构造二叉树的字符序列：);CreateBiTree(T);/*建立一棵二叉树T*/}[实验2]二叉树的遍历实验内容与要求:对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍历和层序遍历并分别输出遍历的结点顺序。分析：二叉树的先序遍历是：若二叉树为空，则空操作；否则，访问根结点，先序遍历左子树，先序遍历右子树。二叉树的中序遍历是：若二叉树为空，则空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。二叉树的后序遍历是：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树；访问个结点。二叉树的层序遍历是：在访问二叉树的结点时按照自上而下，从左至右的顺序。根作为第一层，根的孩子作为第二层，以此类推。先序遍历二叉树递归算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦visit()失败，则操作失败。if(T){if(Visit(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild，Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse中序遍历的递归算法StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(InOrderTraverse(T-rchild，Visit))if(Visit(T-data))4if(InOrderTraverse(T-rchild，Visit))returnOK;returnERROR;}elsereturnOK;}//InOrderTraverse后序遍历递归算法StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(PostOrderTraverse(T-lchild,Visst))if(PostOrderTraverse(T-rchild，Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse层次遍历二叉树的非递归算法StatusLevelOrder(BiTreeT){//按层次遍历二叉树T，Q为队列InitQueue(Q);If(T!=NULL){//若树非空EnQueue(Q,T);//根结点入队列While(!QueueEmpty(Q)){DeQueue(Q,b);//队首元素出队列Visit(b-data);//访问结点If(b-lchild!=NULL)EnQueue(Q,b-lchild);//左子树非空，则入队列If(b-rchold!=Null)EnQueue(Q,b-rchild);//右子树非空，则入队列}//while}//if}LevelOrder参考程序：//以下代码保存在文件shiyan6_1_2.c#includestdio.h#includeBiTNode.hStatusPrintElement(TElemTypee){printf(%2c,e);5returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){inti,j,k;if(T==NULL)returnOK;else{i=Visit(T-data);if(i){j=PreOrderTraverse(T-lchild,Visit);/*先序遍历左子树*/if(j){k=PreOrderTraverse(T-rchild,Visit);/*先序遍历右子树*/if(k)returnOK;}}elsereturnERROR;}}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*中序遍历*/if(T){if(InOrderTraverse(T-lchild,Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*后序遍历*/if(T){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}6voidLevleOrder(BiTreeT){/*层次遍历二叉树T，从第一层开始，每层从左到右*/BiTreeQueue[MAX],b;/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/intfront,rear;front=rear=0;if(T)/*若树非空*/{Queue[rear++]=T;/*根结点入队列*/while(front!=rear){/*当队列非空*/b=Queue[front++];/*队首元素出队列，并访问这个结点*/printf(%2c,b-data);if(b-lchild!=NULL)Queue[rear++]=b-lchild;/*左子树非空，则入队列*/if(b-rchild!=NULL)Queue[rear++]=b-rchild;/*右子树非空，则入队列*/}}}/*LevelOrder*/voidmain(){BiTreeT=NULL,B;printf(\n请读入构造二叉树的字符序列:);B=CreateBiTree(T);/*建立一棵二叉树T*/printf(\n该二叉树的先序遍历是:);PreOrderTraverse(B,PrintElement);/*先序遍历二叉树*/printf(\n该二叉树的中序遍历);InOrderTraverse(B,PrintElement);/*中序遍历二叉树*/printf(\n该二叉树的后序遍历);PostOrderTraverse(B,PrintElement);/*后序遍历二叉树*/printf(\n该二叉树的层次遍历是:);LevleOrder(B);/*层次遍历二叉树*/getchar();}}[实验3]叶子结点统计实验内容与要求：统计一棵二叉树的叶子结点的个数分析：叶子结点是二叉树中既没有左孩子又没有有孩子的结点。采用递归方式。求一棵二叉树的叶子结点数的递归模型如下。f(bt)=0;若为空树时7f(bt)=1;若只有根结点时,该根结点是叶结点f(bt)=f(btree-lchild)+f(btree-rchild);其它参考程序：#includestdio.h#includeBiTNode.hintleafcount(BiTreebt){/*统计二叉树bt中叶子结点数*/intn;if(bt==NULL)n=0;elseif(bt-lchild==NULL&&bt-rchild==NULL)n=1;elsen=leafcount(bt-lchild)+leafcount(bt-rchild);/*二叉树叶子结点数等于左、右子树的叶子结点数之和*/returnn;}voidmain(){BiTreeT=NULL;intm;printf(\n请输入要构造二叉树的结点序列:);T=CreateBiTree(T);/*建立一棵二叉树T*/m=leafcount(T);printf(叶子结点数是:%d,m);getchar