能否提供一个关于数据结构(如图)深度优先遍历(DFS)或广度优先遍历(BFS)的典型代码示例,用C语言实现
时间: 2024-12-18 15:19:31 浏览: 3
当然可以。以下是使用 C 语言分别实现二叉树的深度优先搜索(Depth First Search,DFS)和广度优先搜索(Breadth First Search,BFS)的简单例子。
**深度优先搜索(DFS)示例 - 中序遍历(递归实现):**
```c
#include <stdio.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void dfs(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val); // 先访问根节点
dfs(root->left); // 然后左子树
dfs(root->right); // 最后右子树
}
// 示例:
TreeNode* buildTree() {
// 假设这里构建了一个二叉树结构...
}
int main() {
TreeNode* root = buildTree();
dfs(root);
return 0;
}
```
**广度优先搜索(BFS)示例 - 层次遍历:**
```c
#include <stdio.h>
#include <stdlib.h> // 包含队列操作
struct QueueNode {
int data;
struct QueueNode* next;
};
typedef struct QueueNode QueueNode;
QueueNode* createQueueNode(int data) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void enqueue(QueueNode** front, QueueNode* rear, int data) {
if (*front == NULL) {
*front = rear = createQueueNode(data);
} else {
rear->next = createQueueNode(data);
rear = rear->next;
}
}
int dequeue(QueueNode** front, QueueNode** rear) {
if (*front == NULL) return -1; // 队列为空
int data = (*front)->data;
QueueNode* temp = *front;
*front = (*front)->next;
if (*front == NULL) *rear = NULL;
free(temp);
return data;
}
void bfs(TreeNode* root) {
QueueNode* queueFront = NULL;
QueueNode* queueRear = NULL;
if (root != NULL) {
enqueue(&queueFront, &queueRear, root->val);
while (queueFront != NULL) {
TreeNode* node = (TreeNode*)dequeue(&queueFront, &queueRear);
printf("%d ", node->val);
if (node->left) enqueue(&queueFront, &queueRear, node->left->val);
if (node->right) enqueue(&queueFront, &queueRear, node->right->val);
}
}
}
// 示例同上
int main() {
TreeNode* root = buildTree();
bfs(root);
return 0;
}
```
阅读全文