C语言实现二叉树层次遍历

"层次遍历二叉树的C语言实现" 在计算机科学中，二叉树是一种非线性数据结构，由节点（或称为顶点）和边组成，每个节点最多有两个子节点，通常分为左子节点和右子节点。层次遍历（也称为广度优先搜索，BFS）是遍历或搜索树的一种方法，按照从根节点开始，逐层遍历，先访问同层的左节点，然后右节点的方式进行。在C语言中，我们可以利用队列（Queue）来实现层次遍历。 首先，我们需要定义二叉树节点（BiNode）和队列节点（QNode）的结构体。`BiNode`包含一个字符数据成员（data）以及指向左右子节点的指针。`QNode`则包含一个指向二叉树节点的指针和一个指向下一个队列节点的指针，用于构建链式队列。 ```c typedef struct BiNode { char data; struct BiNode* lchild, *rchild; } BiNode, *BiTree; typedef struct QNode { BiTree data; struct QNode* next; } QNode, *QueuePtr; ``` 接下来，我们定义了一个`LinkQueue`结构体，它包含了队列的前端和后端指针，用于表示队列的状态。 ```c typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; ``` 为了创建二叉树，我们定义了`CreateBiTree`函数，它接受一个二叉树的指针作为参数，采用递归的方式读取输入的字符，生成二叉树结构。 ```c int CreateBiTree(BiTree&T) { // ... } ``` 初始化队列的函数`InitQueue`用于分配内存并设置队列的初始状态。 ```c int InitQueue(LinkQueue&Q) { // ... } ``` `EmptyQueue`函数检查队列是否为空，返回一个布尔值。 ```c int EmptyQueue(LinkQueue&Q) { // ... } ``` `EnQueue`函数将一个二叉树节点入队，即将其添加到队列的末尾。 ```c void EnQueue(LinkQueue&Q, BiTreep) { // ... } ``` `DeQueue`函数出队并返回队列的头元素，同时更新队列的前端指针。这是层次遍历的关键步骤，因为每次遍历都是从队列的头部开始。 ```c int DeQueue(LinkQueue&Q, BiTree&p) { // ... } ``` 层次遍历的主要流程如下： 1. 初始化队列，将根节点入队。 2. 当队列不为空时，出队一个节点，访问该节点，然后将其左右子节点（如果存在）依次入队。 3. 重复步骤2，直到队列为空。 完整的层次遍历函数可能如下所示： ```c void LevelOrderTraversal(BiTree T) { LinkQueue Q; if (InitQueue(Q) == ERROR) return; EnQueue(Q, T); while (!EmptyQueue(Q)) { BiTree p; if (DeQueue(Q, p) == OK) { printf("%c ", p->data); // 访问节点 if (p->lchild) EnQueue(Q, p->lchild); // 左子节点入队 if (p->rchild) EnQueue(Q, p->rchild); // 右子节点入队 } } } ``` 通过以上代码，我们可以实现对二叉树的层次遍历，从而按照层次顺序访问所有节点。这在处理二叉树问题时非常有用，例如在搜索、排序和树的复制等操作中。