数据结构树的有关算法

1、数据结构课程设计任务书学期：11-12-2班级：网络10一、设计目的数据结构是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论 知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学 们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内 部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算 法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作 等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读数据结

2、构课程设计（实习）要求，以学生自学为主、指导教师 指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的 能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情 况，及时地向指导教师汇报。4、编程语言任选。三、设计选题题一：线索二叉树（*）任务：建立中序线索二叉树，并且中序遍历；求中序线索二叉树上已知结点中序的前驱和后继；需求分析和概要设计：建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索 二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍

3、。也可以在遍历的过程中，将 树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。详细设计：树的结构体的声明：typedef char TElemtype;typedef enum PointerTagLink,Thread;/设置标志：Link 为指针，Thread 为线索typedef struct BiThrNode/树结点结构体TElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;相关函数的声明：voidInitBiTree(BiThrTree &T)

4、;/初始化树voidCreatBiTree(BiThrTree &T);/建立二叉树voidInOrderThreading(BiThrTree&Thrt,BiThrTree &T);/中序线索二叉树/线索化/中序遍历求已知结点中序的前驱和后继void InThreading(BiThrTree p);int InOrderTraverse_Thr(BiThrTree T);void InOrderThread_BeAf();初始化树：void InitBiTree(BiThrTree &T)T = new BiThrNode;if(!T) exit(1);T = NULL;建立二叉树：voi

5、d CreatBiTree(BiThrTree &T)char ch;cinch;if(ch =智)T = NULL;elseT = new BiThrNode;if(!T) exit(1);T-data = ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);中序线索二叉树：void InOrderThreading(BiThrTree &Thrt,BiThrTree &T) Thrt = new BiThrNode;/设置头结点if(!Thrt) exit(1); Thrt-LTag = Link;/头结点左边标志为指针Thrt-RTag =Thr

6、ead;/右边的为线索Thrt-rchild = Thrt;/有孩子指向头结点本身if(!T) Thrt-lchild = Thrt; /若树根结点为空，则头结点左孩子指向头结点else/若根结点不为空Thrt-lchild = T;/头结点左孩子指向根结点pre = Thrt;/设置指针pre指向头结点InThreading(T);/线索化树 Tpre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre;线索化树：void InThreading(BiThrTree p)if(p)InThreading(p-lchild);/线索化左子树i

7、f(!p-lchild) p-LTag = Thread; p-lchild = pre;if(!pre-rchild)pre-RTag = Thread; pre-rchild = p;pre = p;InThreading(p-rchild);中序遍历：int InOrderTraverse_Thr(BiThrTree T)BiThrTree p;int i=1;p = T-lchild;while(p!=T)while(p-LTag!=Thread)p = p-lchild;coutdatadata;i+；length+;while(p-RTag=Thread&p-rchild!=T)p

8、 = p-rchild;coutdatadata;/将结点存于数组中i+;length+;p = p-rchild;return OK;测试结果和设计心得体会：建立二叉阕二叉树律斯艮为当输入时表不结点为空:中序遍历为：425163?植输入结点的信息言的甚驱为4Z的启继为S是否继续查找Jress key to continue通过对树的中序线索化使我更加清楚树的有关操作算法,题二：最小生成树问题（*）【问题描述】若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建 设这个通信网，是一个网的最小生成树问题。【系统要求】利用克鲁斯卡尔算法求网的最小生成树。利用普里姆算法

9、求网的最小生成树。要求输出各条边及它们的权值。【测试数据】由学生任意指定，但报告上要求写出多批数据测试结果。【实现提示】通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点 数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的 随机函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既 不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。【选作内容】利用堆排序实现选择权值最小的边。需求分析和概要设计：用克鲁斯卡尔和普里姆算法生成图的最小生成树。首先要构造出图，然后将图生成树，

