数据结构课程设计(5)

m=LeafCount(T->leftChild); sum+=m;

n=LeafCount(T->rightchild); sum+=n; }

return sum; }

void PreOrder(BinTree &T) {

if(T) {

printf(\ PreOrder(T->leftChild); PreOrder(T->rightchild); } }

void InOrder(BinTree &T) {

if(T) {

InOrder(T->leftChild); printf(\ InOrder(T->rightchild); } }

void PostOrder(BinTree &T) {

if(T) {

PostOrder(T->leftChild); PostOrder(T->rightchild); printf(\ } }

二叉树的菜单文件 #include #include #include \#include void bitreemenu() {

BinTree T; int sum,i; while(1)

19

{

printf(\printf(\你输入的是2功能: 二叉树基本操作\\n\\n\\n\printf(\printf(\二叉树的创建\\n\\n\printf(\二叉树的前序遍历\\n\\n\printf(\二叉树的中序遍历\\n\\n\printf(\二叉树的后序遍历\\n\\n\printf(\叶子结点个数 \\n\\n\printf(\退出程序\\n\\n\\n\\n\scanf(\if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1) {

printf(\请输入节点信息 :\ T=creatbitree(T); }

else if(i==3) {

printf(\中序遍历为:\ InOrder(T); }

else if(i==2) {

printf(\前序遍历为:\ PostOrder(T); }

else if(i==4) {

printf(\后序遍历为:\ PostOrder(T); }

20

else if(i==5) {

sum=LeafCount(T);

printf(\叶子节点个数：%d\ } else

printf(\输入选择错误！请重新输入\\n \ } }

二叉排序树头文件 #ifndef _BSTREE_H #define _BSTREE_H typedef struct Node{ int key;

struct Node *lchild,*rchild; }Node,*Tree;

void deleteBST(Tree &T,int data); Tree searchBST(Tree root,int data); void InsertBST(Tree &T,int k);

void searchxBST(Tree root,int data); void creatBST(Tree &T); void PrintBST(Tree &T); void BSTmenu(); #endif

最小生成树的头文件 #ifndef _mintree_h #define _mintree_h

#define MaxVertexNum 20 //最大顶点数为20 #define INF 32767 typedef struct {

int vexs[ MaxVertexNum]; //顶点表

int AdjMatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵，即边表 int vexnum,arcnum;//顶点数和边树

}MGragh; //MGragh是以邻接矩阵存储的图类型 typedef struct {

int begin,end;//边顶点序号 int cost;//边上的权值 }TreeEdge;

void CreatMGragh(MGragh &G); void Prim(MGragh &G); void mintreemenu(); #endif

21

最小生成树的源文件 #include #include \

void CreatMGragh(MGragh &G)//建立无向网G的邻接矩阵 {

int i,j,k,x;

printf(\请输入顶点数和边数（输入格式：顶点数,边数）：\\n\ scanf(\ for(i=0;i

printf(\请输入%d条边，格式：行下标,列下标,边上的权值\\n\ for(k=0;k

scanf(\ G.AdjMatrix [i][j]=x;

G.AdjMatrix[j][i]=G.AdjMatrix[i][j]; } }

void Prim(MGragh &G) {

int n=G.vexnum;

int lowerCost[MaxVertexNum],mincost=0,closeVertex[MaxVertexNum]; TreeEdge close[MaxVertexNum]; int i,j,k,sum=0; for(i=1;i

lowerCost[i]=G.AdjMatrix[0][i]; closeVertex[i]=0; }

lowerCost[0]=0; closeVertex[0]=0; for(i=1;i

mincost=INF; j=1;k=1; while(j

if (lowerCost[j]!=0 && lowerCost[j]

mincost=lowerCost[j]; k=j; }

j++;

22

}

close[i-1].begin=closeVertex[k]; close[i-1].end=k;

close[i-1].cost=mincost; sum=sum+mincost; lowerCost[k]=0; for(j=1;j

if(G.AdjMatrix[k][j]

lowerCost[j]=G.AdjMatrix [k][j];closeVertex[j]=k; } }

printf(\最小生成树如下图所示：\\n始点\\t终点\\t权值\\t\\n\ for(i=0;i

printf(\ }

printf(\最小生成树的总权和为%d\\n\}

最小生成树的菜单文件 #include #include \#include void mintreemenu() {

int i; MGragh G;

printf(\ printf(\你输入的是5功能: 最小生成树基本内容\\n\

printf(\ printf(\创建无向图\\n\\n\

printf(\算法生成树\\n\\n\ printf(\退出程序\\n\\n\\n\\n\ while(1) {

printf(\请选择所要操作的项目：\ scanf(\ if(i==0)break; else if(i==1)

CreatMGragh(G); else if(i==2)Prim(G); else

printf(\输入选择错误！请重新输入\\n \ }

23