《二叉树基本操作实验报告》

1596021563962第1页共27页《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算学院：化学与材料科学学院专业班级：09级材料科学与工程系PB0920603姓名：李维谷学号：PB09206285邮箱：[e-mail]指导教师：贾伯琪实验时间：2010年10月17日1596021563962第2页共27页一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3深度5宽度2非空子孙数6度为2的数目2度为1的数目21596021563962第3页共27页查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3深度4宽度3非空子孙数7度为2的数目2度为1的数目3查找10，失败。删除B后，以广义表形式打印A（，C（F（，G）））二、概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。1、设定“二叉树”的抽象数据类型定义：ADTBiTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D，则R，称BiTree为空二叉树；若D，则HR，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若,rootD则存在,,rlDDrootD且rlDD;（3）若,lD则lD中存在唯一的元素lx,,,Hxrootl且存在lD上的关系;HHl若,rD则rD中存在唯一的元素rx,,,Hxrootr且存在rD上的关系rlrlrHHxrootxrootHHH,,,,,;；（4）llHD,是一棵符合本定义的二叉树，称为根的左子树，rrHD,是一棵符合本定义的二叉树，称为根的有字树基本操作：CreateBiTree&T)操作结果：按照T的定义构造一个二叉树。BiTreeDepth(&T)初始条件：二叉树T已存在。操作结果：返回T的深度。1596021563962第4页共27页BiTreeWidth(&T)初始条件：二叉树T已存在。操作结果：返回T的宽度。PreOderTraverse&T)初始条件：二叉树T已存在。操作结果：先序遍历打印T，InOderTraverse(&T)初始条件：二叉树T已存在。操作结果：中序遍历打印T。PostOderTraverse(&T)初始条件：二叉树T已存在。操作结果：后序遍历打印T。LevelTraverse(&T)初始条件：二叉树T已存在。操作结果：层次遍历T。DeleteXTree(&T,TElemTypex)初始条件：二叉树已存在。操作结果：删除元素为x的结点以及其左子树和右子树。CopyTree(&T)初始条件：二叉树T已存在。操作结果：以T为模板，复制另一个二叉树。｝ADTBiTree2、设定队列的抽象数据类型定义：ADTQueue{数据对象：D={ia},NiBiTreeai数据关系：R1={1,iiaa|1ia,Dai,i=2,…，n}约定1a端为队列头，na端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。EnQueue(&Q,&e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q)初始条件：队列Q已存在。操作结果：删除Q的对头元素，并返回其值。QueueEmpty(&Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回1，否则0。}ADTQueue3、本程序包含四个模块1596021563962第5页共27页1）主程序模块voidmain(){初始化；先序输入二叉树各结点元素；各种遍历二叉树；对二叉树进行常见运算；复制二叉树；在复制的二叉树上进行二叉树的常见操作；｝2）二叉树模块——实现二叉树的抽象数据类型和基本操作2）队列模块——实现队列的抽象数据类型及今本操作3）广义表打印模块——以广义表形式打印二叉树4）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数三、详细设计1、主程序中需要的全程量#defineM10//统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度2、队列的建立与基本操作typedefstructQNode{BiTreedata;//队列中存储的元素类型structQNode*next;//指向二叉树结点的指针}QNode,*Queueptr;typedefstruct{Queueptrfront;//队列的队头指针Queueptrrear;//队列的队尾指针}LinkQueue;算法描述：为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到队列。而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。伪码算法：voidInitQueue(LinkQueue*Q){//初始化队列申请一个结点Q-front=Q-rear=(Queueptr)malloc(sizeof(QNode));if(!Q-front)exit(1);//存储分配失败处理Q-front-next=NULL;//构成带头结点里的空链队列}voidEnQueue(LinkQueue*Q,BiTreee){//插入元素为e为Q的队尾元素Queueptrq;q=(Queueptr)malloc(sizeof(QNode));if(!q)1596021563962第6页共27页exit(1);q-data=e;q-next=NULL;Q-rear-next=q;//元素e的结点入列Q-rear=q;}BiTreeDeQueue(LinkQueue*Q){//从队列中删除队头元素，并直接返回给调用的主函数Queueptrp;BiTreeq;if(Q-front==Q-rear){//队列为空printf(ERROR!\n);exit(1);}p=Q-front-next;q=p-data;Q-front-next=p-next;//删除该结点if(Q-rear==p)Q-rear=Q-front;free(p);returnq;//返回队头元素}intQueueEmpty(LinkQueue*Q){//检查队列是否为空，若为空则返回真值，否则返回0if(Q-front==Q-rear)return1;elsereturn0;}3、二叉树的建立与基本操作typedefstructBiTNode{TElemTypedata;//二叉树结点存储的元素类型structBiTNode*lchild,*rchild;//二叉树左右孩子指针}BiTNode,*BiTree;算法分析：二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。1）二叉树的遍历算法描述：二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因1596021563962第7页共27页此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。伪码算法：voidPreOderTraverse(BiTreeT){//采用二叉链表存储结构if(T){putchar(T-data);//最简单的访问结点法，输出结点元素，这里先访问根结点PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);}}中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。伪码算法：voidInOderTraverse(BiTreeT){//采用二叉链表存储结构if(T){InOderTraverse(T-lchild);//先遍历左子树putchar(T-data);//最简单的访问结点法，输出结点元素，这里第二访问根结点InOderTraverse(T-rchild);}}后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。伪码算法：voidPostOderTraverse(BiTreeT){//采用二叉链表存储结构1596021563962第8页共27页if(T){PostOderTraverse(T-lchild);//先遍历左子树PostOderTraverse(T-rchild);//再遍历右子树putchar(T-data);//最后访问根结点}}2）二叉树的建立算法描述：对二叉树“遍历”基本操作已经建立的基础上，可以在便利过程中对结点进行各种操作，如：在遍历过程中生成结点，建立二叉树存储结构。采用先序遍历建立二叉树链表：（1）按先序序列输入二叉树中结点的元素，以空格表示空，直到输入回车为止；（2）若元素值为空，则赋值NULL；否则生成一个新的结点，将元素值赋值给该跟结点的数值域；（3）建立该跟结点的左子树；（4）建立该根结点的右子树。伪码算法;BiTreeCreateBiTree(BiTreeT){//构造二叉树T，按先序序列输入二叉树中结点的值（一个字符），空格表示空树charch;if((ch=getchar())=='')T=NULL;elseif(ch!='\n'){if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(1);T-dat