数据结构实验三——二叉树基本操作及运算实验报告

《数据结构与数据库》

实验报告

实验题目

二叉树的基本操作及运算

学院：化学与材料科学学院

专业班级：09级材料科学与工程系PB0920603

姓名：李维谷

学号：PB09206285

邮箱：liwg@mail.ustc.edu.cn

指导教师：贾伯琪

实验时间：2010年10月17日

一、需要分析

问题描述：

实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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的数目2

查找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：

若，则，称BiTree为空二叉树；

若，则，H是如下二元关系：

（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

（2） 若则存在且;

（3） 若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系；

（4）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树

基本操作：

CreateBiTree&T)

操作结果：按照T的定义构造一个二叉树。

BiTreeDepth(& T)

初始条件：二叉树T已存在。

操作结果：返回T的深度。

BiTreeWidth(&T)

初始条件：二叉树T已存在。

操作结果：返回T的宽度。

PreOderTraverse&T)

初始条件：二叉树T已存在。

操作结果：先序遍历打印T，

InOderTraverse(&T)

初始条件：二叉树T已存在。

操作结果：中序遍历打印T。

PostOderTraverse(&T)

初始条件：二叉树T已存在。

操作结果：后序遍历打印T。

LevelTraverse(&T)

初始条件：二叉树T已存在。

操作结果：层次遍历T。

DeleteXTree(&T,TElemType x)

初始条件：二叉树已存在。

操作结果：删除元素为x的结点以及其左子树和右子树。

CopyTree(&T)

初始条件：二叉树T已存在。

操作结果：以T为模板，复制另一个二叉树。

｝ADTBiTree

2、设定队列的抽象数据类型定义：

ADTQueue{

数据对象：D={

数据关系：R1={<>|,,i=2,…，n}

约定端为队列头，端为队列尾。

基本操作：

InitQueue(&Q)

操作结果：构造一个空队列Q。

EnQueue(&Q,&e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue(&Q)

初始条件：队列Q已存在。

操作结果：删除Q的对头元素，并返回其值。

QueueEmpty(&Q)

初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回1，否则0。

}ADTQueue

3、本程序包含四个模块

1）主程序模块

voidmain( )

{

初始化；

先序输入二叉树各结点元素；

各种遍历二叉树；

对二叉树进行常见运算；

复制二叉树；

在复制的二叉树上进行二叉树的常见操作；

｝

2）二叉树模块——实现二叉树的抽象数据类型和基本操作

2）队列模块——实现队列的抽象数据类型及今本操作

3）广义表打印模块——以广义表形式打印二叉树

4）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数

三、详细设计

1、主程序中需要的全程量

#define M 10 // 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度

2、队列的建立与基本操作

typedefstruct QNode{

BiTree data; //队列中存储的元素类型

struct QNode *next; //指向二叉树结点的指针

}QNode,*Queueptr;

typedefstruct{

Queueptr front; //队列的队头指针

Queueptr rear; //队列的队尾指针

}LinkQueue;

算法描述：

为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到队列。而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。

伪码算法：

voidInitQueue(LinkQueue *Q)

{//初始化队列申请一个结点

Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));

if(!Q->front)

exit(1);//存储分配失败处理

Q->front->next=NULL;//构成带头结点里的空链队列

}

voidEnQueue(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);

returnq;//返回队头元素

}

intQueueEmpty(LinkQueue *Q)

{//检查队列是否为空，若为空则返回真值，否则返回0

if(Q->front==Q->rear)

return1;

else

return0;

}

3、二叉树的建立与基本操作

typedef structBiTNode{

TElemType data; //二叉树结点存储的元素类型

structBiTNode *lchild,*rchild; //二叉树左右孩子指针

}BiTNode,*BiTree;

算法分析：

二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。

1）二叉树的遍历

算法描述：

二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。

先序遍历二叉树的操作定义：

若二叉树为空，则空操作；否则

（1） 访问根结点；

（2） 先序遍历左子树；

（3） 先序遍历右子树。

伪码算法：

voidPreOderTraverse(BiTree T)

{//采用二叉链表存储结构

if(T)

{

putchar(T->data);//最简单的访问结点法，输出结点元素，这里先访问根结点

PreOderTraverse(T->lchild);

PreOderTraverse(T->rchild);

}

}

