3.21Code

基于二叉链表的二叉树最大宽度的计算

#include<iostream>#define MAXSIZE 1000using namespace std;int k=0;
int m=0; //记录层数 typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;m++; T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 		}
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;m++;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void Traverse(BiTree T,int n[]){if(T){//k代表当前遍历到的层数！ k++;n[k]++;Traverse(T->lchild,n);Traverse(T->rchild,n);k--;}
}void Width(int n[]){int max=n[1];for(int i=2;i<=m;i++)if(max<n[i])max=n[i];cout<<max<<endl;
} int main(){while(true){char ch;int n[100]={0};cin>>ch;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);Traverse(T,n);Width(n);		}return 0;
} 

【思路】每创建一个结点，m++,m维护节点数。

遍历的时候，每进入一层，k++，n[k]++，k维护层数。注意在找完左右子树时，要k--，方便向上层递归

n[i]代表第i个结点对应层的结点个数

最后遍历n数组，找到最大值即可

基于二叉链表的二叉树叶子结点到根结点的路径的求解

#include<iostream>#define MAXSIZE 1000using namespace std;int maxi=0;
int m=0,n=0;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;m++; T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 		}
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;m++;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void Traverse(BiTree T){if(T){m++;Traverse(T->lchild);Traverse(T->rchild);m--;}
}void FindRoad(BiTree T,char path[],int pathlen){if(T){if(T->lchild==NULL && T->rchild==NULL){//叶子节点cout<<T->data;for(int i=pathlen-1;i>=0;i--) cout<<path[i];cout<<endl;}else{path[pathlen]=T->data;pathlen++;FindRoad(T->lchild,path,pathlen);FindRoad(T->rchild,path,pathlen);pathlen--; //很重要 }}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);	Traverse(T);FindRoad(T,path,pathlen);m=0;}return 0;
} 

【思路】重点在于FindRoad函数，参数是path数组和当前path数组应储存的下标

遇到叶子结点时输出整个数组内容，否则存入当前结点名称，进入左右孩子的递归

由以上两题，注意形参是数组时，可以写成int n[ ]的形式

基于二叉链表的二叉树的遍历

#include<iostream>#define MAXSIZE 1000using namespace std;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 		}
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T){if(T){cout<<T->data;PreTraverse(T->lchild);PreTraverse(T->rchild);}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);	PreTraverse(T);cout<<endl;MidTraverse(T);cout<<endl;LastTraverse(T);cout<<endl;}return 0;
} 

基于二叉链表的二叉树结点个数的统计

#include<iostream>#define MAXSIZE 1000using namespace std;int n0=0,n1=0,n2=0;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 		}
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T){if(T){if(T->lchild && T->rchild)n2++;else if(T->lchild && !T->rchild)n1++;else if(!T->lchild && T->rchild)n1++;else n0++;PreTraverse(T->lchild);PreTraverse(T->rchild);}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);	PreTraverse(T);cout<<n0<<" "<<n1<<" "<<n2<<endl;n0=n1=n2=0;}return 0;
} 

基于二叉链表的二叉树高度的计算

#include<iostream>#define MAXSIZE 1000using namespace std;int maxd=0;
typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 		}
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T,int &nowd){if(T){nowd++;maxd=max(nowd,maxd);PreTraverse(T->lchild,nowd);PreTraverse(T->rchild,nowd);nowd--;}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);	int d=0;	PreTraverse(T,d);cout<<maxd<<endl;maxd=0;}return 0;
} 

【注意】最大高度应该用一个全局变量来维护，而每次遍历到的深度则用临时变量来存储和递归传参，在递归前nowd++了，在这一层最终还要nowd--，以便向上回溯！

————————————华丽的分界线————————————————

————————以下是图及应用相关习题————————————————

基于Dijsktra算法的最短路径求解

【Dijkstra算法】

#include <iostream>
#include <cstring>
#define MVNum 100
#define MaxInt 999
using namespace std;typedef struct
{char vexs[MVNum];//点集 int arcs[MVNum][MVNum];//边的邻接矩阵 int vexnum,arcnum;//点数&边数 
}AMGraph;int LocateVex(AMGraph G,char u){//存在则返回u在顶点表中的下标;否则返回-1int i;for(i=0;i<G.vexnum;++i)if(u==G.vexs[i])return i;return -1;}void InitAM(AMGraph &G)
{//初始化图 memset(G.vexs,0,sizeof(G.vexs));//初始化顶点集 for(int i=0;i<MVNum;i++)for(int j=0;j<MVNum;j++)G.arcs[i][j]=MaxInt;return;
}void CreateUDN(AMGraph &G)
{int i,j,k;  //G.vexnum++;for(i=0;i<G.vexnum;i++)cin>>G.vexs[i];for(k=0;k<G.arcnum;k++)//将边录入邻接矩阵，顺便将顶点录入 {char v1,v2;int w;cin>>v1>>v2>>w;//边的端点i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];G.arcs[i][j]=w;G.arcs[k][k]=0;}
}void ShortestPath_DIJ(AMGraph G){ //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 char v0,v1;int S[MVNum];int D[MVNum];int Path[MVNum];cin>>v0>>v1;int v00=LocateVex(G,v0);int n=G.vexnum; int v;                  		//n为G中顶点的个数 for( v = 0; v<n; ++v){             	//n个顶点依次初始化 S[v] = false;                  	//S初始为空集 D[v] = G.arcs[v00][v];           	//将v0到各个终点的最短路径长度初始化 if(D[v]< MaxInt)  Path [v]=v00; //v0和v之间有弧，将v的前驱置为v0 else Path [v]=-1;               	//如果v0和v之间无弧，则将v的前驱置为-1 }//for S[v00]=true;                    	//将v0加入S D[v00]=0;     int w;  int i;               		//源点到源点的距离为0 	
/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/ for(i=1;i<n; ++i){               	//对其余n?1个顶点，依次进行计算 int min= MaxInt;  for(w=0;w<n; ++w) if(!S[w]&&D[w]<min)  {v=w; min=D[w];}         	//选择一条当前的最短路径，终点为v S[v]=true;                   		//将v加入S for(w=0;w<n; ++w) 	//更新从v0出发到集合V?S上所有顶点的最短路径长度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ D[w]=D[v]+G.arcs[v][w];   	//更新D[w] Path [w]=v;              		//更改w的前驱为v }//if }//for   w=LocateVex(G,v1);cout<<D[w]<<endl; char road[G.vexnum];road[0]=G.vexs[w];int t=w;i=0;while(1){  i++;if(t==-1||t==v00)break;road[i]=G.vexs[Path[t]];t=Path[t];	}while(i){if(road[i])cout<<road[i]<<" ";i--;} cout<<road[0];cout<<endl;
}int main()
{	while(1){AMGraph G;InitAM(G);cin>>G.vexnum>>G.arcnum;if(G.vexnum==0&&G.arcnum==0)break;CreateUDN(G);ShortestPath_DIJ(G);}
}