二叉树按层遍历算法及C语言实现

1. 问题描述

给定一个二叉树，要求输出其按层遍历的序列。按层遍历也称为广度优先搜索（BFS），即从根节点开始，逐层访问二叉树的节点。

2. 算法思路

按层遍历可以使用队列数据结构实现。算法步骤如下：

1. 将根节点入队。2. 当队列不为空时，循环执行以下操作： * 从队列头部取出一个节点，访问该节点。 * 将该节点的左孩子和右孩子（如果存在）依次入队。

3. C语言代码实现c#include <stdio.h>#include <stdlib.h>

// 定义二叉树节点结构体typedef struct _binary_treeNode { int data; struct _binary_treeNode* left; struct _binary_treeNode* right;} BiTreeNode;

// 创建二叉树BiTreeNode* createBiTree(int n) { BiTreeNode** nodeArray = (BiTreeNode**)malloc(sizeof(BiTreeNode*) * n); for (int i = 0; i < n; i++) { nodeArray[i] = (BiTreeNode*)malloc(sizeof(BiTreeNode)); nodeArray[i]->data = i; nodeArray[i]->left = NULL; nodeArray[i]->right = NULL; }

int a, b, lr;    for (int i = 0; i < n - 1; i++) {        scanf('%d %d %d', &a, &b, &lr);        if (lr == 0) {            nodeArray[a]->left = nodeArray[b];        } else {            nodeArray[a]->right = nodeArray[b];        }    }

BiTreeNode* root = nodeArray[0];    free(nodeArray);    return root;}

// 按层遍历二叉树void levelOrderTraversal(BiTreeNode* root) { if (root == NULL) { return; }

BiTreeNode** queue = (BiTreeNode**)malloc(sizeof(BiTreeNode*) * 10000);    int front = 0, rear = 0;

queue[rear++] = root;

while (front < rear) {        BiTreeNode* node = queue[front++];        printf('%d ', node->data);

    if (node->left != NULL) {            queue[rear++] = node->left;        }

    if (node->right != NULL) {            queue[rear++] = node->right;        }    }

free(queue);}

int main() { int n; scanf('%d', &n);

BiTreeNode* root = createBiTree(n);

levelOrderTraversal(root);    printf('

');

// 释放内存    free(root);

return 0;}

4. 代码说明

• 代码中首先定义了二叉树节点结构体 BiTreeNode，包含数据域 data 和指向左右孩子的指针 left 和 right。* createBiTree 函数根据输入创建二叉树，并返回根节点。* levelOrderTraversal 函数实现按层遍历算法，使用队列存储节点，依次访问每个节点并将其孩子节点入队。* 主函数 main 中，首先读取节点个数 n，然后调用 createBiTree 函数创建二叉树，最后调用 levelOrderTraversal 函数进行按层遍历并输出结果。

5. 总结

二叉树的按层遍历是一种常用的遍历方式，可以使用队列实现。理解该算法可以帮助我们更好地处理树形结构数据。