A.二叉链表存储的二叉树
定义节点 --- 建立二叉树的函数 --- 前序遍历函数 --- 中序遍历函数
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Node{ //节点，用char存储本身的数据，指针指向左右节点
char data;
Node *lc;
Node *rc;
Node(char c):data(c),lc(NULL),rc(NULL){}
};
Node* build(string s,int& i){ //i代表当前的位置
if(i>=s.length()||s[i]==' ') return NULL;
Node* root = new Node(s[i]);
i++;
root->lc=build(s,i);
i++;
root->rc=build(s,i);
return root;
}
void pre_order(Node *root){
if(root==NULL) return;
cout<<root->data<<' ';
pre_order(root->lc);
pre_order(root->rc);
}
void mid_order(Node*root){
if(root==NULL) return ;
mid_order(root->lc);
cout<<root->data<<' ';
mid_order(root->rc);
}
void midord(Node *root){
}
int main() {
string s;
getline(cin,s);
int i=0;
Node *root = build(s,i);
pre_order(root);
cout<<'\n';
mid_order(root);
cout<<'\n';
mid_order(root);
}B.哈夫曼树
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//定义一个结点类，包含权值和左右子结点
class Node {
public:
int weight;
Node* left;
Node* right;
Node(int w) {
weight = w;
left = NULL;
right = NULL;
}
};
//定义一个比较函数，用于优先队列的排序
struct cmp {
bool operator()(Node* a, Node* b) {
return a->weight > b->weight; //权值小的优先
}
};
//计算哈夫曼树的权值和
int huffmanSum(Node* root, int depth) {
if (root == NULL) return 0; //空结点返回0
if (root->left == NULL && root->right == NULL) return root->weight * depth; //叶子结点返回权值乘以深度
return huffmanSum(root->left, depth + 1) + huffmanSum(root->right, depth + 1); //非叶子结点递归计算左右子树的和
}
int main() {
int n; //叶结点个数
while (cin >> n) { //多组输入
priority_queue<Node*, vector<Node*>, cmp> pq; //创建一个优先队列，用于存储结点指针
for (int i = 0; i < n; i++) {
int w; //输入权值
cin >> w;
Node* node = new Node(w); //创建一个新的结点
pq.push(node); //将结点指针入队
}
while (pq.size() > 1) { //当队列中还有多于一个结点时，循环执行以下操作
Node* left = pq.top(); //取出队首的最小权值结点，作为左子结点
pq.pop(); //出队
Node* right = pq.top(); //取出队首的次小权值结点，作为右子结点
pq.pop(); //出队
Node* parent = new Node(left->weight + right->weight); //创建一个新的父结点，其权值为左右子结点的和
parent->left = left; //连接左子结点
parent->right = right; //连接右子结点
pq.push(parent); //将父结点入队
}
Node* root = pq.top(); //最后队列中只剩一个结点，即为哈夫曼树的根结点
cout << huffmanSum(root, 0) << endl; //输出哈夫曼树的权值和，初始深度为0
}
return 0;
}C.
#include <iostream>
#include <vector>
using namespace std;
vector<int> in, pre, post;
bool unique = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
if(preLeft == preRight) {
in.push_back(pre[preLeft]);
return;
}
if (pre[preLeft] == post[postRight]) {
int i = preLeft + 1;
while (i <= preRight && pre[i] != post[postRight-1]) i++;
if (i - preLeft > 1)
getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
else
unique = false;
in.push_back(post[postRight]);
getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
}
}
int main() {
int n;
scanf("%d", &n);
pre.resize(n), post.resize(n);
for (int i = 0; i < n; i++)
scanf("%d", &pre[i]);
for (int i = 0; i < n; i++)
scanf("%d", &post[i]);
getIn(0, n-1, 0, n-1);
printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
for (int i = 1; i < in.size(); i++)
printf(" %d", in[i]);
printf("\n");
return 0;
}D.最短路径
dfs搜索即可。记得开long long
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5;
int n,m;
int len[150][150];
bool t[150][150];
bool is[150][150];
ll ans=0;
void dfs(int x,int y,int cnt){
if(x==y){
if(ans==0){
ans=cnt;
}
else {
if(ans>cnt)
ans=cnt;
}
return ;
}
for(int i=1;i<=n;i++){
if(i==x) continue;
if(len[x][i]!=0&&is[x][i]!=1){
is[x][i]=1;
dfs(i,y,cnt+len[x][i]);
}
}
}
int main(){
cin>>n>>m;
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
len[x][y]=z;
}
cin>>x>>y;
dfs(x,y,0);
ans==0? cout<<"STOP":cout<<ans;
return 0;
} E.
#include <iostream>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f; // 定义一个无穷大的常量，用于表示没有直接连接的情况
struct Edge {
int from; // 边的起点
int to; // 边的终点
int cost; // 边的代价
Edge(int f, int t, int c): from(f), to(t), cost(c) {} // 构造函数
};
int prim(vector<vector<int>>& graph, vector<Edge>& tree) { // 根据邻接矩阵构建最小生成树，并返回总代价
int n = graph.size(); // 图中顶点的个数
vector<int> pre(n, -1); // 前驱数组，存储每个顶点的前驱顶点的索引，初始为-1
vector<bool> visited(n, false); // 访问标记数组，初始为false
vector<int> dist(n, INF); // 距离数组，存储每个顶点到当前生成树的最短距离，初始为无穷大
int total = 0; // 总代价，初始为0
dist[0] = 0; // 从第一个顶点开始构建最小生成树，将其距离设为0
for (int i = 0; i < n; i++) { // 循环n次，每次加入一个顶点到最小生成树中
int u = -1; // 用于寻找距离最小的顶点的索引，初始为-1
int minDist = INF; // 用于记录最小距离，初始为无穷大
for (int j = 0; j < n; j++) { // 遍历所有顶点
if (!visited[j] && dist[j] < minDist) { // 如果该顶点没有被访问过，且其距离小于当前最小距离
u = j; // 更新最小距离顶点的索引
minDist = dist[j]; // 更新最小距离
}
}
if (u == -1) return -1; // 如果没有找到合适的顶点，说明图不连通，返回-1
visited[u] = true; // 将找到的顶点标记为已访问
total += minDist; // 将最小距离加入总代价中
if (i > 0) tree.push_back(Edge(u, pre[u], minDist)); // 如果不是第一个顶点，将对应的边加入最小生成树中，pre[u]表示u的前驱顶点
for (int v = 0; v < n; v++) { // 遍历所有顶点，更新距离数组和前驱数组
if (!visited[v] && graph[u][v] < dist[v]) { // 如果该顶点没有被访问过，且u到v的边的代价小于当前距离
dist[v] = graph[u][v]; // 更新距离
pre[v] = u; // 更新前驱
}
}
}
return total; // 返回总代价
}
int main() {
int n; // 图中顶点的个数
cin >> n; // 输入顶点个数
vector<vector<int>> graph(n, vector<int>(n)); // 邻接矩阵，初始为n*n的二维向量
vector<Edge> tree; // 最小生成树，初始为空
for (int i = 0; i < n; i++) { // 输入邻接矩阵
for (int j = 0; j < n; j++) {
cin >> graph[i][j]; // 输入第i行第j列的元素，即i到j的边的代价，如果为0表示没有直接连接
if (graph[i][j] == 0) graph[i][j] = INF; // 将0替换为无穷大，方便后续处理
}
}
int result = prim(graph, tree); // 调用prim函数构建最小生成树，并得到总代价
if (result == -1) { // 如果返回值为-1，说明图不连通
cout << "The graph is not connected." << endl; // 输出提示信息
} else { // 如果返回值不为-1，说明图连通
cout << result << endl; // 输出总代价
}
return 0; // 程序结束
}