完成二叉树层序遍历的实现 c语言运用队列 数据结构
时间: 2023-11-26 08:03:08 浏览: 107
实现二叉树的层序遍历需要用到队列这一数据结构,具体实现步骤如下:
1. 定义一个队列结构体,并实现队列的基本操作,包括入队、出队、队列是否为空等。
```
typedef struct QueueNode {
TreeNode *val;
struct QueueNode *next;
} QueueNode;
typedef struct {
QueueNode *front;
QueueNode *rear;
int size;
} Queue;
Queue *createQueue() {
Queue *q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
q->size = 0;
return q;
}
bool isEmpty(Queue *q) {
return q->size == 0;
}
void enqueue(Queue *q, TreeNode *val) {
QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->val = val;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}
TreeNode *dequeue(Queue *q) {
if (isEmpty(q)) {
return NULL;
}
QueueNode *node = q->front;
TreeNode *val = node->val;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(node);
q->size--;
return val;
}
```
2. 实现二叉树的层序遍历,使用队列来存储当前层的节点,并逐层遍历。
```
void levelOrder(TreeNode *root) {
if (root == NULL) {
return;
}
Queue *q = createQueue();
enqueue(q, root);
while (!isEmpty(q)) {
int levelSize = q->size;
for (int i = 0; i < levelSize; i++) {
TreeNode *node = dequeue(q);
printf("%d ", node->val);
if (node->left != NULL) {
enqueue(q, node->left);
}
if (node->right != NULL) {
enqueue(q, node->right);
}
}
printf("\n");
}
}
```
以上代码实现了二叉树的层序遍历,可以通过以下测试代码进行测试:
```
int main() {
TreeNode *root = createTree();
printf("层序遍历结果:\n");
levelOrder(root);
return 0;
}
```
其中,`createTree()` 是创建一个二叉树的函数,可以根据需要自行实现。
阅读全文