二叉树及其应用(算法与数据结构课程设计).doc

二叉树及其应用
一、问题描述
二叉树是一种常见的数据结构，在实际中应用十分广泛。二叉树有顺序和链式两种存储结构，可以运用递归和非递归设计算法，能够求解节点在二叉树中的层次数等问题。在实际应用中，要求以同学录为例完成系统的设计与管理。
二、基本要求
1、选择合适的存储结构，完成二叉树的建立。最好采用顺序和链式两种方法。
2、在顺序二叉树中求解节点所在层次数。
3、在链式二叉树中求解节点所在层次数。
4、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。
三、测试数据
1、分别以顺序和链式存储测试图示二叉树中节点E所在层次：

2、同学录的测试数据：
"赵一","1979-01-01","15811111111","0807011001"
"钱二","1980-02-02","15822222222","0807011002"
"孙三","1981-03-03","15833333333","0807011003"
"李四","1982-04-04","15844444444","0807011004"
在上表的的基础上，测试表的建立，以及记录的新增、修改、删除等。
四、算法思想
1、在顺序二叉树下求节点所在层次数
本题中顺序二叉树按照满二叉树的原则建立，空节点存“0”。故节点所在层次count与节点下标m有如下关系：
1)初始层次数count=1，当m=0时，所查节点不存在
2)当m非0时，令m=m/2，count加一
3)m不为1时，返回层次数count；m为1时，重复步骤2)
2、在链式二叉树下求节点所在层次数
算法要用非递归算法求解二叉树中给定节点的深度，为实现层次非递归求解，必须借用数据结构保存将要访问的节点，在函数CengciTree(BiTreeLink T,char c)中用数组queue实现此功能。具体编程时，用变量n保存当前访问的节点的层次数目并初始化为1，front和rear是数组queue中当前正在访问的节点的下标以及可插入节点的下标，而flag起到标志作用用来表明是否要增加当前的层次数n。
算法开始时，首先判断树是否为空，若为空树退出程序；若树不为空，则先判断根节点的值是否与要查找节点的值相等，若相等则返回n，否则将当前层次n加1，并将根节点的左孩子、右孩子以及根节点本身插入到数组queue中。可能，有人会问为什么还要将根节点插入到数组queue中？这里，将根节点插入到数组queue中的目的是，当queue[front]保存的是根节点的指针时，二叉树的一层节点遍历结束了，需要将当前层次数n加1并让queue[rear]保存根节点的指针。
算法的核心部分就是while循环里面的内容，首先让标志flag值为0,如果queue[front]不为空且queue[front]->data的值等于要查找的值c，程序结束返回n即可；若queue[front]的值是指向根节点的指针，表明当前层次上的所有节点都已经访问过了，要访问下一个层次的节点了，故要把n加1并让flag值为1以表明在数组的插入位置queue[rear]需要赋值为跟节点的指针；如果，均不是上述情况，则将queue[front]的左孩子、右孩子都放到数组queue中，并将front指向下一个元素。重复上述循环，直到找到了要查找的值，或者遍历了所有的节点。
3、同学录的实现
本题的一个实际应用是实现同学录，我们采用二叉树存储结构，利用预置数组建立二叉树；先序方式遍历二叉树并输出；递归算法实现对同学录的查找；基于查找实现对同学录的修改和新增成员；求所要操作节点的父亲节点，从而顺利的编写对同学录的删除操作。
五、模块划分：
1、在顺序二叉树下求节点所在层次数
（1）void Creattree()其功能是建立顺序二叉树；
（2）void Cengcitree()其功能是求节点层次
2、在链式二叉树下求节点所在层次数
（1）int CreateBiTree(BiTreeLink *T)其功能是建立二叉树；
（2）void PreOrderTraverse(BiTreeLink T) 其功能是先序遍历二叉树；
（3）int CengciTree(BiTreeLink T,char c) 其功能是求层次数
（1）int n=0,front=0,rear=0,flag;初始化队列；
（2）(front+1)%MAXSIZE!=rear判断队列不满。
3、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。
（1）void CreateBiTree(DataType *items,BiTree *T)其功能是建立同学录
（2）void PreOrderTraverse(BiTree T)
（3）PBTNode SearchTree(BiTree T,char *ch)
（4）void ModifyTree(BiTree T)
（5）void DeleteTree(BiTree T)
4、main()主函数，功能是调要相关函数实现问题的求解。
六、数据结构：
1、二叉树的抽象数据类型结构定义：
typedef struct Node
{ TElemType data;
struct Node *lchild,*rchild;
} BiTNode, *BiTreeLink;
2、同学录节点信息：
typedef struct Info{
char name[20]; //姓名
char date[11]; //生日
char phone[12]; //电话
char StudentNum[11];//学号
}DataType;
3、同学录数据存储结构：
typedef struct Node
{ DataType data;
struct Node *left,*right;
}BTNode, *PBTNode,*BiTree;

