使用c语言用循环队列的方法写一个二叉树数据结构
时间: 2023-05-29 13:06:34 浏览: 70
循环队列的方法实现二叉树数据结构可以使用广度优先搜索(BFS)算法。具体步骤如下:
1. 定义二叉树节点结构体,包含节点值、左子节点指针和右子节点指针。
```
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
2. 定义循环队列结构体,包含队列大小、队头、队尾和队列数组。
```
typedef struct Queue {
int size;
int front;
int rear;
TreeNode **array;
} Queue;
```
3. 定义初始化队列函数和入队、出队函数。
```
Queue* createQueue(int size) {
Queue *queue = (Queue*)malloc(sizeof(Queue));
queue->size = size;
queue->front = -1;
queue->rear = -1;
queue->array = (TreeNode**)malloc(size * sizeof(TreeNode*));
return queue;
}
int isFull(Queue *queue) {
return ((queue->rear + 1) % queue->size == queue->front);
}
int isEmpty(Queue *queue) {
return (queue->front == -1);
}
void enqueue(Queue *queue, TreeNode *node) {
if (isFull(queue)) {
return;
}
queue->rear = (queue->rear + 1) % queue->size;
queue->array[queue->rear] = node;
if (queue->front == -1) {
queue->front = queue->rear;
}
}
TreeNode* dequeue(Queue *queue) {
if (isEmpty(queue)) {
return NULL;
}
TreeNode *node = queue->array[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front = (queue->front + 1) % queue->size;
}
return node;
}
```
4. 定义二叉树的BFS函数,使用循环队列实现。
```
void bfs(TreeNode *root) {
if (root == NULL) {
return;
}
Queue *queue = createQueue(100); // 假设队列最大容量为100
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);
}
}
}
```
5. 测试函数,构造一棵二叉树并进行BFS遍历。
```
int main() {
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 6;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 7;
bfs(root);
return 0;
}
```
输出结果为:1 2 3 4 5 6 7。