层次遍历二叉树c语言

### C语言实现二叉树的层次遍历 在C语言中，可以通过队列来实现二叉树的层次遍历。以下是具体的实现方法： #### 数据结构定义 为了表示二叉树节点，可以定义如下结构体： ```c typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; } BiTree; ``` #### 层次遍历的核心逻辑 层次遍历的关键在于利用队列存储当前层的节点，并逐层处理这些节点。具体过程如下： 1. 初始化一个空队列。 2. 将根节点加入队列。 3. 当队列不为空时，执行以下操作： - 取出队首节点并访问其数据。 - 如果该节点存在左子树，则将左子树节点加入队列。 - 如果该节点存在右子树，则将右子树节点加入队列。 #### 实现代码示例 下面是完整的C语言代码实现层次遍历的功能： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点 typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; } BiTree; // 队列节点 typedef struct QueueNode { BiTree* tree_node; struct QueueNode* next; } QNode; // 链式队列 typedef struct LinkQueue { QNode* front; // 队头指针 QNode* rear; // 队尾指针 } LinkQueue; // 初始化队列 void InitQueue(LinkQueue* queue) { queue->front = queue->rear = (QNode*)malloc(sizeof(QNode)); queue->front->next = NULL; } // 判断队列是否为空 int IsEmpty(LinkQueue* queue) { return queue->front == queue->rear; } // 入队操作 void EnQueue(LinkQueue* queue, BiTree* node) { QNode* temp = (QNode*)malloc(sizeof(QNode)); temp->tree_node = node; temp->next = NULL; queue->rear->next = temp; queue->rear = temp; } // 出队操作 BiTree* DeQueue(LinkQueue* queue) { if (IsEmpty(queue)) return NULL; QNode* temp = queue->front->next; BiTree* res = temp->tree_node; queue->front->next = temp->next; if (queue->rear == temp) queue->rear = queue->front; free(temp); return res; } // 创建二叉树 BiTree* CreateTree() { BiTree* T = (BiTree*)malloc(sizeof(BiTree)); char data; scanf(" %c", &data); // 注意前面加空格以忽略可能存在的多余字符 if (data == '#') { return NULL; } else { T->data = data; printf("请输入%c的左子树: ", data); T->lchild = CreateTree(); printf("请输入%c的右子树: ", data); T->rchild = CreateTree(); return T; } } // 层次遍历函数 void LevelOrderTraversal(BiTree* root) { if (!root) return; LinkQueue queue; InitQueue(&queue); EnQueue(&queue, root); while (!IsEmpty(&queue)) { BiTree* current = DeQueue(&queue); printf("%c ", current->data); if (current->lchild != NULL) { EnQueue(&queue, current->lchild); } if (current->rchild != NULL) { EnQueue(&queue, current->rchild); } } } ``` 上述代码实现了通过队列完成二叉树的层次遍历功能[^2]。 #### 输出样例 假设输入的二叉树为 `A B D E # # F G H I J K`（其中 `#` 表示空节点），运行程序后会按照层次顺序依次输出各节点的数据。 --- 问题