七、源程序：
1、在顺序二叉树下求节点所在层次数
#define maxlen 100
#include"stdio.h"
typedef struct node
{ char data;
} Bitree[maxlen];
int N; Bitree T;
/*建立二叉树*/
void Creattree()
{ int i; char c;
printf("请输入结点数目(包括空结点)：");
scanf("%d",&N);
printf("请输入结点(空结点为0):");
for(i=1;i<=N;i++)
{
scanf("%s",&c);
T[i].data=c;
}
}
/*求二叉树节点所在层次*/
void Cengcitree()
{
int i,m=0,count=1; char c;
printf("请输入某一结点：");
scanf("%s",&c);
i=1;
while(i<=N)
{
if(T[i].data==c){m=i; break;}
i++;
}
if (m==0)
printf("\n节点不存在");
while(m!=1)
{
m=m/2;
count++;
}
printf("\n节点所在层次:%d\n",count);
}
/*主函数*/
void main()
{
Creattree();
Cengcitree();}
2、在链式二叉树下求节点所在层次数
#include "stdio.h"
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 20
#define NULL 0
typedef char TElemType;

/* 二叉链树的类型定义*/
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTreeLink;

/*先序建立二叉树*/
int CreateBiTree(BiTreeLink *T)
{ char ch;
scanf("%c",&ch);
if (ch==' ')
*T=NULL;
else
{ *T=(BiTreeLink)malloc(sizeof(BiTNode));
if (!(*T)) return 0; /* 未分配到空间错误返回*/
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild); }
return 1; }