中序遍历二叉树的操作定义：

若二叉树为空，则空操作；否则

（1） 中序遍历左子树；

（2） 访问根结点；

（3） 中序遍历右子树。

伪码算法：

voidInOderTraverse(BiTree T)

{//采用二叉链表存储结构

if(T)

{

InOderTraverse(T->lchild);//先遍历左子树

putchar(T->data);// 最简单的访问结点法，输出结点元素，这里第二访问根结点

InOderTraverse(T->rchild);

}

}

后序遍历二叉树的操作定义：

若二叉树为空，则空操作；否则

（1） 后序遍历左子树；

（2） 后序遍历右子树；

（3） 访问根结点。

伪码算法：

voidPostOderTraverse(BiTree T)

{//采用二叉链表存储结构

if(T)

{

PostOderTraverse(T->lchild);//先遍历左子树

PostOderTraverse(T->rchild);//再遍历右子树

putchar(T->data);//最后访问根结点

}

}

2）二叉树的建立

算法描述：

对二叉树“遍历”基本操作已经建立的基础上，可以在便利过程中对结点进行各种操作，如：在遍历过程中生成结点，建立二叉树存储结构。

采用先序遍历建立二叉树链表：

（1） 按先序序列输入二叉树中结点的元素，以空格表示空，直到输入回车为止；

（2） 若元素值为空，则赋值NULL；否则生成一个新的结点，将元素值赋值给该跟结点的数值域；

（3） 建立该跟结点的左子树；

（4） 建立该根结点的右子树。

伪码算法;

BiTree CreateBiTree(BiTree T)

{//构造二叉树T，按先序序列输入二叉树中结点的值（一个字符），空格表示空树

charch;

if((ch=getchar())==' ')

T=NULL;

else

if(ch!='\n')

{

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

exit(1);

T->data=ch; //生成根结点

T->lchild=CreateBiTree(T->lchild);//构造左子树

T->rchild=CreateBiTree(T->rchild);//构造右子树

}

returnT;//返回所构造二叉树（子）树的地址

}

3）二叉树的层次遍历

算法分析：

有时需要一层层访问二叉树，比如判断二叉树是否为完全二叉树、找出指定层中含有的叶子/度为2/度为1的结点等，这就需要另一种遍历方法——层次遍历。

先访问的结点，其孩子结点必然也先访问，引入队列存储已被访问的，但其左右孩子尚未访问的结点的指针。

算法描述:

（1）若结点不为空，则访问该结点，并将其入列；

（2）接着从队列中取已被访问的，但其左右孩子尚未被访问的；

（3）访问该结点的左孩子，将其入列；

（4）访问该结点的右孩子，将其入列。

伪码算法：

intvisit(TElemType e)

{//简单的结点访问函数

if(e)

{

putchar(e);//打印该结点元素

return1;

}

else

return0;

}

voidLevelTraverse(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） 若结点不为空，则求其左子树的深度，并返回其值h1；

（2） 求其右子树的深度，也返回其值h2；

（3） 选择左右子树深度的最大值，将其加一（该结点本身深度）即为该结点子树的深度。

伪码算法：

intBiTreeDepth(BiTree T)

{//后序遍历求树T所指二叉树的深度

inthl=0,hr=0;

if(!T)

return 0;

else

{

hl=BiTreeDepth(T->lchild);//求左子树的深度

hr=BiTreeDepth(T->rchild);//求右子树的深度

if(hl>=hr)return hl+1;

else returnhr+1;//子树深度的最大值再加上本身所在结点的深度记为子树的深度

}

}

5）求二叉树的宽度

算法描述：

（1） 定义一个数组，来存放每层的结点数，max来存放到这层为止时的最大结点数；

（2） 计算每一层的结点数将其赋值给对应的数组元素；

（3） 每层计算完后，用max与本层结点数比较，若max小，则将本层结点数赋值给max;

（4） 最后返回max。

伪码算法：

int BiTreeWidth(BiTree T,int i)

{

int staticn[M]={0};//存放各层结点数，M为最先预料的最大树的最大深度

int staticmax=0;//最大宽度

if(T!=NULL)

{

if(i==1)//若是访问根结点

{

n[i]++;//第一层加1

i++;//到第二层

if(T->lchild)

n[i]++;//若有左孩子则该层加1

if(T->rchild)

n[i]++;//若有右孩子则该层加1

}

else

{//访问子树的结点

i++;//向下一层

if(T->lchild)

n[i]++;

if(T->rchild)

n[i]++;

}

if(max

max=n[i];//取出目前为止，各层结点数的最大值

BiTreeWidth(T->lchild,i);//遍历左子树

BiTreeWidth(T->rchild,i--);//网上退一层后遍历右子树

}

returnmax;

}

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;//将其值赋为空

}

returnt;

}

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);

}

}

