写一段二叉树的层序遍历代码,用C++语言
时间: 2024-05-01 18:21:34 浏览: 113
以下是C语言的二叉树层序遍历代码:
```c
#include<stdio.h>
#include<stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct QueueNode {
struct TreeNode* node;
struct QueueNode* next;
};
struct Queue {
struct QueueNode* front, * rear;
};
struct QueueNode* createQueueNode(struct TreeNode* node) {
struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
temp->node = node;
temp->next = NULL;
return temp;
}
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(struct Queue* q, struct TreeNode* node) {
struct QueueNode* temp = createQueueNode(node);
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct TreeNode* deQueue(struct Queue* q) {
if (q->front == NULL) {
return NULL;
}
struct TreeNode* temp = q->front->node;
struct QueueNode* tempNode = q->front;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(tempNode);
return temp;
}
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
void printGivenLevel(struct TreeNode* root, int level) {
if (root == NULL) {
return;
}
if (level == 1) {
printf("%d ", root->val);
}
else if (level > 1) {
printGivenLevel(root->left, level - 1);
printGivenLevel(root->right, level - 1);
}
}
void levelOrder(struct TreeNode* root) {
int depth = maxDepth(root);
for (int i = 1; i <= depth; i++) {
printGivenLevel(root, i);
}
}
int main() {
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->right->val = 3;
root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->left->val = 4;
root->left->right->val = 5;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->left->val = 6;
root->right->right->val = 7;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right->left = NULL;
root->right->right->right = NULL;
printf("Level order traversal of binary tree is:\n");
levelOrder(root);
return 0;
}
```
这段代码实现了一个基本的二叉树层序遍历算法,使用了队列来辅助实现。在main函数中,我们手动构建了一个二叉树,并输出了层序遍历的结果。
阅读全文
相关推荐



