数据结构实验报告之二叉树(终极版本)

《数据结构》实验报告姓名系别班级学号实验日期指导教师实验成绩周娟信息学院电子2班102002072012-4-26王政霞实验三二叉树需求分析一、实验目的1、掌握二叉树的基本运算和遍历算法的实现2、掌握树形结构的特点，二叉树的存储方式以及相应操作二、实验内容按先序遍历序列建立二叉树的二叉链表，已知先序序列为(F表示空格)：ABCFFDEFGFFFFFF。并写一个函数treenodes()统计该二叉树的节点个数。如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。概要设计1>抽象数据结构类型二叉树的定义:ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=Φ，则R=Φ,称BinaryTree为空二叉树；若D≠Φ，则R={H},H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1，Dr}，且D1∩Dr=Φ；（3）若D1≠Φ，则D1中存在唯一的元素X1，<root，X1>属于H，且存在Dr上的关系Hr属于H；H={<root，X1>，<root，Xr>,H1,Hr};(4)(D，{H1}）是一棵符合本定义的二叉树，称为根的左子树，(Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子数。基本操作：InitBiTree(&T)操作结果：构造空二叉树T。DestroyBiTree(&T)初始条件：二叉树T已存在。操作结果：销毁二叉树T。GreateBiTree(&T,definition)初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree{&T};初始条件：二叉树T存在。操作结果：将二叉树t清空。BiTreeEmpty(T)初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE,否则返回FALSE.BiTreeDepth(T)初始条件：二叉树T存在。操作结果：返回T的深度。Root(T)初始条件：二叉树T已存在。操作结果：返回T的根。LeftBiTree&（T，e)初始条件：二叉树T存在，e是T中某个节点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightBiTree(T，e)初始条件：二叉树T已存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。PreOrderTraverse（T,Visit（））初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：先序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。InOrderTraverse（T,Visit（））初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：中序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。PostOrderTraverse（T,Visit（））初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：后序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。LevelOrderTraverse（T,Visit（））初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：层序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。}ADTBinaryTree2>各程序模块之间的层次关系图：主程序模块主程序模块从键盘输入二叉树的先序序列从键盘输入二叉树的先序序列 调用递归先序遍历调用递归先序遍历函数模块实现先序遍历调用递归中序遍历函数模块实现中序遍历调用递归中序遍历函数模块实现中序遍历调用递归后序遍历函数模块实现后序遍历调用递归后序遍历函数模块实现后序遍历调用层次遍历函数判断结点数调用层次遍历函数判断结点数详细设计#include"stdio.h"#include"stdlib.h"#include"malloc.h"1、二叉树的定义typedefcharTElemType;typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode;2、队列的定义typedefstructQNode{ BiTNodedata; structQNode*next;}Queue;typedefstruct//队列的头指针和尾指针{Queue*front; Queue*rear;}LinkQueue;intJT=0;3、先序建立二叉树BiTNode*CreateBiTree(){TElemTypech; BiTNode*T; scanf("%c",&ch); if(ch=='') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0); T->data=ch; JT++; T->lchild=CreateBiTree();//建立左子树 T->rchild=CreateBiTree();//建立右子树 } returnT;}4、初始化队列intInitQueue(LinkQueue*Q){ Q->front=Q->rear=(Queue*)malloc(sizeof(Queue)); if(!Q->front) exit(0); Q->front->next=NULL; return1;}intEnQueue(LinkQueue*Q,BiTNodee)//向队列中插入元素{ Queue*p; p=(Queue*)malloc(sizeof(Queue)); if(!p) exit(0); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return1;//插入成功返回1}5、出队intDeQueue(LinkQueue*Q,BiTNode*e){ Queue*p; if(Q->front==Q->rear)//队列为空 return0; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return1;}6、判断队列是否为空队列intEmptyQueue(LinkQueue*Q){ if(Q->rear==Q->front) return1; else return0;}7、队列的层次遍历voidLevelTraverse(BiTNode*T){ LinkQueueQ; BiTNode*p; InitQueue(&Q); EnQueue(&Q,*T); p=T; while(!EmptyQueue(&Q)) {DeQueue(&Q,p); printf("%c",p->data); if(p->lchild) EnQueue(&Q,*p->lchild); if(p->rchild) EnQueue(&Q,*p->rchild); }}8、递归先序遍历voidPreOrderTraverse(BiTNode*btn){if(btn!=NULL){printf("%c",btn->data);PreOrderTraverse(btn->lchild);PreOrderTraverse(btn->rchild);}}9、递归中序遍历voidInOrderTraverse(BiTNode*btn){if(btn!=NULL){InOrderTraverse(btn->lchild);printf("%c",btn->data);InOrderTraverse(btn->rchild);}} 10、递归后序遍历voidPostOrderTraverse(BiTNode*btn){if(btn!=NULL){PostOrderTraverse(btn->lchild);PostOrderTraverse(btn->rchild);printf("%c",btn->data);}}11、主函数main(){ BiTNode*btn; printf("\n输入二叉树空节点输“”：\n"); btn=CreateBiTree(); printf("\n递归先序遍历二叉树的结果:\n"); PreOrderTraverse(btn);//递归先序遍历建立的二叉树printf("\n递归中序遍历二叉树的结果:\n");InOrderTraverse(btn);printf("\n递归后序遍历二叉树的结果:\n");PostOrderTraverse(btn); printf("\n二叉树的结点数为:%d\n",JT);//二叉树结点的数目 printf("\n层次遍历二叉树的结果:\n"); LevelTraverse(btn); printf("\n");}调试分析：由于开始对二叉树存储的知识还不熟识，在建立二叉链表和二叉树的遍历出现了很多问题。3、在使用二叉树的遍历时，有时因为自己的粗心，把指针的位置弄错了。4、做本程序用到了指针的知识，有时一有不懂的东西又只能打开书来看。5、开始时没有把二叉树的左右子树情况考虑全面，导致咋遍历的时候出现了一些错误。用户使用说明本程序的运行环境为MicrosofeV