[实用] C++ 树与图相关模版
请看完后点个赞，谢谢
1 邻接表存图
//邻接表存图模版 22-04-11#include using namespace std;const int N=100;int h[N],vtx[2*N],nxt[2*N],idx=0;void add_edge(int a,int b){nxt[idx]=h[a];h[a]=idx;vtx[idx]=b;idx++;}int main() {ios::sync_with_stdio(0);cin.tie(0);int n,m,a,x,y;cin>>n>>m;//初始化-1memset(h,-1,sizeof(h));for (int i=0;i>a>>x>>y;add_edge(x,y);if (a==1) add_edge(y,x);}int p;for (int i=0;i<=n;i++){p=h[i];//链表指针cout<<i<<":";//循环遍历顶点下面所有链接的点while (p!=-1){cout<<" "<<vtx[p];p=nxt[p];}cout<<endl;}return 0;}2 欧拉回路模版
//欧拉回路模版 22-04-08#includeusing namespace std; int g[110][110],d[110];//保存每个顶点的度int n,m,x,y,cnt=1;//计数器int vis[1010];//保存路径 void dfs(int u){for (int v=1;v>n>>m;memset(g,0,sizeof(g));for (int i=1;i>x>>y;g[x][y]=1;g[y][x]=1;d[x]++;d[y]++;}int start=1;//找奇点for (int i=1;i<=n;i++){if (d[i]%2==1){start=i;break;}}dfs(start);for (int i=1;i<cnt;i++) cout<<vis[i]<<" ";return 0;}3 堆模版
//堆模版 22-03-27#include using namespace std; int heap[11]={0,1,1,2,5,4,4,3,7,6} ;int heapsz=0; void push(int n)//维护大顶堆{int now,next;//指向当前与下一个节点heapsz++;heap[heapsz]=n;now=heapsz;while (now>1){next=now/2;if (heap[now]>=heap[next]) swap(heap[now],heap[next]);else break;now=next;}} void print(){for (int i=1;i<=5;i++) cout<<heap[i]<<" ";} int main(){ios::sync_with_stdio(0);cin.tie(0);//建堆for (int i=1;i>tmp;push(tmp);print();}}4 树的遍历模版
//树的遍历模版 (前序中序后续) 22-03-19#include using namespace std;int n,tr[110];void preorder(int k)//前序{cout<<tr[k]<<" ";//如果有左儿子,就继续perorder(左儿子)if (tr[2*k]!=-1 && 2*k<=n) preorder(2*k);if (tr[2*k+1]!=-1 && 2*k+1<=n) preorder(2*k+1);}void inorder(int k)//中序{if (tr[2*k]!=-1 && 2*k<=n) inorder(2*k);cout<<tr[k]<<" ";//如果有左儿子,就继续inorder(左儿子)if (tr[2*k+1]!=-1 && 2*k+1<=n) inorder(2*k+1);}void postorder(int k)//后序{//如果有左儿子,就继续postorder(左儿子)if (tr[2*k]!=-1 && 2*k<=n) postorder(2*k);if (tr[2*k+1]!=-1 && 2*k+1<=n) postorder(2*k+1);cout<<tr[k]<>n;memset(tr,-1,sizeof(tr));for (int i=1;i>tr[i];cout<<"前序遍历: ";preorder(1);cout<<"\n";cout<<"中序遍历: ";inorder(1);cout<<"\n";cout<<"后序遍历: ";postorder(1);cout<<"\n"; return 0;}