10、故要 使用邻接矩阵储存图。详细设计：有关结构体的声明：char VertexType;int VRType;char InfoType;struct ArcCell(typedeftypedeftypedeftypedefVRType adj;/VRType是顶点的关系类型。无权图用1或0表示相连否。对带权图，则为权值类型。InfoType *info;/表示相关信息的指针ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;typedef struct（/顶点向量/邻接矩阵图的当前顶点数和弧度数VertexType vexsMAX_VEXTEX_NUM;

11、AdjMatrix arcs;vexnum,arcnum;int MGraph;typedef struct(VertexType adjvex;VRType lowcost;closedge;typedef struct(VertexType begin;VertexType end;VRType weight;EdgeType;相关函数的声明：int CreateGraph(MGraph &G);/创造图后要返回其值int LocateVex(MGraph G,VertexType u);/求点 u 在图中的位置int minmum( closedge closedgeMAX_VEXTEX

12、_NUM);/求最小值函数void MinSpanTree_PRIM(MGraph G,VertexType u); /PRIM 最小生成树void MinSpanTree_KRUSKAL(MGraph G);创造图：int CreateGraph(MGraph &G)int i,j,k,w;VertexType v1,v2;cout请输入顶点数和边数G.vexnumG.arcnum;high=G.arcnum;cout请输入顶点信息endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj =INF

13、INITY;G.=NULL;/ KRUSKAL最小生成树初始化邻接矩阵/最大值8cout请输入每条边对应的两个顶点(v1,v2)及其权值(w)endl;for(k=0;kv1v2w;i=LocateVex(G,v1);j=LocateVex(G,v2);edgesk+1.begin=v1;edgesk+1.end=v2;G.arcsij.adj=w;G.arcsji.adj=w;edgesk+1.weight=w;return OK;PRIM最小生成树：void MinSpanTree_PRIM(MGraph G,VertexType u)int k,j,i;closed

14、ge closedgeMAX_VEXTEX_NUM;cinu;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(closedge);cout 边 ： (closedgek.adjvex,G.vexsk) 权 值 closedgek.lowcostendl;closedgek.lowcost=0;for(j=1;jG.vexnum;+j)if(G.arcskj.adjclo

15、sedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;KRUSKAL最小生成树：void MinSpanTree_KRUSKAL(MGraph G)HeapSort();for(int k=1;k=G.arcnum;k+)coutedgesk.weight ;coutendl;int fatherMAX_VEXTEX_NUM;int i,j,vf1,vf2;for(i=0;iG.vexnum;i+)fatheri=-1;i=0;j=0;while(iG.arcnum&jG.vexnum-1)vf1=Find

16、(father,edgesi+1.begin);vf2=Find(father,edgesi+1.end);if(vf1!=vf2)fathervf2=vf1;j+;cout边：(edgesi+1.begin,edgesi+1.end)权值:edgesi+1.weight ) ) XI c F D B c F E F r lc,f,c,b,a2LD,B,c,ls s.h _l.:h _l.:h _l.:h _l.:h -I.1271 * 工* 通过对图的操作更加明白图与树之间的关系。从而更加熟练的操作图与树。附录：1.线索二叉树代码：#include iostreamusing namespa

17、ce std;3.#define OK 1#define ERROR 06.typedef char TElemtype;typedef enum PointerTagLink,Thread;typedef struct BiThrNodeTElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;14.15.TElemtype e;BiThrTree pre,Thrt;char a100;int length=0;20./初始化树/建立二叉树/建立中序线索二叉/线索化/中序

18、遍历/求已知结点中序的void InitBiTree(BiThrTree &T);void CreatBiTree(BiThrTree &T);void InOrderThreading(BiThrTree &Thrt,BiThrTree &T); 树void InThreading(BiThrTree p);int InOrderTraverse_Thr(BiThrTree T);void InOrderThread_BeAf();前驱和后继27.void InitBiTree(BiThrTree &T) TOC o 1-5 h z T = new BiThrNode;if(!T) exit

19、(1);T = NULL;void CreatBiTree(BiThrTree &T)char ch;cinch;if(ch = ) T = NULL;elseT = new BiThrNode;if(!T) exit(1);T-data = ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild); TOC o 1-5 h z void InOrderThreading(BiThrTree &Thrt,BiThrTree &T)Thrt = new BiThrNode;if(!Thrt) exit(1);Thrt-LTag = Link;Thrt-RTag

20、 =Thread;Thrt-rchild = Thrt;if(!T) Thrt-lchild = Thrt;elseThrt-lchild = T;pre = Thrt;InThreading(T);pre-rchild = Thrt;pre-RTag = Thread;Thrt-rchild = pre; TOC o 1-5 h z void InThreading(BiThrTree p)68.if(p)InThreading(p-lchild);if(!p-lchild)p-LTag = Thread;p-lchild = pre;if(!pre-rchild)pre-RTag = Th

21、read;pre-rchild = p;81.82.83.pre = p;InThreading(p-rchild); TOC o 1-5 h z int InOrderTraverse_Thr(BiThrTree T)BiThrTree p;int i=1;p = T-lchild;while(p!=T)while(p-LTag!=Thread)p = p-lchild;coutdatadata; TOC o 1-5 h z i+;length+;while(p-RTag=Thread&p-rchild!=T)p = p-rchild;coutdatadata;i+;length+;108.

22、109.return OK;void InOrderThread_BeAf()22.123.124.char YES;TElemtype data;bool flag=false;cout请输入结点的信息data;for(int i=1;i=length;i+)if(data=ai)flag = true; if(i=1)coutdata的前驱为NILrchild;else125.coutdata的前驱为ai-1endl;if(i=length)coutdata的后继为NILendl;elsecoutdata的后继为ai

23、+1endl;if(!flag)cout没有该节点endl;cout是否继续查找(Y/N)YES;if(YES=Y|YES=y)InOrderThread_BeAf();void main()BiThrTree T;InitBiTree(T);cout建立二叉树endl;cout二叉树的根为(当输入时表示结点为空)：endl;CreatBiTree(T);InOrderThreading(Thrt,T);cout中序遍历为：endl;InOrderTraverse_Thr(Thrt);coutendl;InOrderThread_BeAf();3.最小生成树代码：#include iostre

24、amusing namespace std;#define OK 1#define ERROR 0#define MAX_VEXTEX_NUM 30/最多结点数#defineMAX_ARC_NUM 1000#defineINFINITY INT_MAX/最大值8typedefchar VertexType;typedefint VRType;typedefchar InfoType;typedefstruct ArcCell(VRType adj;/VRType是顶点的关系类型。无权图用1或0表示相连否。对带权图，则为权值类型。InfoType *info;/表示相关信息的指针14.15.16

25、.5.36.37.ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM; typedef struct( VertexType vexsMAX_VEXTEX_NUM; AdjMatrix arcs;intvexnum,arcnum;MGraph;typedef struct( VertexType adjvex; VRType lowcost; closedge;typedef struct( VertexType begin; VertexTyp

26、e end; VRType weight; EdgeType; MGraph G;/顶点向量/邻接矩阵图的当前顶点数和弧度数high;CreateGraph(MGraph &G);LocateVex(MGraph G,VertexType u);minmum( closedge closedgeMAX_VEXTEX_NUM);/创造图后要返回其值EdgeType edgesMAX_ARC_NUM; int int int int void MinSpanTree_PRIM(MGraph G,VertexType u); void MinSpanTree_KRUSKAL(MGraph G);in

27、t CreateGraph(MGraph &G)int i,j,k,w;VertexType v1,v2;cout请输入顶点数和边数G.vexnumG.arcnum;high=G.arcnum;cout请输入顶点信息endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)/初始化邻接矩阵 TOC o 1-5 h z for(j=0;jG.vexnum;+j)G.arcsij.adj =INFINITY;G.=NULL;cout请输入每条边对应的两个顶点(v1,v2)及其权值(w)endl;for(k=0;kv1v2w;i=LocateVex(

28、G,v1);j=LocateVex(G,v2);edgesk+1.begin=v1;edgesk+1.end=v2;G.arcsij.adj=w;G.arcsji.adj=w;edgesk+1.weight=w; TOC o 1-5 h z return OK;int LocateVex(MGraph G,VertexType u)int i;for(i=0;iG.vexnum;i+)if(u=G.vexsi)return i;return OK;int minmum(closedge closedgeMAX_VEXTEX_NUM)int j,k;int mincost;mincost=INF

29、INITY;for(j=0;jG.vexnum;+j) TOC o 1-5 h z if(closedgej.lowcost!=0&closedgej.lowcostu;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)008.109.110.closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(closedge);cout边：(closedgek.adjvex,G.vexsk

30、)权 值: closedgek.lowcostendl;closedgek.lowcost=0;for(j=1;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;44./权值堆排序

31、void HeapAdjust(int s,int high) edges0.weight=edgess.weight;edges0.begin=edgess.begin;edges0.end=edgess.end;for(int j=2*s;j=high;j*=2)if(jhigh&edgesj.weight=edgesj.weight) break;edgess.weight=edgesj.weight;edgess.begin=edgesj.begin;edgess.end=edgesj.end;s=j;edgess.weight=edges0.weight;edgess.begin=edges0.begin;edgess.end=edges0.end;void HeapSort() for(int i=high/2;i0;-i) Heap