/* 先序遍历二叉树*/
void PreOrderTraverse(BiTreeLink T)
{ if (T)
{ printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild); }
}
/*求二叉树节点所在层次数*/
int CengciTree(BiTreeLink T,char c)
{
int n=1,front=0,rear=0,flag;
BiTreeLink queue[MAXSIZE];//
if(!T)
{
printf("树为空!\n");
return n;
}
if(T->data==c)
return n;
queue[rear++]=T->lchild;
queue[rear++]=T->rchild;
queue[rear++]=T;
n++;
while((front+1)%MAXSIZE!=rear)
{
flag=0;
if(queue[front]&&queue[front]->data==c) return n;
if(queue[front]==T)
{
n++;
flag=1;
}
else if(queue[front])
{
queue[rear]=queue[front]->lchild;
rear=(rear+1)%MAXSIZE;
queue[rear]=queue[front]->rchild;
rear=(rear+1)%MAXSIZE;
}
if(flag)
{
queue[rear]=T;
rear=(rear+1)%MAXSIZE;
}
front=(front+1)%MAXSIZE;
}
printf("\n元素%c不存在。\n",c);
return -1;
}
/****主函数****/
int main()
{
BiTreeLink T;
int c=0;
char x;
printf("请输入节点\n"); CreateBiTree(&T);
printf("\n先序:"); PreOrderTraverse(T);
printf("\n请输入节点：");
getchar();
printf("\n请输入要查询的字符：");
scanf("%c",&x);
printf("\n所在层次%3d\n\n",CengciTree(T,x));
system("pause");
return 0;
}
3、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
/****二叉链树的类型定义****/
typedef struct Info{
char name[20]; //姓名
char date[11]; //生日
char phone[12]; //电话
char StudentNum[11];//学号
}DataType;
typedef struct Node
{ DataType data;
struct Node *left,*right;
}BTNode, *PBTNode,*BiTree;
/*****插入（左孩子）****/
PBTNode InsertLeft(PBTNode T,DataType x)
{ PBTNode p;
if(!T) return NULL;
if(T->left ==NULL)
{ p=(PBTNode)malloc(sizeof(BTNode));
p->data=x;
p->left =NULL;
p->right =NULL;
T->left =p;
return p;}
return NULL;
}
/*****插入（右孩子）****/
PBTNode InsertRight(PBTNode T,DataType x)
{ PBTNode p;
if(!T) return NULL;
if(T->right ==NULL)
{ p=(PBTNode)malloc(sizeof(BTNode));
p->data=x;
p->left =NULL;
p->right =NULL;
T->right =p;
return p;}
return NULL;
}
/*****插入****/
void InsertChild(PBTNode T,DataType x)
{ if (T->left==NULL && T->right==NULL && !strcmp(T->data.name ," 无"))
{T->data=x;}
else if (InsertLeft(T,x)) return;
else{
if (InsertRight(T,x)) return;
else InsertChild(T->left ,x);}
}
/****建立二叉树****/
void CreateBiTree(DataType *items,BiTree *T)
{ int i;
printf("本程序通过预置数组建立二叉树\n");
(*T)=(PBTNode)malloc(sizeof(BTNode));
(*T)->left=NULL;
(*T)->right=NULL;
(*T)->data=items[0];
for(i=1;i<4;i++)
{ InsertChild(*T,items[i]);}
}
/****先序遍历二叉树****/
void PreOrderTraverse(BiTree T)
{ if (T)
{printf("\n\t姓名\t\t学号\t\t生日\t\t电话\n");
printf("\n\t%s\t%s\t%s\t%s\n\n",T->data.name,T->data.StudentNum,T->data.date,T->data.phone);
PreOrderTraverse(T->left);
PreOrderTraverse(T->right); }
}
/****查找二叉树****/
PBTNode SearchTree(BiTree T,char *ch)
{ PBTNode flag=NULL;
if (T)
{ if(!strcmp(T->data.name,ch))
{ printf("\n\t%s\t%s\t%s\t%s\n\n",T->data.name,T->data.StudentNum,T->data.date,T->data.phone);
flag=T; return flag;
}
else flag=SearchTree(T->left,ch);
if(flag) return flag;
else
flag=SearchTree(T->right,ch);
}
return flag;
}
/****查找父亲节点****/
PBTNode SearchFather(PBTNode r,BiTree T,int *flag)
{ PBTNode p=NULL;
if(T)
{ if(T->left==r)
{(*flag)=0; p=T;return p;}//flag=0表示左孩子的父亲
else if(T->right==r)
{(*flag)=1; p=T;return p;}
else
{p=SearchFather(r,T->left,flag);
if(p) return p;
else p=SearchFather(r,T->right,flag);}
}
return p;
}
/****修改二叉树****/
void ModifyTree(BiTree T)
{ char ch[20],Mod[12]; PBTNode ModifyNode; int caseflag;
printf("请输入要修改信息的姓名:"); scanf("%s",ch);
ModifyNode=SearchTree(T,ch);
if(!ModifyNode)
printf("\n查找的姓名不存在\n");
else
{while(1){
printf("\n\
1.修改生日\n\
2.修改电话\n\
3.修改学号\n\
4.不修改\n");
scanf("%d",&caseflag);
switch(caseflag)
{case 1:
printf("请输入修改后的生日:");
scanf("%s",Mod);
strcpy(ModifyNode->data.date,Mod);
break;
case 2:
printf("请输入修改后的电话:");
scanf("%s",Mod);
strcpy(ModifyNode->data.phone,Mod);
break;
case 3:
printf("请输入修改后的学号:");
scanf("%s",Mod);
strcpy(ModifyNode->data.StudentNum,Mod);
break;
case 4:return;}
}
}
}
/****删除二叉树****/
void DeleteTree(BiTree T)
{ char ch[20]; PBTNode DelNodeFather,DelNode,p,q;int flag;
printf("请输入要删除信息的姓名:"); scanf("%s",ch);
DelNode=SearchTree(T,ch);
if(!DelNode)
printf("\n查找的姓名不存在\n");
else
{if (T==DelNode)
{if(DelNode->left)
{p=DelNode->left;
while(p->right)
{p=p->right;}
p->right=DelNode->right;
q=DelNode->left;
*DelNode=*q;
q->left=NULL;
q->right=NULL;
free(q);}
else if(DelNode->right)
{ q=DelNode->right;
*DelNode=*q;
q->left=NULL;
q->right=NULL;
free(q);}
else { strcpy(T->data.name," 无");
strcpy(T->data.StudentNum," 无");
strcpy(T->data.date," 无");
strcpy(T->data.phone," 无");}
}
else
{ DelNodeFather=SearchFather(DelNode,T,&flag);
if(DelNode->left)
{p=DelNode->left;
while (p->right)
{p=p->right;}
p->right=DelNode->right;
q=DelNode->left;
*DelNode=*q;
q->left=NULL;
q->right=NULL;
free(q);}
else{ q=DelNode->right;
if(q)
{ *DelNode=*q;
q->left=NULL;
q->right=NULL;
free(q);}
else{ free(DelNode);
if (flag==0) DelNodeFather->left=NULL;
if (flag==1) DelNodeFather->right=NULL;}
}
}
printf("\n删除指定姓名后的同学录\n");
}
}
/****主函数****/
void main()
{ BiTree T;
Int caseflag;
char ch[20];
DataType x={"周五","1983-05-05","15855555555","0807011005"};
DataType items[4]={
{"赵一","1979-01-01","15811111111","0807011001"},
{"钱二","1980-02-02","15822222222","0807011002"},
{"孙三","1981-03-03","15833333333","0807011003"},
{"李四","1982-04-04","15844444444","0807011004"}};
CreateBiTree(items,&T);
printf("\n先序遍历:\n"); PreOrderTraverse(T);

while(1){
printf("\n\
1.按姓名查找\n\
2.新增同学信息\n\
3.修改同学信息\n\
4.删除同学信息\n\
5.退出\n\n");
scanf("%d",&caseflag);
switch(caseflag)
{case 1:
printf("请输入要查找的姓名:"); scanf("%s",ch);
if(!SearchTree(T,ch))
printf("\n查找的姓名不存在\n");
break;
case 2:
printf("\n新增:\n");
InsertChild(T,x);
PreOrderTraverse(T);
break;
case 3:
ModifyTree(T);
PreOrderTraverse(T);
break;
case 4:
DeleteTree(T);
PreOrderTraverse(T);
break;
case 5:return;}
}
}
八、测试结果：
2、在顺序二叉树中求解节点所在层次数。

