1、删除B后，以广义表形式打印A（，C（F（，G）二、概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。1、设定“二叉树”的抽象数据类型定义：ADT BiTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若，则，称BiTree为空二叉树；，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若则存在且;（3）若则中存在唯一的元素,且存在上的关系若；（4）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树基本操作： CreateBiTree&T） 操作结果：按照T的定义构造一个二叉树。 B
2、iTreeDepth（& T） 初始条件：二叉树T已存在。返回T的深度。BiTreeWidth（&初始条件：返回T的宽度。PreOderTraverse&先序遍历打印T，InOderTraverse（&中序遍历打印T。PostOderTraverse（&后序遍历打印T。LevelTraverse（&层次遍历T。DeleteXTree（&T,TElemType x）二叉树已存在。删除元素为x的结点以及其左子树和右子树。 CopyTree（&以T为模板，复制另一个二叉树。ADT BiTree2、设定队列的抽象数据类型定义：ADT Queue 数据对象：D= 数据关系：R1=|,i=2,，n约定端为
3、队列头，端为队列尾。 InitQueue（&Q）构造一个空队列Q。 EnQueue（&Q,&e） 队列Q已存在。插入元素e为Q的新的队尾元素。 DeQueue（&删除Q的对头元素，并返回其值。 QueueEmpty（&若Q为空队列，则返回1，否则0。 ADT Queue 3、本程序包含四个模块1）主程序模块void main（ ） 初始化； 先序输入二叉树各结点元素；各种遍历二叉树；对二叉树进行常见运算；复制二叉树；在复制的二叉树上进行二叉树的常见操作；2）二叉树模块实现二叉树的抽象数据类型和基本操作2）队列模块实现队列的抽象数据类型及今本操作3）广义表打印模块以广义表形式打印二叉树4）二叉树
4、运算模块对二叉树的叶子、非空子孙结点数目、度为2或1的结点数三、详细设计1、主程序中需要的全程量#define M 10 / 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度2、队列的建立与基本操作typedef struct QNode BiTree data; /队列中存储的元素类型 struct QNode *next; /指向二叉树结点的指针 QNode,*Queueptr;typedef struct Queueptr front; /队列的队头指针 Queueptr rear; /队列的队尾指针LinkQueue;算法描述：为了对二叉树进行层次遍历，需要“先访问的结点
5、，其孩子结点必然也先访问”，故需运用到队列。而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。伪码算法：void InitQueue（LinkQueue *Q）/初始化队列申请一个结点 Q-front=Q-rear=（Queueptr）malloc（sizeof（QNode）; if（!Q-front） exit（1）;/存储分配失败处理front-next=NULL;/构成带头结点里的空链队列void EnQueue（LinkQueue *Q,BiTree e）/插入元素为e为Q的队尾元素 Queueptr q; q=（Queueptr）malloc（s
6、izeof（QNode）;q） q-data=e;rear-next=q; /元素e的结点入列rear=q;BiTree DeQueue（LinkQueue *Q）/从队列中删除队头元素，并直接返回给调用的主函数 Queueptr p; BiTree q; if（Q-front=Q-rear） /队列为空 printf（ERROR!n）; p=Q-next; q=p-data;next=p- /删除该结点rear=p） Q-rear=Q-front; free（p）; return q;/返回队头元素int QueueEmpty（LinkQueue *Q）/检查队列是否为空，若为空则返回真值，
7、否则返回0 return 1; else return 0;3、二叉树的建立与基本操作typedef struct BiTNode TElemType data; /二叉树结点存储的元素类型 struct BiTNode *lchild,*rchild; /二叉树左右孩子指针BiTNode,*BiTree;算法分析：二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。1）二叉树的遍历二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结
8、点均被访问一次，而且仅被访问一次。回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOderTravers
9、e（BiTree T）/采用二叉链表存储结构 if（T） putchar（T-data）;/最简单的访问结点法，输出结点元素，这里先访问根结点 PreOderTraverse（T-lchild）;rchild）;中序遍历二叉树的操作定义：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void InOderTraverse（BiTree T） InOderTraverse（T-/先遍历左子树/ 最简单的访问结点法，输出结点元素，这里第二访问根结点 后序遍历二叉树的操作定义：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。void PostOderTraverse（B
10、iTree T） PostOderTraverse（T-/再遍历右子树 putchar（T-/最后访问根结点2）二叉树的建立对二叉树“遍历”基本操作已经建立的基础上，可以在便利过程中对结点进行各种操作，如：在遍历过程中生成结点，建立二叉树存储结构。采用先序遍历建立二叉树链表：（1）按先序序列输入二叉树中结点的元素，以空格表示空，直到输入回车为止；（2）若元素值为空，则赋值NULL；否则生成一个新的结点，将元素值赋值给该跟结点的数值域；（3）建立该跟结点的左子树；（4）建立该根结点的右子树。伪码算法;BiTree CreateBiTree（BiTree T）/构造二叉树T，按先序序列输入二叉树中
11、结点的值（一个字符），空格表示空树 char ch; if（ch=getchar（）= ） T=NULL;if（ch!=n if（!（T=（BiTree）malloc（sizeof（BiTNode） T-data=ch; /生成根结点lchild=CreateBiTree（T-/构造左子树rchild=CreateBiTree（T-/构造右子树 return T;/返回所构造二叉树（子）树的地址3）二叉树的层次遍历有时需要一层层访问二叉树，比如判断二叉树是否为完全二叉树、找出指定层中含有的叶子/度为2/度为1的结点等，这就需要另一种遍历方法层次遍历。先访问的结点，其孩子结点必然也先访问，引入队
12、列存储已被访问的，但其左右孩子尚未访问的结点的指针。算法描述:（1）若结点不为空，则访问该结点，并将其入列；（2）接着从队列中取已被访问的，但其左右孩子尚未被访问的；（3）访问该结点的左孩子，将其入列；（4）访问该结点的右孩子，将其入列。int visit（TElemType e）/简单的结点访问函数 if（e） putchar（e）;/打印该结点元素void LevelTraverse（BiTree T） LinkQueue *Q=（LinkQueue *）malloc（sizeof（LinkQueue）; BiTree p=（BiTree）malloc（sizeof（BiTNode）; I
13、nitQueue（Q）;/初始化队列，队列的元素为二叉树的结点指针 if（T!=NULL）visit（T-data）/访问该结点 exit（1）; EnQueue（Q,T）;/将已被访问的，但左右孩子没被访问的结点入列 while（!QueueEmpty（Q） /队列不为空，则尚有未被访问其孩子的结点 p=DeQueue（Q）;/将该结点出列，返回其地址 if（p-lchild! if（!visit（p-lchild-data）/访问左孩子 exit（1）; EnQueue（Q,p-/将其入列rchild!rchild-data）/访问右孩子4）求二叉树的深度（1）若结点不为空，则求其左子树的
14、深度，并返回其值h1；（2）求其右子树的深度，也返回其值h2；（3）选择左右子树深度的最大值，将其加一（该结点本身深度）即为该结点子树的深度。int BiTreeDepth（BiTree T）/后序遍历求树T所指二叉树的深度 int hl=0,hr=0; hl=BiTreeDepth（T-/求左子树的深度 hr=BiTreeDepth（T-/求右子树的深度 if（hl=hr）return hl+1; else return hr+1;/子树深度的最大值再加上本身所在结点的深度记为子树的深度5）求二叉树的宽度（1）定义一个数组，来存放每层的结点数，max来存放到这层为止时的最大结点数；（2）计算
15、每一层的结点数将其赋值给对应的数组元素；（3）每层计算完后，用max与本层结点数比较，若max小，则将本层结点数赋值给max;（4）最后返回max。int BiTreeWidth（BiTree T,int i） int static nM=0;/存放各层结点数，M为最先预料的最大树的最大深度 int static max=0;/最大宽度 if（i=1）/若是访问根结点 ni+;/第一层加1 i+;/到第二层 if（T-lchild） ni+;/若有左孩子则该层加1rchild）/若有右孩子则该层加1 else /访问子树的结点/向下一层 if（maxlchild,i）;/遍历左子树rchild
16、,i-）;/网上退一层后遍历右子树 return max;6）删除二叉树的某个结点（1）先序遍历找到该结点；（2）若此结点为空，不必释放；若不为空，则先释放其左右子树的所有结点的空间，再赋为空；（3）再释放根结点的空间，并将这个结点的父节点指向该结点的指针域赋为空。BiTree DeleteBiTree（BiTree t）/释放该结点空间的函数 if（t! t-lchild=DeleteBiTree（t-/释放其左子树的空间rchild=DeleteBiTree（t-/释放右子树的空间 free（t）;/释放根结点的空间 t=NULL;/将其值赋为空 return t;BiTree Delet
17、eXTree（BiTree t,TElemType x）/先序查找到需删结点位置 if（t-data=x）/判断是否为指定结点 DeleteBiTree（t）;/释放树的空间t=NULL; t-lchild=DeleteXTree（t-lchild,x）;rchild=DeleteXTree（t-rchild,x）;7）复制二叉树（1）先复制其左子树；（2）再复制其右子树；（3）生成一个新结点，将根复制。BiTree GetTreeNode（TElemType item,BiTree lptr,BiTree rptr）/生成一个其元素值为item，左指针为lpttr，右指针为rptr的结点 B
18、iTree t; t=（BiTree）malloc（sizeof（BiTNode）; t-data=item;lchild=lptr;rchild=rptr;BiTree CopyTree（BiTree T）/已知二叉树的根指针T，返回它的复制品的根指针 BiTree newlptr,newrptr,newnode; return NULL;/复制一颗空树 if（T- newlptr=CopyTree（T-/复制（遍历）其左子树 newlptr=NULL; newrptr=CopyTree（T- /复制（遍历）其右子树 newrptr=NULL; newnode=GetTreeNode（T-d
19、ata,newlptr,newrptr）;/生成根结点 return newnode;4、广义表形式打印二叉树为了让打印的二叉树更形象，更清楚的反映二叉树各结点的关系，采用广义表形式打印则可以满足要求。（1）打印根结点，若其还有孩子，则输出“（”；（2）若有左孩子，则打印左子树；（3）若还有右子树，则先打印“，”区分左右孩子，再打印右子树，并输出“）”表示输除完毕。void print（BiTree T）/广义表形式打印二叉树%c,T- if（T-=NULL | T-=NULL）/该结点还有孩子 printf（ print（T-/广义表打印左子树 printf（,/广义表打印右子树）5、二叉树
20、的常见运算1）求二叉树的叶子数（1）若该结点无孩子，则表示为叶子，计数器加一；（2）若该结点右孩子，求其左子树的的叶子；（3）再求其右子树的叶子。int LeafNum（BiTree T）/统计叶子数 int static n=0;/定义一个静态局部变量作为计数器lchild=NULL & T-rchild=NULL）/结点无孩子 n+;/计数器加一 LeafNum（T-/求左子树的叶子数 /求右子树的叶子数 return n;2）求不同的度的结点数（1）定义一个静态局部数组变量来统计不同度的结点数（2）若该结点既有左孩子又有右孩子则度为2的计数器加一，若该节点只有左孩子或只有右孩子，则度为1的结点数的计数器加一、（3）在对其左右子树进行相同操作。int *JudgeCBT（BiTree T）/统计不同度的结点数 int static d3=0;/d1作为度为1的计数器，d2作为度为2的计数器=NULL &=NULL）/左右孩子都有 d2+; /只有一个孩子 if（T-rchild=NULL） d1+; else
