数据结构实验三

申（9需壕公*大孝数据结构与数据库实验报告实验题二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树 的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运 算。问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉 得应该：1、建立二叉树；2、通过递归方法来遍历(先序、中序和后序)二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等5、运用广义表对二叉树进行广义表形式的打印。算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的 结点以空格输入表示，并且本实验是以先序顺序输入的。输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行 打印。对二叉树的一些运算结果以整型输出。程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度 求树的非空子孙结点个数、度为 2 的结点数目、度为 2 的结点数目。对二叉树的某个元素进行查找，对二叉 树的某个结点进行删除。测试数据： 输 入 一：ABCDDDEDGDDF口 (以表示空格)，查找5,删除E预测结果：先序遍历 ABCDEGF中序遍历 CBEGDFA后序遍历 CGEFDBA层次遍历 ABCDEFG广义表打印 A(B(C,D(E(,G) ,F) 叶子数 3 深度 5 宽度 2 非空子孙数 6 度为 2 的数目 2 度为 1的数目 2 查找 5，成功，查找的元素为 E删除E后，以广义表形式打印A (B (C,D (,F)输 入二：ABDDDEHDDDCFDG口 (以表示空格)，查找10,删除B 预测结果：先序遍历 ABDEHCFG中序遍历 DBHEAGFC后序遍历 DHEBGFCA层次遍历 ABCDEFHG广义表打印 A( B(D,E(H),C(F(,G) 叶子数 3 深度 4 宽度 3 非空子孙数 7 度为 2 的数目 2 度为 1的数目 3 查找 10，失败。概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。1、设定“二叉树”的抽象数据类型定义：ADT BiTree数据对象D： D是具有相同特性的数据元素的集合。数据关系R：若D二，则R二，称BiTree为空二叉树；若D鼻，则R 抽, H 是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若 D - Loot，则存在 D - root=(D , D 且 D n D 二；l rl r(3) 若D H，则D中存在唯一的元素x , g H,且存在D上的关系l l l l lH u H;若D H,则D中存在唯一的元素x , e H,且存在D上的 lrrrrr关系 H u H; H = t root, x , , H , H rlr l r(4) (D ,馆是一棵符合本定义的二叉树，称为根的左子树，(D ,彷是一棵符合本l lr r定义的二叉树，称为根的有字树基本操作：CreateBiTree&T)操作结果：按照T的定义构造一个二叉树。BiTreeDepth(& T)初始条件：二叉树T已存在。操作结果：返回T的深度。BiTreeWidth(&T)初始条件：二叉树T已存在。操作结果：返回T的宽度。PreOderTraverse&T)初始条件：二叉树T已存在。操作结果：先序遍历打印 T，InOderTraverse(&T)初始条件：二叉树T已存在。操作结果：中序遍历打印ToPostOderTraverse(&T)初始条件：二叉树T已存在。操作结果：后序遍历打印 ToLevelTraverse(&T)初始条件：二叉树T已存在。操作结果：层次遍历ToDeleteXTree(&T,TElemType x)初始条件：二叉树已存在。操作结果：删除元素为x的结点以及其左子树和右子树。 CopyTree(&T)初始条件：二叉树T已存在。 操作结果：以T为模板，复制另一个二叉树。 ADT BiTree2、设定队列的抽象数据类型定义：ADT Queue数据对象：D= a a e BiTree, i e N +i i数据关系：R1=|a ,a e D ,i=2,，ni i1i1 i约定a 端为队列头，a端为队列尾。1n基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。EnQueue(&Q,&e)初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q)初始条件：队列Q已存在。操作结果：删除Q的对头元素，并返回其值。QueueEmpty(&Q)初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回1,否则0。 ADT Queue3、本程序包含四个模块1 )主程序模块 void main( )初始化； 先序输入二叉树各结点元素；各种遍历二叉树； 对二叉树进行常见运算；复制二叉树； 在复制的二叉树上进行二叉树的常见操作；2) 二叉树模块实现二叉树的抽象数据类型和基本操作2) 队列模块实现队列的抽象数据类型及今本操作3) 广义表打印模块以广义表形式打印二叉树4) 二叉树运算模块对二叉树的叶子、非空子孙结点数目、度为2或1的结点数三、 详细设计1、主程序中需要的全程量#define M 10 /统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度2、队列的建立与基本操作typedef struct QNodeBiTree data; /队列中存储的元素类型struct QNode *next; /指向二叉树结点的指针QNode,*Queueptr;typedef structQueueptr front; /队列的队头指针Queueptr rear; /队列的队尾指针LinkQueue;算法描述：为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到 队列。而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列 是否为空。伪码算法：void InitQueue(LinkQueue *Q) /初始化队列申请一个结点Q-front=Q-rear=(Queueptr)malloc(sizeof(QNode);if(!Q-front)exit(l);/存储分配失败处理Q-front-next=NULL;构成带头结点里的空链队列void EnQueue(LinkQueue *Q,BiTree e) /插入元素为 e 为 Q 的队尾元素Queueptr q;q=(Queueptr)malloc(sizeof(QNode);if(!q)exit(1);q-data=e;q-next=NULL;Q-rear-next=q; /元素 e 的结点入列Q-rear=q;BiTree DeQueue(LinkQueue *Q) /从队列中删除队头元素，并直接返回给调用的主函数Queueptr p;BiTree q;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);return q;返 回队头元素int QueueEmpty(LinkQueue *Q) /检查队列是否为空，若为空则返回真值，否则返回0 if(Q-front=Q-rear)return 1;elsereturn 0;3、二叉树的建立与基本操作typedef struct BiTNodeTElemType data; /二叉树结点存储的元素类型struct BiTNode *lchild,*rchild; /二叉树左右孩子指针BiTNode,*BiTree;算法分析： 二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对 二叉树的操作可通过递归调用来实现。1) 二叉树的遍历算法描述：二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理 这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而 且仅被访问一次。回顾二叉树的递归定义可知，二叉树是由 3 个基本单元组成：根节点、左子树和右子树。因 此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访 问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。 若限定先右后左，则只有前三种情况，分别称之为先(根)序遍历。中(根)序遍历和后(根) 序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。伪码算法：void PreOderTraverse(BiTree T)/采用二叉链表存储结构if(T)putchar(T-data);/最简单的访问结点法，输出结点元素，这里先访问根结点 PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则(1) 中序遍历左子树；(2) 访问根结点；(3) 中序遍历右子树。伪码算法：void InOderTraverse(BiTree T) /采用二叉链表存储结构 if(T) InOderTraverse(T-lchild);/先遍历左子树putchar(T-data);/ 最简单的访问结点法，输出结点元素，这里第二访问根结点InOderTraverse(T-rchild);后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则( 1 )后序遍历左子树；( 2)后序遍历右子树；( 3 )访问根结点。伪码算法：void PostOderTraverse(BiTree T)/采用二叉链表存储结构if(T)PostOderTraverse(T-lchild);/先遍历左子树PostOderTraverse(T-rchild);/再遍历右子树 putchar(T-data);/最 后访问根结点2) 二叉树的建立算法描述： 对二叉树“遍历”基本操作已经建立的基础上，可以在便利过程中对结点进行各种操作，如： 在遍历过程中生成结点，建立二叉树存储结构。采用先序遍历建立二叉树链表：(1) 按先序序列输入二叉树中结点的元素，以空格表示空，直到输入回车为止；(2) 若元素值为空，则赋值NULL；否则生成一个新的结点，将元素值赋值给该跟结点的数值 域；(3) 建立该跟结点的左子树；(4) 建立该根结点的右子树。 伪码算法;BiTree CreateBiTree(BiTree T)/构造二叉树T,按先序序列输入二叉树中结点的值(一个字符)，空格表示空树char ch;if(ch=getchar()= )T=NULL;elseif(ch!=n)if(!(T=(BiTree)malloc(sizeof(BiTNode) exit(1);T-data=ch; /生成根结点T-lchild=CreateBiTree(T-lchild);/构 造左子树 T-rchild=CreateBiTree(T-rchild);/构 造右子树return T;/返回所构造二叉树(子)树的地址3) 二叉树的层次遍历算法分析： 有时需要一层层访问二叉树,比如判断二叉树是否为完全二叉树、找出指定层中含有的叶子/ 度为 2/度为1的结点等,这就需要另一种遍历方法层次遍历。先访问的结点,其孩子结点必然也先访问,引入队列存储已被访问的,但其左右孩子尚未访 问的结点的指针。算法描述:(1) 若结点不为空,则访问该结点,并将其入列；(2) 接着从队列中取已被访问的,但其左右孩子尚未被访问的；(3) 访问该结点的左孩子,将其入列；(4) 访问该结点的右孩子,将其入列。伪码算法：int visit(TElemType e)/简单的结点访问函数if(e)putchar(e);/打印该结点元素return 1;elsereturn 0;void LevelTraverse(BiTree T)LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue);BiTree p=(BiTree)malloc(sizeof(BiTNode);InitQueue(Q);/初始化队列，队列的元素为二叉树的结点指针if(T!=NULL)if(!visit(T-data)/访问该结点exit(1);EnQueue(Q,T);将已被访问的，但左右孩子没被访问的结点入列 while(!QueueEmpty(Q)/队列不为空，则尚有未被访问其孩子的结点 p=DeQueue(Q);将该结点出列，返回其地址 if(p-lchild!=NULL)if(!visit(p-lchild-data)访问左孩子 exit(1);EnQueue(Q,p-lchild);将 其入列 if(p-rchild!=NULL)if(!visit(p-rchild-data)访问右孩子 exit(1);EnQueue(Q,p-rchild);/将其入列4) 求二叉树的深度算法描述：(1) 若结点不为空，则求其左子树的深度，并返回其值hl；(2) 求其右子树的深度，也返回其值h2；(3) 选择左右子树深度的最大值，将其加一(该结点本身深度)即为该结点子树的深度 伪码算法：int BiTreeDepth(BiTree T)/后序遍历求树T所指二叉树的深度int hl=0,hr=0;if(!T)return 0;elsehl=BiTreeDepth(T-lchild);/求 左子树的深度 hr=BiTreeDepth(T-rchild);/求 右子树的深度 if(hl=hr)return hl+1;else return hr+1;子树深度的最大值再加上本身所在结点的深度记为子树的深度5) 求二叉树的宽度算法描述：(1) 定义一个数组，来存放每层的结点数，max来存放到这层为止时的最大结点数；(2) 计算每一层的结点数将其赋值给对应的数组元素；(3) 每层计算完后，用max与本层结点数比较，若max小，则将本层结点数赋值给max;(4) 最后返回 max。伪码算法：int BiTreeWidth(BiTree T,int i)int static nM=0;存放各层结点数，M为最先预料的最大树的最大深度int static max=O; 最大宽度if(T!=NULL)if(i=l)若是访问根结点ni+; 第一层加 1i+；到第一层if(T-lchild)ni+;若有左孩子则该层加1if(T-rchild)ni+;若有右孩子则该层加1else/访问子树的结点i+;向下一层if(T-lchild)ni+;if(T-rchild)ni+;if(maxlchild,i);/遍 历左子树BiTreeWidth(T-rchild,i-);/网上退一层后遍历右子树return max;6) 删除二叉树的某个结点 算法描述：(1) 先序遍历找到该结点；(2) 若此结点为空，不必释放；若不为空，则先释放其左右子树的所有结点的空间，再赋为空(3) 再释放根结点的空间，并将这个结点的父节点指向该结点的指针域赋为空。伪码算法：BiTree DeleteBiTree(BiTree t)/释放该结点空间的函数if(t!=NULL)t-lchild=DeleteBiTree(t-lchild);/释 放其左子树的空间 t-rchild=DeleteBiTree(t-rchild);/释放右子树的空间 free(t);/释放根结点的空间t=NULL;将其值赋为空return t;BiTree DeleteXTree(BiTree t,TElemType x)/先序查找到需删结点位置if(t!=NULL)if(t-data=x)判断是否为指定结点 DeleteBiTree(t);/释放树的空间 t=NULL;elset-lchild=DeleteXTree(t-lchild,x); t-rchild=DeleteXTree(t-rchild,x);return t;7) 复制二叉树算法描述:(1) 先复制其左子树；(2) 再复制其右子树；(3) 生成一个新结点，将根复制。 伪码算法：BiTree GetTreeNode(TElemType item,BiTree lptr,BiTree rptr)/生成一个其元素值为item，左指针为lpttr，右指针为rptr的结点 BiTree t;t=(BiTree)malloc(sizeof(BiTNode);t-data=item;t-lchild=lptr;t-rchild=rptr;return t;BiTree CopyTree(BiTree T)/已知二叉树的根指针T,返回它的复制品的根指针BiTree newlptr,newrptr,newnode;if(!T)return NULL;/复制一颗空树if(T-lchild)newlptr=CopyTree(T-lchild);/复制(遍历)其左子树elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild); /复制(遍历)其右子树elsenewrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生 成根结点 return newnode;4、广义表形式打印二叉树算法分析： 为了让打印的二叉树更形象，更清楚的反映二叉树各结点的关系，采用广义表形式打印则可 以满足要求。算法描述：(1) 打印根结点，若其还有孩子，则输出“(”； ( 2)若有左孩子，则打印左子树；( 3)若还有右子树，则先打印“，”区分左右孩子，再打印右子树，并输出“)”表示输除完毕。 伪码算法：void print(BiTree T)/广义表形式打印二叉树if(T!=NULL)printf(%c,T-data);if(T-lchild!=NULL II T-rchild!=NULL)/ 该结点还有孩子printf();print(T-lchild);广义表打印左子树if(T-rchild!=NULL)printf(,);print(T-rchild);/广义表打印右子树 printf();5、二叉树的常见运算1)求二叉树的叶子数算法描述：(1) 若该结点无孩子，则表示为叶子，计数器加一；( 2) 若该结点右孩子，求其左子树的的叶子；( 3) 再求其右子树的叶子。伪码算法：int LeafNum(BiTree T)/统计叶子数int static n=0;定义一个静态局部变量作为计数器if(T!=NULL)if(T-lchild=NULL & T-rchild=NULL) 结点无孩子n+;计数器加一LeafNum(T-lchild);/求左子树的叶子数LeafNum(T-rchild); /求右子树的叶子数return n;2) 求不同的度的结点数 算法描述：(1) 定义一个静态局部数组变量来统计不同度的结点数(2) 若该结点既有左孩子又有右孩子则度为2 的计数器加一，若该节点只有左孩子或只有右孩 子，则度为 1 的结点数的计数器加一、(3) 在对其左右子树进行相同操作。 伪码算法：int *JudgeCBT(BiTree T)/统计不同度的结点数int static d3=0;/d作为度为1的计数器，d2作为度为2的计数器if(T!=NULL)if(T-lchild!=NULL & T-rchild!=NULL)左右孩子都有 d2+;else /只有一个孩子if(T-lchild!=NULL & T-rchild=NULL)d1+; elseif(T-lchild=NULL & T-rchild!=NULL)d1+;JudgeCBT(T-lchild);/统计左子树JudgeCBT(T-rchild);/统计右孩子return d;返回数组的指针3) 求非空子孙结点数算法描述：(1) 定义一个静态局部变量，作为计数器；(2) 若该节点的左孩子非空则加一，右孩子非空亦加一；(3) 统计左子树；统计右子树。伪码算法：int BiTreeDescendant(BiTree T) /统计非空子孙结点数int static n=0;初始化计数器if(T!=NULL)if(T-lchild)n+;if(T-rchild)n+;BiTreeDescendant(T-lchild);/统计左子树BiTreeDescendant(T-rchild);/统计右子树return n;4) 查找二叉树的某个位置的结点(先序序列)算法描述：(1) 定义一个静态局部变量，用作记录已查结点的个数；(2) 从根节点开始，如果相查找的位置理由元素，则打印该元素，如果想查的位置超过二叉树 本身的元素数则返回出错。伪码算法：int PreOderKNode(BiTree T,int k,TElemType *e)/T为二叉树，k为带查找的结点位序；e为指针带值返回查找到的数。int static count=0;作为计数器，记录已查找的结点数if(T=NULL)return 0;count+;访问结点，对已访问的结点进行计数 if(count=k)判断该结点是否是待查找的结点e=&T-data;printf(存在你想查找位置的元素，先序序列中第d个元素是cn,k,*e);return 1;/查找成功elseif(countk)计数器count已经超出k,则直接返回0,查找不成功return 0;else/在左或右子树中查找if(PreOderKNode(T-lchild,k,e)=0) return PreOderKNode(T-rchild,k,e);return 1;6、主程序的伪码算法：void main()BiTree T=NULL,T_1=NULL,T_2=NULL;int i=1,*n=0,*kd,k=0;char x=0;printf(请按先序序列输入各结点n);T=CreateBiTree(T);先序序列构造一棵二叉树/遍历二叉树printf(先序遍历二叉树：n);PreOderTraverse(T);putchar(n); printf(”中序遍历二叉树：n);InOderTraverse(T);putchar(n); printf(后序遍历二叉树：n);PostOderTraverse(T);putchar(n); printf(层次遍历二叉树：n);LevelTraverse(T);putchar(n);printf(”以广义表形式打印二叉树:n);广义表形式打印二叉树 print(T);putchar(n);/二叉树的基本操作和运算printf(”二叉树的叶子数 LeafNumber 为:dn,LeafNum(T);统计叶子数 printf(二叉树的深 度 Depth 为:dn,BiTreeDepth(T);计算深度 printf(”二叉树的宽度 Width 为:dn,BiTreeWidth(T,i);/计算宽度 /统计非空子孙结点数printf(”二叉树非空子孙结点 DescendantNumber 数为:dn,BiTreeDescendant(T); kd=JudgeCBT(T);统计不同度的结点数printf(二叉树度为1的结点数为:d，度为2的结点数为:dn,kdl,kd2); /二叉树的基本操作，删除和查找printf(下面进行二叉数的查找和删除操作n); T_2=CopyTree(T);putchar(n);/运用二叉树的复制操作 printf(复制后的T_2,以先序序列输出:n); PreOderTraverse(T_2);putchar(n);printf(请输入你想查找在在先序序列的第几个位置的元素)； scanf(%d,&k);if(!PreOderKNode(T_2,k,e)printf(”不存在你想查找的位Sn);T_1=CopyTree(T);putchar(n);printf(复制后的T_1,以先序序列输出:n);PreOderTraverse(T_1);putchar(n); getchar(); printf(请输入你想删除元素值为多少的结点5); x=getchar();getchar();DeleteXTree(T_1,x);printf(先序遍历二叉树：n);PreOderTraverse(T_1);putchar(n); printf(以广义表形式打印二叉树:n);print(T_1);putchar(n);调试分析1、在调试过程中，在进行二叉树的基本操作时就出现错误了，为了方便检查错误，故逐渐将主函数的谋 部分调用的函数先屏蔽后，再运行调试，才发现了错误。2、在调试过程中，为了方便对调用函数的检查，每当计数器变化时，就输出该值，就可以看出是哪里的 问题。3、在调试过程中，在运行删除时，程序出现错误，当输入欲删除结点后，程序并没有删除该结点。后来 经过调试才发现，因为在输入删除元素时，是由 getcha（r ）接收，而在查找时遗留下的回车直接被 getchar （）接收，当作 NULL 去运行了。4、在调试过程中，更改了4 的错误，在删除一个结点后，虽然能删除元素了，但再次打印该树后，就发 现每当打印到删除结点位置时，程序就报错。后来经过老师和同学的帮助才发现，虽然将待删结点的 空间释放，但并没有把指向该结点的父结点的指针域赋空，后来更改后，程序完美运行了。5、从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的队列和链式存储结 构的二叉树的应用。五、用户使用说明1、本程序的运行环境为Windows7旗舰版操作系统，执行文件为：二叉树的基本操作及运算.exe；2、进入程序后即显示提示信息：“请按先序序列输入各结点”以等待用户输入欲构造的二叉树的各元 素值；若用户输入的的是一个不符合先序序列的字符串，则程序报错；3、在用户正确输入二叉树的元素后，程序会自动对其先序、中序、后序和层次遍历，并对二叉树进 行求叶子数、深度、宽度、非空子孙结点数、度为1 的结点数和度为2的结点数。并在自动复制 一棵树后，出现“请输入你想查找在先序序列的第几个位置的元素”，等待用户输入欲查找的元素 位置；4、输入查找的位置后，如果存在该位置的元素，则程序会显示“存在你想查找位置的元素，先序序 列中第x个元素是x”；然后会弹出“请输入你想删除元素值为多少的结点”，等待用户输入某个 元素值；5、输入某个元素值后，若删除成功则会先序遍历和广义表形式打印删除后的二叉树。6、本程序要求在输入二叉树元素是一定要正确，空格不能少，也不能多，不然程序会报错。六、测试结果1、正确输入：ABCDDDEDGDDF口 ，查找5,删除E运行界面：2、正确输入：ABDnnEHnnncFDGnnn （以表示空格），査找1 o,删除b 运行界面：请按先序序列输入各结点ABD H CF G先序遍历二叉树：ABDEHCFG中序遍历二灭树；DBHEAFGC后库通历二叉树:DHEBGFGA层次遍历二灵树：ABCDEFHG以广义表形式打印二叉树二二叉树的叶数Leaf Number为:3 二叉疎的深 二叉恢的宽一 二叉诜菲空子孙绩点Descendan tHumbe澈为: 孟艇加&論麟的结鷄复制后的丁_2,以先序序列输岀:ABDEHCFG请输入你想查找在在先序序列的第几个位置的元素10不存在你想查找的位置复制后的T-1，以先序序列输岀:ABDEHCFG丰输入你想删除元素值为多少的结点 先序遍历二叉树：A CFG以广义表形式打印二叉树二Press any hey to continue以上结果与自己在进行程序概要分析时的预测结果一致七、心得体会这次实验设计让我更加了解并更加灵活运用到大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次实验设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不 过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在进行编程时一定要把 每个问题都分析清楚，比如自己在编写删除删除BiTree DeleteBiTree(BiTree t), BiTree DeleteXTree(BiTree t,TElemType x)时，只是把一个指针忘记赋为空，则导致程序报错，希望以后在运用递归调用时，一定要弄 清各种值的传递关系。还有，在编写函数时，编写时能把每一步的结果都打印出来，这能很方便的调试程序。在编写实验报告时自己无意发现，其实统计非空子孙结点数、不同度的结点数甚至叶子数的函数思想 与算法十分相似，都可以编写在一个函数里，这也说明了实验报告的重要性，我们应该在实验报告里多反 思、总结，尽量完善自己的程序设计。程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计 很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现 自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率 高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。 参考文献：1数据结构（C语言版）严蔚敏清华大学出版社2. C程序设计谭浩强清华大学出版社3. 数据结构题集（C语言版）严蔚敏吴伟民米宁清华大学出版社4. C程序设计学习指导与练习贾伯琪中国科学技术大学出版社八、附录“二叉树的基本操作及运算”源程序代码：#include#include#includetypedef char TElemType;char *e;#define M 10typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct QNodeBiTree data;struct QNode *next;QNode,*Queueptr;typedef structQueueptr front;Queueptr rear;LinkQueue;void InitQueue(LinkQueue *Q)Q-front=Q-rear=(Queueptr)malloc(sizeof(QNode); if(!Q-front)exit(1);Q-front-next=NULL;void EnQueue(LinkQueue *Q,BiTree e)Queueptr q; q=(Queueptr)malloc(sizeof(QNode);if(!q)exit(1);q-data=e; q-next=NULL;Q-rear-next=q;Q-rear=q;BiTree DeQueue(LinkQueue *Q)Queueptr p;BiTree q; 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);return q;int QueueEmpty(LinkQueue *Q)if(Q-front=Q-rear)return 1;elsereturn 0;BiTree CreateBiTree(BiTree T)char ch;if(ch=getchar()= )T=NULL;elseif(ch!=n) if(!(T=(BiTree)malloc(sizeof(BiTNode) exit(1);T-data=ch; T-lchild=CreateBiTree(T-lchild); T-rchild=CreateBiTree(T-rchild);return T;void PreOderTraverse(BiTree T)if(T)putchar(T-data);PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);void InOderTraverse(BiTree T)if(T)InOderTraverse(T-lchild); putchar(T-data);InOderTraverse(T-rchild);void PostOderTraverse(BiTree T)if(T)PostOderTraverse(T-lchild);PostOderTraverse(T-rchild); putchar(T-data);int visit(TElemType e)if(e) putchar(e); return 1;elsereturn 0;void LevelTraverse(BiTree T)LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue);BiTree p=(BiTree)malloc(sizeof(BiTNode); InitQueue(Q);if(T!=NULL) if(!visit(T-data) exit(1);EnQueue(Q,T); while(!QueueEmpty(Q) p=DeQueue(Q); if(p-lchild!=NULL) if(!visit(p-lchild-data) exit(1);EnQueue(Q,p-lchild); if(p-rchild!=NULL) if(!visit(p-rchild-data) exit(1);EnQueue(Q,p-rchild);int BiTreeDepth(BiTree T)int hl=0,hr=0;if(!T)return 0;elsehl=BiTreeDepth(T-lchild);hr=BiTreeDepth(T-rchild);if(hl=hr)return hl+1;else return hr+1;int BiTreeWidth(BiTree T,int i)int static nM=0;int static max=0; if(T!=NULL)if(i=1)ni+;i+;if(T-lchild) ni+;if(T-rchild) ni+;elsei+;if(T-lchild) ni+;if(T-rchild) ni+; if(maxlchild,i);BiTreeWidth(T-rchild,i-); return max;BiTree GetTreeNode(TElemType item,BiTree lptr,BiTree rptr) BiTree t; t=(BiTree)malloc(sizeof(BiTNode); t-data=item;t-lchild=lptr;t-rchild=rptr;return t;BiTree CopyTree(BiTree T)BiTree newlptr,newrptr,newnode;if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);elsenewrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr); return newnode;int LeafNum(BiTree T)int static n=0;if(T!=NULL)if(T-lchild=NULL & T-rchild=NULL) n+;LeafNum(T-lchild);LeafNum(T-rchild);return n;void print(BiTree T)if(T!=NULL)printf(%c,T-data);if(T-lchild!=NULL | T-rchild!=NULL)printf();print(T-lchild); if(T-rchild!=NULL) printf(,);print(T-rchild);printf();int *JudgeCBT(BiTree T)int static d3=0; if(T!=NULL) if(T-lchild!=NULL & T-rchild!=NULL)d2+;else if(T-lchild!=NULL & T-rchild=NULL) d1+;else if(T-lchild=NULL & T-rchild!=NULL) d1+;JudgeCBT(T-lchild);JudgeCBT(T-rchild);return d;int BiTreeDescendant(BiTree T)int static n=0; if(T!=NULL) if(T-lchild) n+;if(T-rchild) n+;BiTreeDescendant(T-lchild); BiTreeDescendant(T-rchild); return n;BiTree DeleteBiTree(BiTree t)if(t!=NULL) t-lchild=DeleteBiTree(t-lchild); t-rchild=DeleteBiTree(t-rchild);free(t); t=NULL;return t;BiTree DeleteXTree(BiTree t,TElemType x)if(t!=NULL) if(t-data=x)DeleteBiTree(t);t=NULL;else t-lchild=DeleteXTree(t-lchild,x); t-rchild=DeleteXTree(t-rchild,x);return t;int PreOderKNode(BiTree T,int k,TElemType *e)int static count=0;if(T=NULL)return 0;count+;if(count=k) e=&T-data;printf(存在你想查找位置的元素，先序序列中第d个元素是%cn,k,*e); return 1;elseif(countk)return 0;elseif(PreOderKNode(T-lchild,k,e)=0) return PreOderKNode(T-rchild,k,e);return 1;void main()BiTree T=NULL,T_1=NULL,T_2=NULL;int i=1,*n=0,*kd,k=0;char x=0;printfC请按先序序列输入各结点n);T=CreateBiTree(T);printf(先序遍历二叉树：n);PreOderTraverse(T);putchar(n);printf(中序遍历二叉树：n);InOderTraverse(T);putchar(n);printf(后序遍历二叉树：n);PostOderTraverse(T);putchar(n);printf(层次遍历二叉树：n);LevelTraverse(T);putchar(n);printf(以广义表形式打印二叉树:n); print(T);putchar(n);printf (二叉树的叶子数 LeafNumber 为：dn,LeafNum(T);printf (二叉树的深 度 Depth 为：dn,BiTreeDepth(T);printf (二叉树的宽 度Width 为：%dn,BiTreeWidth(T,i);printf (二叉树非空子孙结点 DescendantNumber 数为:%dn,BiTreeDescendant(T); kd=JudgeCBT(T);printf (二叉树度为1的结点数为:%d，度为2的结点数为：dn,kd1,kd2); printfC下面进行二叉数的查找和删除操作n);T_2=CopyTree(T);putchar(n);printfC复制后的T_2,以先序序列输出:n);PreOderTraverse(T_2);putchar(n);printfC请输入你想查找在在先序序列的第几个位置的元素n ); scanf(%d,&k);if(!PreOderKNode(T_2,k,e)printf(不存在你想查找的位置n);T_1=CopyTree(T);putchar(n);printfC复制后的T_1,以先序序列输出:n);PreOderTraverse(T_1);putc