returnt;

}

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;

returnt;

}

BiTree CopyTree(BiTree T)

{//已知二叉树的根指针T，返回它的复制品的根指针

BiTree newlptr,newrptr,newnode;

if(!T)

return NULL;//复制一颗空树

if(T->lchild)

newlptr=CopyTree(T->lchild);//复制（遍历）其左子树

else

newlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild); //复制（遍历）其右子树

else

newrptr=NULL;

newnode=GetTreeNode(T->data,newlptr,newrptr);//生成根结点

returnnewnode;

}

4、广义表形式打印二叉树

算法分析：

为了让打印的二叉树更形象，更清楚的反映二叉树各结点的关系，采用广义表形式打印则可以满足要求。

算法描述：

（1）打印根结点，若其还有孩子，则输出“（”；

（2）若有左孩子，则打印左子树；

（3）若还有右子树，则先打印“，”区分左右孩子，再打印右子树，并输出“）”表示输除完毕。

伪码算法：

voidprint(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(")");

}

}

}

5、二叉树的常见运算

1）求二叉树的叶子数

算法描述：

（1） 若该结点无孩子，则表示为叶子，计数器加一；

（2） 若该结点右孩子，求其左子树的的叶子；

（3） 再求其右子树的叶子。

伪码算法：

intLeafNum(BiTree T)

{//统计叶子数

int staticn=0;//定义一个静态局部变量作为计数器

if(T!=NULL)

{

if(T->lchild==NULL&& T->rchild==NULL)//结点无孩子

n++;//计数器加一

LeafNum(T->lchild);//求左子树的叶子数

LeafNum(T->rchild); //求右子树的叶子数

}

returnn;

}

2）求不同的度的结点数

算法描述：

（1） 定义一个静态局部数组变量来统计不同度的结点数

（2） 若该结点既有左孩子又有右孩子则度为2的计数器加一，若该节点只有左孩子或只有右孩子，则度为1的结点数的计数器加一、

（3） 在对其左右子树进行相同操作。

伪码算法：

int*JudgeCBT(BiTree T)

{//统计不同度的结点数

int staticd[3]={0};//d[1]作为度为1的计数器，d[2]作为度为2的计数器

if(T!=NULL)

{

if(T->lchild!=NULL&& T->rchild!=NULL)//左右孩子都有

d[2]++;

else

{//只有一个孩子

if(T->lchild!=NULL&& T->rchild==NULL)

d[1]++;

else

if(T->lchild==NULL&& T->rchild!=NULL)

d[1]++;

}

JudgeCBT(T->lchild);//统计左子树

JudgeCBT(T->rchild);//统计右孩子

}

returnd;//返回数组的指针

}

3）求非空子孙结点数

算法描述：

（1） 定义一个静态局部变量，作为计数器；

（2） 若该节点的左孩子非空则加一，右孩子非空亦加一；

（3） 统计左子树；统计右子树。

伪码算法：

intBiTreeDescendant(BiTree T)

{//统计非空子孙结点数

int staticn=0;//初始化计数器

if(T!=NULL)

{

if(T->lchild)

n++;

if(T->rchild)

n++;

BiTreeDescendant(T->lchild);//统计左子树

BiTreeDescendant(T->rchild);//统计右子树

}

returnn;

}

4）查找二叉树的某个位置的结点（先序序列）

算法描述：

（1） 定义一个静态局部变量，用作记录已查结点的个数；

（2） 从根节点开始，如果相查找的位置理由元素，则打印该元素，如果想查的位置超过二叉树本身的元素数则返回出错。

伪码算法：

intPreOderKNode(BiTree T,intk,TElemType *e)

