2.17学习总结

已知二叉树中序，后序 求先序  

#include <stdio.h>
#include <string.h>// 根据中序和后序遍历求先序遍历
void getPreorder(char inorder[], char postorder[], int inStart, int inEnd, int postStart, int postEnd) {if (inStart > inEnd || postStart > postEnd) {return;}// 后序遍历的最后一个元素是根节点char root = postorder[postEnd];printf("%c", root);// 在中序遍历中找到根节点的位置int rootIndex;for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {if (inorder[rootIndex] == root) {break;}}// 计算左子树的节点数量int leftSubtreeSize = rootIndex - inStart;// 递归处理左子树getPreorder(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSubtreeSize - 1);// 递归处理右子树getPreorder(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSubtreeSize, postEnd - 1);
}int main() {char inorder[10], postorder[10];// 读取中序和后序遍历的字符串scanf("%s", inorder);scanf("%s", postorder);int len = strlen(inorder);// 调用函数求先序遍历getPreorder(inorder, postorder, 0, len - 1, 0, len - 1);printf("\n");return 0;
}

已知二叉树中序，先序求后序 

 

#include <stdio.h>
#include <string.h>#define MAXN 30// 根据前序和中序遍历输出后序遍历结果
void getPostorder(char* inorder, char* preorder, int inStart, int inEnd, int* preIndex) {if (inStart > inEnd) return;// 从前序遍历中取出当前根节点char root = preorder[*preIndex];(*preIndex)++;// 在中序遍历中找到根节点的位置int inIndex;for (inIndex = inStart; inIndex <= inEnd; inIndex++) {if (inorder[inIndex] == root) break;}// 递归处理左子树getPostorder(inorder, preorder, inStart, inIndex - 1, preIndex);// 递归处理右子树getPostorder(inorder, preorder, inIndex + 1, inEnd, preIndex);// 输出根节点printf("%c", root);
}int main() {char inorder[MAXN], preorder[MAXN];scanf("%s", inorder);scanf("%s", preorder);int len = strlen(inorder);int preIndex = 0;// 调用函数获取后序遍历结果getPostorder(inorder, preorder, 0, len - 1, &preIndex);return 0;
}

 

#include <stdio.h>
#include <stdlib.h>#define MAX_N 100005// 定义邻接表节点结构
typedef struct Node {int vertex;struct Node* next;
} Node;// 定义队列节点结构
typedef struct QueueNode {int vertex;int distance;
} QueueNode;// 全局变量
Node* adj[MAX_N];
int distance[MAX_N];
int visited[MAX_N];
int n, d;// 创建新的邻接表节点
Node* createNode(int v) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = v;newNode->next = NULL;return newNode;
}// 添加边到邻接表
void addEdge(int u, int v) {Node* newNode = createNode(v);newNode->next = adj[u];adj[u] = newNode;newNode = createNode(u);newNode->next = adj[v];adj[v] = newNode;
}// 广度优先搜索
void bfs() {QueueNode queue[MAX_N];int front = 0, rear = 0;// 初始化起点queue[rear].vertex = 1;queue[rear].distance = 0;rear++;visited[1] = 1;distance[1] = 0;while (front < rear) {QueueNode current = queue[front++];int u = current.vertex;int dist = current.distance;Node* temp = adj[u];while (temp != NULL) {int v = temp->vertex;if (!visited[v]) {visited[v] = 1;distance[v] = dist + 1;queue[rear].vertex = v;queue[rear].distance = dist + 1;rear++;}temp = temp->next;}}
}int main() {// 读取输入scanf("%d %d", &n, &d);// 初始化邻接表、距离数组和访问标记数组for (int i = 1; i <= n; i++) {adj[i] = NULL;distance[i] = -1;visited[i] = 0;}// 构建图for (int i = 0; i < n - 1; i++) {int u, v;scanf("%d %d", &u, &v);addEdge(u, v);}// 进行广度优先搜索bfs();// 统计距离不超过 d 的小企鹅数量int count = 0;for (int i = 2; i <= n; i++) {if (distance[i] != -1 && distance[i] <= d) {count++;}}// 输出结果printf("%d\n", count);return 0;
}