I

3、在链式二叉树中求解节点所在层次数。

4、以同学录为例，利用二叉树存储结构实现建立、查找、新增、修改、删除等功能。
(1)建立:

2、查找：

3、新增：

4、修改：

5、删除：

九、参考文献
《数据结构C语言版》严蔚敏 吴伟民 主编；
《C语言程序设计》谭浩强 主编；

小结
此次课程设计我们小组的题目是《二叉树的应用》，在老师的指导下，我们首先分析了课程设计的任务、要求和目的，经过小组讨论，明确了题目的含义、所需要的知识，最终确定了问题的解决方案。我主要是对二叉树中节点所在的层次数进行求解，而另两位组员的任务是完成二叉树在现实生活中的具体应用实例的设计，虽然同为二叉树的内容，但是具体方面有些差异，所以经过小组讨论，在征得老师的同意之后，我们分成两小组分别进行课程设计，以下就是我在此次课程设计中的小结：
为了充分利用时间更好的完成老师下达课程设计任务，我温习了之前学习的C语言知识和数据结构中关于队列、二叉树的有关知识，然后充分利用上课时间查阅资料和编写代码，通过对一些现有源代码的研究，以及指导老师提供关于二叉树的部分源代码研究，逐渐对整个课程设计有了更清晰的认识，在脑海中有了明确的设计思路。在编写代码的过程中，由于C语言知识的不扎实，频繁的出现错误，虚心请教老师和同学，经过指导，对程序进行不停的修改和调试，完成了此次课程设计。
本次课程设计训练了我对计算机加工的数据对象进行分析的能力，选择适当的数据结构及相应算法的能力。让我对所学课程内容掌握情况的一次自我验证。同时这些日子里小组同学之间互相学习，探讨算法，才得出此完善的程序，深刻感受到团队合作的力量，当程序完成时我们一个个都感到深深的欣慰，也从实践中学到很多知识。
通过课程设计能提高了我对所学知识的综合应用能力，能全面检查并掌握所学内容；培养了我独立思考、刻苦钻研的精神；在分析问题、解决问题的过程中，让我获得一种成功的喜悦，进而增加其学习和应用的兴趣。
wilyes11收集 博客(与学习无关)：