{//T为二叉树，k为带查找的结点位序；e为指针带值返回查找到的数。

int staticcount=0;//作为计数器，记录已查找的结点数

if(T==NULL)

return0;

count++;//访问结点，对已访问的结点进行计数

if(count==k)//判断该结点是否是待查找的结点

{

e=&T->data;

printf("存在你想查找位置的元素，先序序列中第%d个元素是%c\n",k,*e);

return1;//查找成功

}

else

if(count>k)//计数器count已经超出k，则直接返回0，查找不成功

return 0;

else

{//在左或右子树中查找

if(PreOderKNode(T->lchild,k,e)==0)

return PreOderKNode(T->rchild,k,e);

return1;

}

}

6、主程序的伪码算法：

voidmain()

{

BiTree T=NULL,T_1=NULL,T_2=NULL;

inti=1,*n=0,*kd,k=0;

charx=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为:%d\n",LeafNum(T));//统计叶子数

printf("二叉树的深 度Depth为:%d\n",BiTreeDepth(T));//计算深度

printf("二叉树的宽 度Width为:%d\n",BiTreeWidth(T,i));//计算宽度

//统计非空子孙结点数

printf("二叉树非空子孙结点DescendantNumber数为:%d\n",BiTreeDescendant(T));

kd=JudgeCBT(T);//统计不同度的结点数

printf("二叉树度为1的结点数为:%d，度为2的结点数为:%d\n",kd[1],kd[2]);

//二叉树的基本操作，删除和查找

printf("下面进行二叉数的查找和删除操作\n");

T_2=CopyTree(T);putchar('\n');//运用二叉树的复制操作

printf("复制后的T_2,以先序序列输出:\n");

PreOderTraverse(T_2);putchar('\n');

printf("请输入你想查找在在先序序列的第几个位置的元素\n");

scanf("%d",&k);

if(!PreOderKNode(T_2,k,e))

printf("不存在你想查找的位置\n");

T_1=CopyTree(T);putchar('\n');

printf("复制后的T_1,以先序序列输出:\n");

PreOderTraverse(T_1);putchar('\n'); getchar();

printf("请输入你想删除元素值为多少的结点\n");

x=getchar();getchar();

DeleteXTree(T_1,x);

printf("先序遍历二叉树：\n");

PreOderTraverse(T_1);putchar('\n');

printf("以广义表形式打印二叉树:\n");

print(T_1);putchar('\n');

}

四、调试分析

1、 在调试过程中，在进行二叉树的基本操作时就出现错误了，为了方便检查错误，故逐渐将主函数的谋部分调用的函数先屏蔽后，再运行调试，才发现了错误。

2、 在调试过程中，为了方便对调用函数的检查，每当计数器变化时，就输出该值，就可以看出是哪里的问题。

3、 在调试过程中，在运行删除时，程序出现错误，当输入欲删除结点后，程序并没有删除该结点。后来经过调试才发现，因为在输入删除元素时，是由getchar（）接收，而在查找时遗留下的回车直接被getchar（）接收，当作NULL去运行了。

4、 在调试过程中，更改了4的错误，在删除一个结点后，虽然能删除元素了，但再次打印该树后，就发现每当打印到删除结点位置时，程序就报错。后来经过老师和同学的帮助才发现，虽然将待删结点的空间释放，但并没有把指向该结点的父结点的指针域赋空，后来更改后，程序完美运行了。

5、 从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的队列和链式存储结构的二叉树的应用。

五、用户使用说明

1、 本程序的运行环境为Windows7旗舰版操作系统，执行文件为：二叉树的基本操作及运算.exe；

2、 进入程序后即显示提示信息：“请按先序序列输入各结点”以等待用户输入欲构造的二叉树的各元素值；若用户输入的的是一个不符合先序序列的字符串，则程序报错；

3、 在用户正确输入二叉树的元素后，程序会自动对其先序、中序、后序和层次遍历，并对二叉树进行求叶子数、深度、宽度、非空子孙结点数、度为1的结点数和度为2的结点数。并在自动复制一棵树后，出现“请输入你想查找在先序序列的第几个位置的元素”，等待用户输入欲查找的元素位置；

4、 输入查找的位置后，如果存在该位置的元素，则程序会显示“存在你想查找位置的元素，先序序列中第x个元素是x”；然后会弹出“请输入你想删除元素值为多少的结点”，等待用户输入某个元素值；

5、 输入某个元素值后，若删除成功则会先序遍历和广义表形式打印删除后的二叉树。

