（1）.给出二叉树结点的数据类型定义；
（2）.给出C语言描述算法；
【1】：
typedef struct node { int weight; struct node *left,*right; //指向结点左右子女的指针 }BiNode,*BiTree;
【2】：
int WPL=0; void inorder(BiTree bt,level lv) //bt是二叉树，lv是结点的层次，初值为1 { if(bt) {inorder (bt->left,lv+1); //中序遍历左子树 if(bt->left==null &&bt->right==null) //判断该结点是否为叶子 WPL+=(lv-1)*bt->weight; //累加结点带权路径长度 inorder(bt->right,lv+1); } }
【先序遍历】NLR（递归）
void PreOrder(BiTree T){ if(T!=NULL){ visit(T); //访问根结点 PreOrder(T->lchild); //递归遍历左子树 preOrder(T->rchild); } }
【中序遍历】LNR（递归）
void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); visit(T); InOrder(T->rchild); } }
【后序遍历】LRN（递归）
void PostOrder(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
【先序非递归遍历】
void PreOrderTraverse(BiTree b){ InitStack(S); BiTree p=b; //工作指针p while(p||!IsEmpty(S)){ while(p){ Printf(“%c”,p->data); //先序先遍历结点 Push(S,p); //进栈保存 p=p->lchild; } if(!IsEmpty(S)){ p=Pop(S); p=p->rchild; } } }
【中序非递归遍历】
void InOrder(BiTree b){ InitStack(S); BiTree p=b; while(p||!IsEmpty(S)){ //栈不空或P不空时循环 if(p){ //根指针进栈，遍历左子树 Push(S,p); //每遇到非空二叉树先向左走 p=p->lchild; } else{ //根指针退栈，访问根结点，遍历右子树 Pop(S,p); visit(b); p=p->rchild; //再向右子树走 } } }
【后序非递归遍历】
1 void PostOrder(BiTree b){ 2 3 InitStack(S); 4 5 BiTree p=b,r=NULL; //工作指针P,辅助指针r 6 7 while(p||!IsEmpty(S)){ 8 9 //1.从根结点到最左下角的左子树都入栈 10 11 if(p){ 12 13 Push(S,p); 14 15 p=p->lchild; 16 17 } 18 19 //2.返回栈顶的两种情况 20 21 else{ 22 23 GetTop(S,p); //取栈顶，不是出栈！ 24 25 //1）右子树还未访问，而且右子树不空，第一次栈顶 26 27 if(p->rchild&&p->rchild!=r) 28 29 p=p->rchild; 30 31 //2）右子树已经访问或为空，接下来出栈访问结点 32 33 else{ 34 35 Pop(S,p); 36 37 Printf(“%c”,p->data); 38 39 r=p; //指向访问过的右子树根结点 40 41 p=NULL; //使p为空从而继续访问栈顶 42 43 } 44 45 }
【层次遍历】
void LevelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); //将根结点入队 while(!IsEmpty(Q)){ //队列不空循环 DeQueue(Q,P); //对头元素出队 visit(p); if(p->lchild!=NULL) EnQueue(Q,p->lchild); //左子树不空，则左子树入队列 if(p->rchild!=NULL) EnQueue(Q,p->rchild); //右子树不空，则右子树入队列 }
设计一个算法，从大到小输出二叉排序树中所有其值不小于k 的关键字。
【分析】：
为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树。
【算法】：
void OutPut(BSTNode *bt,KeyType k){ if(bt==NULL) return ; if(bt->rchild!=NULL) OutPut(bt->rchild,k); //递归输出右子树结点 if(bt->data>=k) Printf(“%d”,bt->data); //只输出大于等于k的结点值 if(bt->lchild!=NULL) OutPut(bt->lchild,k); //递归输出左子树的结点 }
【图的邻接矩阵存储结构定义】
#define MaxVertexNum 100 //顶点数目的最大值 typedef char VertextType; //顶点的数据类型 typedef int EdgeType; //带权图中边上权值的数据类型 typedef struct{ VertexType Vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表 int vexnum,arcnum; //图的当前顶点数和弧数 }MGraph;
【图的邻接表存储结构定义】
#define MaxVertexNum 100 //图中顶点数目的最大值 typedef struct ArcNode{ //边表结点 int adjvex; //该弧所指向的顶点的位置 struct ArcNode *next; //指向下一条弧的指针 //InfoType info; //网的边权值 }ArcNode; typedef struct VNode{ //顶点表结点 VertextType data; //顶点信息 ArcNode *first; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MaxVertexNum]; typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; //图的顶点数和弧数 }ALGraph; //ALGraph是以邻接表存储的图类型
图的遍历：
【BFS算法】：
1 #define MaxSize 100; 2 3 bool visited[MaxSize]; //访问标记数组 4 5 void BFS(Graph G,int v){ 6 7 ArcNode *p; 8 9 InitQueue(Q); 10 11 visit(v); 12 13 visited[v]=TRUE; //对v做已访问标记 14 15 Enqueue(Q,v); 16 17 while(!IsEmpty(Q)){ 18 19 DeQueue(Q,v); 20 21 p=G->adjList[v].firstedge; //指针P指向当前顶点的边表链表头指针 22 23 while(p){ 24 25 if(!visited[p->adjvex]){ //P所指向顶点如果未被访问 26 27 visit(p->adjvex); 28 29 visited[p->adjvex]=TRUE; 30 31 EnQueue(Q,p->adjvex); //这个顶点入队列 32 33 } 34 35 p=p->next; //p指向该顶点的下一条边 36 37 } 38 39 } 40 41 } 42 43 void BFSTraverse(Graph G){ 44 45 for(i=0;i<G.vexnum;i++) 46 47 visited[i]=FALSE; //访问标记数组初始化 48 49 for(i=0;i<G.vexnum;i++){ //从0号顶点开始遍历 50 51 if(!visited[i]) //对每个连通分量调用一次BFS 52 53 BFS(G,i);f //vi未访问过，从vi开始BFS 54 55 } 56 57 }
【BFS算法求解单源最短路径问题】
void BFS_MIN_Distance(Graph G,int u){ //d[i]表示从u到i结点的最短路径 for(i=0;i<G.vexnum;++i) d[i]=65535; //初始化路径长度 visited[u]=TRUE; d[u]=0; EnQueue(Q,u); while(!IsEmpty(Q)){ //BFS算法主过程 DeQueue(Q,u); //对头元素u出队 for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)) if(!visited[w]){ //w为u的尚未访问的邻接顶点 visited[w]=TRUE; //设已访问标记 d[w]=d[u]+1; //路径长度加1 EnQueue(Q,w); //顶点w入队 }//if }//while }
【DFS算法】(递归)
1 #define MaxSize 100; 2 3 bool visited[MaxSize]; 4 5 void DFS(Graph G,int v){ 6 7 ArcNode *p; 8 9 visit(v); 10 11 visited[v]=TRUE; //设已访问标记 12 13 p=G->adjList[v].firstarc; 14 15 while(p!=NULL){ //没遍历完顶点的所有邻接顶点 16 17 if(!visited[p->adjvex]){ //如果该顶点没被访问 18 19 DFS(G,p->adjvex); //递归访问该顶点 20 21 } 22 23 p=p->nextarc; //看还有没有其他未访问的顶点 24 25 } 26 27 } 28 29 void DFSTraverse(Graph G){ 30 31 int i; 32 33 for(i=0;i<G->vexnum;i++) 34 35 visited[i]=false; 36 37 for(i=0;i<G->vexnum;i++) 38 39 if(!visited[i]) 40 41 DFS(G,i); 42 43 }
(非递归）邻接表存储
【DFS非递归算法】：
void DFS_Non_RC(AGraph &G,int v){ //从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点 int w; //顶点序号 InitStack(S); for(i=0;i<G.vexnum;i++) visited[i]=FALSE; //初始化visited Push(S,v); visited[v]=TRUE; //v入栈并置visited[v] while(!IsEmpty(S)){ k=Pop(S); //栈中退出一个顶点 visit(v); //先访问，再将其子结点入栈 for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)) //k所有邻接点 if(!visited[w]){ //未进过栈的顶点进栈 Push(S,w); visited[w]=true; //作标记，以免再次入栈 }//if }//while }
【拓扑排序算法】：
1 bool TopologicalSort(Graph G){ 2 3 //如果G存在拓扑排序，返回truel;否则返回false,这时G中存在环 4 5 InitStack(S); 6 7 for(int i=0;i<G.vexnum;i++) 8 9 if(indegree[i]==0) 10 11 Push(S,i); //将所有入度为0的顶点进栈 12 13 int count=0; //计数，记录当前已经输出的顶点数 14 15 while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点 16 17 Pop(S,i); //栈顶元素出栈 18 19 print[count++]=i; //输出顶点i 20 21 for(p=G.vertices[i].firstarc;p;p=p->nextarc){ 22 23 //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S 24 25 v=p->adjvex; 26 27 if(!(- -indegree[v])) 28 29 Push(S,v); //入度为0，则入栈 30 31 }//for 32 33 }//while 34 35 if(count<G.vexnum) 36 37 return false; //排序失败，有向图中有回路 38 39 else 40 41 return true; //成功 42 43 }
【直接插入排序算法】
void InsertSort(ElemType A[],int n){ int i,j; for(i=2;i<=n;i++) //依次将A[2]~A[n]插入到前面已排序序列 if(A[i].key<A[i-1].key){ //若A[i]的关键码小于其前驱，需将A[i]插入有序表 A[0]=A[i]; //复制为哨兵，A[0]不存放元素 for(j=i-1;A[0].key<A[j].key;--j) //从后往前查找待插入位置 A[j+1]=A[j]; //向后挪位 A[j+1]=A[0]; //复制到插入位置 } }
【冒泡排序算法】：
void BubbleSort(ElemType A[],int n){ //将序列A中的元素按从小到大排序 for(i=0;i<n-1;i++){ flag=false; //表示本趟冒泡是否发生交换的标志 for(j=n-1;j>i;j--) //一趟冒泡过程 if(A[j-1].key>A[j].key){ //若为逆序 swap(A[j-1],A[j]); flag=true; } if(flag==false) return ; //本趟遍历后没有发生交换，说明表已经有序 } }
【折半查找】：
int Binary_Search(SeqList L,ElemType key){ //在有序表L中查找关键字为key的元素，若存在返回其位置， int low=0,high=L.TableLen-1,mid; while(low<=high){ mid=(low+high)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]>key) high=mid-1; else low=mid+1; //从后半部分继续查找 } return -1; }
原文：https://www.cnblogs.com/itzine/p/11523979.html