广度优先搜索二叉树C语言
时间: 2023-12-10 20:34:22 浏览: 36
以下是广度优先搜索二叉树的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct Queue {
TreeNode* items[MAX_QUEUE_SIZE];
int front;
int rear;
} Queue;
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
return q;
}
int isQueueEmpty(Queue* q) {
return q->front == -1;
}
int isQueueFull(Queue* q) {
return q->rear == MAX_QUEUE_SIZE - 1;
}
void enqueue(Queue* q, TreeNode* item) {
if (isQueueFull(q)) {
printf("Queue is full\n");
} else {
if (q->front == -1) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = item;
}
}
TreeNode* dequeue(Queue* q) {
TreeNode* item = NULL;
if (isQueueEmpty(q)) {
printf("Queue is empty\n");
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
}
return item;
}
TreeNode* createNode(int data) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void breadthFirstSearch(TreeNode* root) {
if (root == NULL) {
return;
}
Queue* q = createQueue();
enqueue(q, root);
while (!isQueueEmpty(q)) {
TreeNode* current = dequeue(q);
printf("%d ", current->data);
if (current->left != NULL) {
enqueue(q, current->left);
}
if (current->right != NULL) {
enqueue(q, current->right);
}
}
}
int main() {
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Breadth First Search: ");
breadthFirstSearch(root); // 输出:1 2 3 4 5 6 7
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)