二叉树和应用(算法与数据结构课程设计)

./二叉树与其应用一、问题描述二叉树是一种常见的数据结构,在实际中应用十分广泛。二叉树有顺序和链式两种存储结构,可以运用递归和非递归设计算法,能够求解节点在二叉树中的层次数等问题。在实际应用中,要求以同学录为例完成系统的设计与管理。二、基本要求1、选择合适的存储结构,完成二叉树的建立。最好采用顺序和链式两种方法。2、在顺序二叉树中求解节点所在层次数。3、在链式二叉树中求解节点所在层次数。4、以同学录为例,利用二叉树存储结构,实现建立、查找、新增、删除等功能。三、测试数据1、分别以顺序和链式存储测试图示二叉树中节点E所在层次：2、同学录的测试数据："赵一","1979-01-01"钱二","1980-02-02"孙三","1981-03-03"李四","1982-04-04在上表的的基础上,测试表的建立,以与记录的新增、修改、删除等。四、算法思想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<BiTreeLinkT,charc>中用数组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〕voidCreattree<>其功能是建立顺序二叉树；〔2〕voidCengcitree<>其功能是求节点层次2、在链式二叉树下求节点所在层次数〔1〕intCreateBiTree<BiTreeLink*T>其功能是建立二叉树；〔2〕voidPreOrderTraverse<BiTreeLinkT>其功能是先序遍历二叉树；〔3〕intCengciTree<BiTreeLinkT,charc>其功能是求层次数〔1〕intn=0,front=0,rear=0,flag;初始化队列；〔2〕<front+1>%MAXSIZE!=rear判断队列不满。3、以同学录为例,利用二叉树存储结构,实现建立、查找、新增、删除等功能。〔1〕voidCreateBiTree<DataType*items,BiTree*T>其功能是建立同学录〔2〕voidPreOrderTraverse<BiTreeT>〔3〕PBTNodeSearchTree<BiTreeT,char*ch>〔4〕voidModifyTree<BiTreeT>〔5〕voidDeleteTree<BiTreeT>4、main<>主函数,功能是调要相关函数实现问题的求解。六、数据结构：1、二叉树的抽象数据类型结构定义：typedefstructNode{TElemTypedata;structNode*lchild,*rchild;}BiTNode,*BiTreeLink;2、同学录节点信息：typedefstructInfo{ charname[20]; //XX chardate[11]; //生日 charphone[12]; // charStudentNum[11];//学号}DataType;3、同学录数据存储结构：typedefstructNode{DataTypedata;structNode*left,*right;}BTNode,*PBTNode,*BiTree;七、源程序：1、在顺序二叉树下求节点所在层次数#definemaxlen100#include"stdio.h"typedefstructnode {chardata; }Bitree[maxlen]; intN;BitreeT;/*建立二叉树*/voidCreattree<>{inti;charc; printf<"请输入结点数目<包括空结点>：">; scanf<"%d",&N>; printf<"请输入结点<空结点为0>:">; for<i=1;i<=N;i++> { scanf<"%s",&c>; T[i].data=c; }}/*求二叉树节点所在层次*/voidCengcitree<>{ inti,m=0,count=1;charc; 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>;}/*主函数*/voidmain<>{ Creattree<>; Cengcitree<>;}2、在链式二叉树下求节点所在层次数#include"stdio.h"#include<stdlib.h>#include<malloc.h>#defineMAXSIZE20#defineNULL0typedefcharTElemType;/*二叉链树的类型定义*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTreeLink;/*先序建立二叉树*/intCreateBiTree<BiTreeLink*T>{charch;scanf<"%c",&ch>;if<ch==''>*T=NULL;else{*T=<BiTreeLink>malloc<sizeof<BiTNode>>;if<!<*T>>return0;/*未分配到空间错误返回*/<*T>->data=ch;CreateBiTree<&<*T>->lchild>;CreateBiTree<&<*T>->rchild>;}return1;}/*先序遍历二叉树*/voidPreOrderTraverse<BiTreeLinkT>{if<T>{printf<"%c",T->data>;PreOrderTraverse<T->lchild>;PreOrderTraverse<T->rchild>;}}/*求二叉树节点所在层次数*/intCengciTree<BiTreeLinkT,charc>{ intn=1,front=0,rear=0,flag; BiTreeLinkqueue[MAXSIZE];// if<!T> { printf<"树为空!\n">; returnn; }if<T->data==c> returnn;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>returnn; if<queue[front]==T> { n++; flag=1; } elseif<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;}/****主函数****/intmain<>{BiTreeLinkT;intc=0;charx;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">;return0;}3、以同学录为例,利用二叉树存储结构,实现建立、查找、新增、删除等功能。#include"stdio.h"#include"stdlib.h"#include"string.h"/****二叉链树的类型定义****/typedefstructInfo{ charname[20]; //XX chardate[11]; //生日 charphone[12]; // charStudentNum[11];//学号}DataType;typedefstructNode{DataTypedata;structNode*left,*right;}BTNode,*PBTNode,*BiTree;/*****插入〔左孩子〕****/PBTNodeInsertLeft<PBTNodeT,DataTypex>{PBTNodep;if<!T>returnNULL;if<T->left==NULL>{ p=<PBTNode>malloc<sizeof<BTNode>>; p->data=x; p->left=NULL; p->right=NULL; T->left=p; returnp;}returnNULL;}/*****插入〔右孩子〕****/PBTNodeInsertRight<PBTNodeT,DataTypex>{PBTNodep;if<!T>returnNULL;if<T->right==NULL>{ p=<PBTNode>malloc<sizeof<BTNode>>; p->data=x; p->left=NULL; p->right=NULL; T->right=p; returnp;}returnNULL;}/*****插入****/voidInsertChild<PBTNodeT,DataTypex>{ if<T->left==NULL&&T->right==NULL&&!strcmp<T->,"无">> {T->data=x;} elseif<InsertLeft<T,x>>return; else{ if<InsertRight<T,x>>return; elseInsertChild<T->left,x>;}}/****建立二叉树****/voidCreateBiTree<DataType*items,BiTree*T>{inti;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]>;}}/****先序遍历二叉树****/voidPreOrderTraverse<BiTreeT>{if<T>{printf<"\n\tXX\t\t学号\t\t生日\t\t\n">;printf<"\n\t%s\t%s\t%s\t%s\n\n",T->,T->data.StudentNum,T->data.date,T->data.phone>;PreOrderTraverse<T->left>;PreOrderTraverse<T->right>;}}/****查找二叉树****/PBTNodeSearchTree<BiTreeT,char*ch>{ PBTNodeflag=NULL; if<T> { if<!strcmp<T->,ch>> { printf<"\n\t%s\t%s\t%s\t%s\n\n",T->,T->data.StudentNum,T->data.date,T->data.phone>; flag=T;returnflag; } elseflag=SearchTree<T->left,ch>; if<flag>returnflag; else flag=SearchTree<T->right,ch>; } returnflag;}/****查找父亲节点****/PBTNodeSearchFather<PBTNoder,BiTreeT,int*flag>{PBTNodep=NULL; if<T> {if<T->left==r> {<*flag>=0;p=T;returnp;}//flag=0表示左孩子的父亲 elseif<T->right==r> {<*flag>=1;p=T;returnp;} else {p=SearchFather<r,T->left,flag>; if<p>returnp;elsep=SearchFather<r,T->right,flag>;} }returnp;}/****修改二叉树****/voidModifyTree<BiTreeT>{charch[20],Mod[12];PBTNodeModifyNode;intcaseflag;printf<"请输入要修改信息的XX:">;scanf<"%s",ch>;ModifyNode=SearchTree<T,ch>;if<!ModifyNode> printf<"\n查找的XX不存在\n">;else{while<1>{printf<"\n\ 1.修改生日\n\ 2.修改\n\ 3.修改学号\n\ 4.不修改\n">;scanf<"%d",&caseflag>;switch<caseflag>{case1:printf<"请输入修改后的生日:">; scanf<"%s",Mod>;strcpy<ModifyNode->data.date,Mod>; break;case2:printf<"请输入修改后的:">; scanf<"%s",Mod>;strcpy<ModifyNode->data.phone,Mod>; break;case3:printf<"请输入修改后的学号:">; scanf<"%s",Mod>;strcpy<ModifyNode->data.StudentNum,Mod>; break;case4:return;}}}}/****删除二叉树****/voidDeleteTree<BiTreeT>{charch[20];PBTNodeDelNodeFather,DelNode,p,q;intflag;printf<"请输入要删除信息的XX:">;scanf<"%s",ch>;DelNode=SearchTree<T,ch>;if<!DelNode> printf<"\n查找的XX不存在\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>;} elseif<DelNode->right> { q=DelNode->right; *DelNode=*q; q->left=NULL; q->right=NULL; free<q>;} else{ strcpy<T->,"无">; 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删除指定XX后的同学录\n">; }}/****主函数****/voidmain<>{BiTreeT;Intcaseflag;charch[20];DataTypex={"周五","1983-05-05DataTypeitems[4]={ {"赵一","1979-01-01 {"钱二","1980-02-02 {"孙三","1981-03-03 {"李四","1982-04-04CreateBiTree<items,&T>;printf<"\n先序遍历:\n">;PreOrderTraverse<T>;while<1>{printf<"\n\ 1.按XX查找\n\ 2.新增同学信息\n\ 3.修改同学信息\n\ 4.删除同学信息\n\ 5.退出\n\n">;scanf<"%d",&caseflag>;switch<caseflag>{case1: printf<"请输入要查找的XX:">;scanf<"%s",ch>; if<!SearchTree<T,ch>> printf<"\n查找的XX不存在\n">; break;case2: printf<"\n新增:\n">