6、 本程序要求在输入二叉树元素是一定要正确，空格不能少，也不能多，不然程序会报错。

六、测试结果

1、正确输入：ABC□□DE□G□□F□□□,查找5,删除E

运行界面：

2、正确输入：ABD□□EH□□□CF□G□□□ （以□表示空格）,查找10,删除B

运行界面：

以上结果与自己在进行程序概要分析时的预测结果一致

七、心得体会

这次实验设计让我更加了解并更加灵活运用到大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。

这次实验设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在进行编程时一定要把每个问题都分析清楚，比如自己在编写删除删除BiTree DeleteBiTree(BiTree t)，BiTree DeleteXTree(BiTree t,TElemType x)时，只是把一个指针忘记赋为空，则导致程序报错，希望以后在运用递归调用时，一定要弄清各种值的传递关系。

还有，在编写函数时，编写时能把每一步的结果都打印出来，这能很方便的调试程序。

在编写实验报告时自己无意发现，其实统计非空子孙结点数、不同度的结点数甚至叶子数的函数思想与算法十分相似，都可以编写在一个函数里，这也说明了实验报告的重要性，我们应该在实验报告里多反思、总结，尽量完善自己的程序设计。

程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。

最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。

参考文献：

1.《数据结构(C语言版)》 严蔚敏 清华大学出版社

2.《C程序设计》 谭浩强 清华大学出版社

3.《数据结构题集（C语言版）》严蔚敏 吴伟民 米宁 清华大学出版社

4.《C程序设计学习指导与练习》贾伯琪 中国科学技术大学出版社

八、附录

“二叉树的基本操作及运算”源程序代码：

#include

#include

#include

typedef char TElemType;

char *e;

#define M 10

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

typedef struct QNode{

BiTree data;

struct QNode *next;

}QNode,*Queueptr;

typedef struct{

Queueptr 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;

else

return 0;

}

BiTree CreateBiTree(BiTree T)

{

char ch;

if((ch=getchar())==' ')

T=NULL;

else

if(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;

}

else

return 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;

else

{

hl=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 n[M]={0};

int static max=0;

if(T!=NULL)

{

if(i==1)

{

n[i]++;

i++;

if(T->lchild)

n[i]++;

if(T->rchild)

n[i]++;

}

else

{

i++;

if(T->lchild)

n[i]++;

if(T->rchild)

n[i]++;

}

if(max

max=n[i];

BiTreeWidth(T->lchild,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);

else

newlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);

else

newrptr=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 d[3]={0};

if(T!=NULL)

{

if(T->lchild!=NULL && T->rchild!=NULL)

d[2]++;

else

{

if(T->lchild!=NULL && T->rchild==NULL)

d[1]++;

else

if(T->lchild==NULL && T->rchild!=NULL)

d[1]++;

}

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个元素是%c\n",k,*e);

return 1;

}

else

if(count>k)

return 0;

else

{

if(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;

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为:%d\n",LeafNum(T));

printf("二叉树的深 度Depth为:%d\n",BiTreeDepth(T));

printf("二叉树的宽 度Width为:%d\n",BiTreeWidth(T,i));

printf("二叉树非空子孙结点DescendantNumber数为:%d\n",BiTreeDescendant(T));

kd=JudgeCBT(T);

printf("二叉树度为1的结点数为:%d，度为2的结点数为:%d\n",kd[1],kd[2]);

printf("下面进行二叉数的查找和删除操作\n");

T_2=CopyTree(T);putchar('\n');

printf("复制后的T_2,以先序序列输出:\n");

PreOderTraverse(T_2);putchar('\n');

printf("请输入你想查找在在先序序列的第几个位置的元素\n");

scanf("%d",&k);

if(!PreOderKNode(T_2,k,e))

printf("不存在你想查找的位置\n");

T_1=CopyTree(T);putchar('\n');

printf("复制后的T_1,以先序序列输出:\n");

PreOderTraverse(T_1);putchar('\n'); getchar();

printf("请输入你想删除元素值为多少的结点\n");

x=getchar();getchar();

DeleteXTree(T_1,x);

printf("先序遍历二叉树：\n");

PreOderTraverse(T_1);putchar('\n');

printf("以广义表形式打印二叉树:\n");

print(T_1);putchar('\n');

}