二叉树的层序遍历

树是最基本的数据结构之一。它们用于存储和组织数据。

一种称为二叉树的树形数据结构由左节点和右节点组成，每个节点最多可以有两个子节点。一切都从根节点开始，它是树中的第一个节点。二叉树是一种树形数据结构，由左节点和右节点组成，每个节点最多有两个子节点。根节点——树中的第一个节点——是所有事物的起点。

树的每个节点包含以下信息

指向左子节点的指针。

指向右子节点的指针

对于叶子节点，左右子指针都指向 null。

示例

中序遍历算法

1. 中序遍历 R 的左子树。
2. 处理根 R
3. 中序遍历 R 的右子树。

我们来看一个下面的二叉树示例

其中 LT 是左子树，RT 是右子树，A 是二叉树的根节点。

DEBACF 是一个中序二叉树遍历算法。

例行活动-

以下是一些可以对二叉树执行的典型操作

下表列出了可以对二叉树执行的常见操作。

1. 插入

可以将任何顺序的元素添加到二叉树中。在初始插入过程中，会创建根节点。接下来的插入会递归地在树的每个层级搜索一个空位。当发现左子节点或右子节点为空时，新元素会被添加。作为一种习惯，插入总是从左子节点开始。

二叉树可以按任何顺序添加元素。根节点在初始插入操作时创建。随后的插入会递归地在树的每个层级搜索一个空位。

当发现左子节点或右子节点为空时，就会添加新元素。作为一种习惯，插入总是从左子节点开始。

2. 删除/移除

此外，二叉树也可能丢失其组件之一。由于元素没有按任何特定顺序排列，因此当某个节点被删除时，最右边的元素会取代其位置。

层序遍历是一种广度优先遍历二叉树的技术。我们首先遍历一个节点。因为当前深度的每个邻居节点都必须在移到下一层节点之前被遍历，所以这个过程称为层序遍历。

假设我们得到了一棵树。我们将从打印根节点的值开始，然后是根节点子节点的值，依此类推，在层序遍历树时打印每一层的所有节点的值。我们的主要任务是打印树的当前层级的所有节点，从上到下。我们将使用先进先出 (队列) 方法来处理树，以实现这个想法。然后处理一个节点的子节点并将它们放入队列。每个节点都会被逐一移除、打印，然后其子节点会被放入队列。树是最基本的数据结构之一。它们有一个特定的任务，即存储和组织数据。

二叉树也可以失去一个元素。由于元素没有按任何特定顺序排列，因此当某个节点被删除时，最右边的元素会取代其位置。

层序遍历是一种广度优先遍历二叉树的技术。我们首先遍历一个节点。这个过程之所以被称为层序遍历，是因为它涉及在移到树的下一层节点之前遍历当前深度的每个邻居节点。

假设我们得到了一棵树。我们将从打印根节点的值开始，然后是根节点子节点的值，依此类推，在层序遍历树时打印每一层的所有节点的值。

因此，我们的主要职责是按照从第一层到最后一层的顺序打印树的当前层级中的节点。我们将使用先进先出（队列）技术来处理树，以实现这个想法。

将处理一个节点，并将其子节点添加到队列中。我们将逐个移除每个节点，打印它们，然后将其子节点添加到队列中。下面是层序遍历算法，它说明了完整的过程。

C 语言程序

树的每个节点包含以下内容

1. 数据
2. 指向左子节点的指针
3. 指向右子节点的指针

对于叶子节点，左子节点和右子节点指针都指向 null。

任何允许分支节点按特定顺序组织的树都可以提供中序遍历。实际上，如果您设想一个表达式树，其中节点是“+”或“-”运算符，叶子是数值或变量，那么可能有充分的理由将“+”运算符表示为具有任意数量子节点。然而，如果我们允许特定层级的树具有单个一元子节点，则必须谨慎。

正如在这种树的多数应用中（例如支持否定运算符或“-”运算符的表达式树）一样，我将在下面的示例中将一元子节点视为前序遍历。考虑下面的树定义（使用 Go 作为模板语言定义，但实际上，任何语言都可以）

假设 TreeNode 类型具有 Visit() 函数。

继续使用 Go 作为模板语言，我们现在可以为这个 Tree 结构定义前序、中序和后序遍历。

如您所见，前序和后序遍历非常简单：在前序遍历中，您在每个节点之前调用 Visit()；在后序遍历中，您在每个节点之后调用 Visit()。然而，在 InOrderTraversal() 中，您在每个元素之间进行访问，并且实际上可能多次访问同一个节点。在这种情况下，必须谨慎，并且您必须任意选择先访问节点还是子节点。虽然我在前面的示例中先访问了节点，但您的应用程序可能需要做出更合适的其他决定。

C++

Input:
    1
  /   \ 
 3     2
Output:
1 3 2

Java

输出

Input:
    1
  /   \ 
 3     2
Output:
1 3 2

Python

输出

    Input:
    1
  /   \ 
 3     2
Output:
1 3 2

概述

1. 什么是树的层序遍历？

层序遍历算法按深度顺序遍历树中的每个节点，从根开始，然后是它的子节点，依此类推。

2. 如何进行层序遍历？

可以使用队列和按深度遍历节点来执行层序遍历。

3. BFS 和层序遍历等效吗？

是的，因为这两种算法都按深度遍历节点，所以它们是相同的。

4. 何时适合使用层序遍历？

作为广度优先搜索，层序遍历可用于解决各种图论问题，包括查找单个连通分量中的所有节点。