有一二叉链表,试用c语言编写按层次顺序遍历二叉树的算法。
时间: 2024-12-08 11:16:39 浏览: 13
在C语言中,我们可以使用队列数据结构来实现按照层次顺序遍历二叉树(也称为层次遍历或广度优先搜索,BFS)。这里是一个简单的示例,假设我们有一个二叉树节点结构:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义一个队列辅助结构
typedef struct QueueNode {
TreeNode* node;
struct QueueNode* next;
} QueueNode;
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return; // 如果根节点为空,直接返回
QueueNode* queue = (QueueNode*)malloc(sizeof(QueueNode));
queue->node = root;
queue->next = NULL;
while (queue != NULL) {
TreeNode* temp = queue->node;
queue->node = queue->next; // 将当前层节点移出队列
printf("%d ", temp->val); // 输出当前层的值
// 把下一层的节点加入队列
if (temp->left != NULL) {
queue->next = (QueueNode*)malloc(sizeof(QueueNode));
queue->next->node = temp->left;
queue->next->next = NULL;
}
if (temp->right != NULL) {
queue->next = (QueueNode*)malloc(sizeof(QueueNode));
queue->next->node = temp->right;
queue->next->next = NULL;
}
// 移除空指针
if (queue->node == NULL) queue = NULL;
}
free(queue);
}
```
这个函数首先检查根节点是否为空,然后创建一个队列并将根节点入队。接着进入一个循环,只要队列不为空,就取出并处理队列的第一个节点,同时将它的左右子节点(如果存在)加入队列。最后记得释放分配的内存。
阅读全文