本文共 1627 字，大约阅读时间需要 5 分钟。

广度优先和深度优先遍历

广度优先（层次遍历）

广度优先遍历是一种以队列为工作工具的遍历方式，从树的根节点开始，按照从上到下的顺序，逐层遍历所有节点。这意味着我们会先访问根节点，然后访问根节点的左孩子，最后是右孩子，直到树的叶节点为止。这种遍历方式非常适用于需要整体了解树结构的场景。

广度优先的特点

• 顺序规律：根节点首先被访问，然后是它的左孩子和右孩子，依次类推。
• 逻辑清晰：使用队列数据结构可以毫无问题地按层次处理每个节点。
• 应用场景：广度优先遍历可以用来进行树的层次结构分析、图像的灰度处理等。

示例代码

def breadth_travel(self, root):    """利用队列实现树的层次遍历"""    if root is None:        return    queue = []    queue.append(root)    while queue:        node = queue.pop()        print(node.elem)        if node.lchild is not None:            queue.append(node.lchild)        if node.rchild is not None:            queue.append(node.rchild)

代码解读

深度优先遍历

深度优先遍历是一种更“深入”地遍历方式，用于尽可能深入树的叶子节点。它包括三种常见的遍历方式：先序遍历、中序遍历和后序遍历。这些遍历方式在算法领域应用广泛。

深度优先的特点

• 递归特征：每个子问题都会被递归地解决。
• 遍历规律：先序遍历先处理根节点，后处理右子树；中序遍历先处理左子树，再处理根节点，最后处理右子树；后序遍历则处理完左右子树后处理根节点。

先序遍历

先序遍历的顺序是“根节点→左子树→右子树”。这种遍历方式的典型应用是二叉树的前序遍历。

def preorder(self, root):    if root is None:        return    print(root.elem)    self.preorder(root.lchild)    self.preorder(root.rchild)

中序遍历

中序遍历的顺序是“左子树→根节点→右子树”。这个遍历方式通常用于统计节点数量或特定属性的总和。

def inorder(self, root):    if root is None:        return    self.inorder(root.lchild)    print(root.elem)    self.inorder(root.rchild)

后序遍历

后序遍历的顺序是“左子树→右子树→根节点”。这种遍历方式适用于需要最后处理根节点的场景，例如删除或释放资源。

def postorder(self, root):    if root is None:        return    self.postorder(root.lchild)    self.postorder(root.rchild)    print(root.elem)

深度优先的优势

• 逻辑简洁：代码结构遵循递归的思考方式。
• 灵活性高：适用于多种不同的遍历需求。
• 适合复杂结构：无论树的高度如何，深度优先都能有效遍历所有节点。

通过以上内容可以看出，广度优先和深度优先两种遍历方式各有优势。在不同的应用场景下，我们可以根据需求选择合适的遍历算法。