给我按层次顺序遍历二叉树的c++算法的代码
时间: 2024-05-14 16:16:59 浏览: 62
关于一个数据结构的一个i算法的描述,是二叉树的遍历问题,只有源代码,但是是可以直接运行的,是用C写的二叉树遍历问题.zip
以下是基于递归的二叉树按层次顺序遍历的C代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义树的节点
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 定义队列结构体及方法
struct Queue {
struct Node** items;
int front, rear, size;
};
struct Queue* createQueue(int capacity) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->items = (struct Node**)malloc(capacity * sizeof(struct Node*));
queue->size = capacity;
queue->front = 0;
queue->rear = -1;
return queue;
}
int isEmpty(struct Queue* queue) {
return queue->rear == -1;
}
void enqueue(struct Queue* queue, struct Node* item) {
if (queue->rear == queue->size - 1) {
printf("Queue is full!\n");
return;
}
queue->rear++;
queue->items[queue->rear] = item;
}
struct Node* dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty!\n");
return NULL;
}
struct Node* item = queue->items[queue->front];
queue->front++;
if (queue->front > queue->rear) {
queue->front = 0;
queue->rear = -1;
}
return item;
}
// 定义遍历方法
void levelOrder(struct Node* root) {
struct Queue* queue = createQueue(100);
if (root == NULL) return;
enqueue(queue, root);
while (!isEmpty(queue)) {
struct Node* node = dequeue(queue);
printf("%d ", node->data);
if (node->left != NULL)
enqueue(queue, node->left);
if (node->right != NULL)
enqueue(queue, node->right);
}
}
// 创建节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 初始化二叉树
struct Node* initTree() {
struct Node* 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);
return root;
}
// 主函数
int main() {
struct Node* root = initTree();
printf("按层次顺序遍历二叉树: ");
levelOrder(root);
printf("\n");
return 0;
}
```
阅读全文