首页深度优先遍历和广度C语言代码

深度优先遍历和广度C语言代码

时间: 2024-10-15 10:08:00 浏览: 72

深度优先搜索（Depth First Search，DFS）是一种用于图或树的遍历算法，它从根节点开始，尽可能深地探索每个分支，直到到达叶子节点，然后回溯到上一层继续探索其他未访问过的节点。在C语言中，你可以使用递归的方式来实现深度优先遍历。这里是一个简单的二叉树深度优先遍历的示例： ```c #include <stdio.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 递归版深度优先遍历（前序遍历） void dfs(TreeNode* root) { if (root != NULL) { printf("%d ", root->val); // 访问当前节点 dfs(root->left); // 递归左子树 dfs(root->right); // 递归右子树 } } int main() { // 创建一个示例二叉树... TreeNode* root = ...; // 初始化节点 dfs(root); return 0; } ``` 对于广度优先搜索（Breadth First Search，BFS），你需要借助队列来逐层遍历。以下是C语言中的BFS示例： ```c #include <stdio.h> #include <stdlib.h> // 二叉树结构体同上 // BFS遍历 void bfs(TreeNode* root) { if (root == NULL) return; Queue queue; initQueue(&queue); // 初始化队列 enqueue(&queue, root); // 入队根节点 while (!isEmpty(&queue)) { TreeNode* node = dequeue(&queue); // 出队 printf("%d ", node->val); if (node->left != NULL) enqueue(&queue, node->left); if (node->right != NULL) enqueue(&queue, node->right); } } int main() { // 示例二叉树初始化... TreeNode* root = ...; bfs(root); return 0; } ```

阅读全文