python 层次遍历

在Python中，层次遍历通常用于处理嵌套的数据结构，如字典或树形数据结构。层次遍历也称为深度优先搜索（Depth-First Search, DFS），它按照从上到下、从左到右的顺序递归地访问节点。

例如，如果你有一个代表目录结构的嵌套字典：

directory = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': [],
    'D': []
}

你可以使用递归函数来实现层次遍历：

def traverse_directory(directory, path=""):
    for key in directory:
        new_path = f"{path}/{key}" if path else key
        print(new_path)
        traverse_directory(directory[key], new_path)

traverse_directory(directory)

这将输出每个文件夹及其内容，按层次结构显示。

相关问题

python 二叉树层次遍历

二叉树的层次遍历可以使用广度优先搜索（BFS）的方式来实现。以下是一个示例的 Python 代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        level_size = len(queue)
        level_values = []

        for _ in range(level_size):
            current_node = queue.pop(0)
            level_values.append(current_node.val)

            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)

        result.append(level_values)
    return result

你可以创建一个 `TreeNode` 类来表示二叉树的节点，其中 `val` 是节点的值，`left` 和 `right` 分别表示左子节点和右子节点。然后，定义 `levelOrder` 函数来进行层次遍历。

在 `levelOrder` 函数中，我们首先判断根节点是否为空。如果为空，则直接返回空列表。接下来，我们使用一个队列 `queue` 来存储待遍历的节点。将根节点加入队列后，我们进入循环。在每一层的循环中，我们首先获取当前层的节点数量 `level_size`，然后创建一个空列表 `level_values` 来存储当前层的节点值。

接下来，我们通过循环从队列中取出 `level_size` 个节点，并将其值加入到 `level_values` 列表中。同时，如果当前节点的左子节点和右子节点存在，则将它们加入到队列中。完成当前层的遍历后，将 `level_values` 加入到结果列表 `result` 中。

最后，当队列为空时，表示遍历完成，我们返回结果列表 `result`。

这样，调用 `levelOrder` 函数并传入二叉树的根节点，即可得到二叉树的层次遍历结果。

python二叉树层次遍历

二叉树层次遍历是一种广度优先遍历算法，也被称为BFS遍历。它的主要思想是按照树的层次结构，从根节点开始逐层遍历整棵树，直到所有节点都被遍历完为止。

在Python中实现二叉树的层次遍历，可以使用队列来存储每一层的节点，具体实现步骤如下：

1. 定义一个队列，并将根节点入队
2. 循环遍历队列，直到队列为空
3. 对于每个节点，将其左子节点和右子节点依次入队
4. 对于每个节点，将其值输出

以下是 Python 实现代码：

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        cur_level = []
        for i in range(len(queue)):
            node = queue.pop(0)
            cur_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(cur_level)
    return res