Python中的树形深度优先搜索算法
树形深度优先搜索算法是一种基于遍历的算法，它可以用于对树这种数据结构进行遍历。它的基本思路是从根节点开始遍历，一直到叶子节点，同时记录下遍历到的节点，并按照深度优先的方式遍历整个树。以下是Python实现的代码演示：
# 定义树的节点类 class TreeNode: def __init__(self, val): self.val = val self.children = [] # 定义树的遍历函数 def dfs(root): if not root: return [] res = [] queue = [root] while queue: cur = queue.pop() res.append(cur.val) for child in cur.children[::-1]: queue.append(child) return res # 构建示例树 root = TreeNode('p') p1 = TreeNode('i') p2 = TreeNode('d') p3 = TreeNode('a') p4 = TreeNode('n') p5 = TreeNode('c') p6 = TreeNode('o') p7 = TreeNode('d') p8 = TreeNode('e') p9 = TreeNode('!') root.children = [p1, p2, p3] p1.children = [p4, p5] p2.children = [p6, p7] p3.children = [p8, p9] # 输出遍历结果 print(dfs(root)) # ['p', 'a', '!', 'e', 'd', 'o', 'c', 'n', 'd', 'i']
在这个例子中，我们先定义了一个TreeNode类来表示每个树的节点，其包含两个属性，一个是节点的值val，另一个是节点的子节点列表children。然后我们定义了一个深度优先遍历函数dfs，它接受一个根节点作为输入，返回一个遍历结果数组。在函数中，我们使用了一个列表queue来保存待遍历的节点，初始值为根节点。当queue中还有节点时，我们从队列中取出节点cur，将它的值添加到结果数组res中，并将它的所有子节点添加到queue中。由于我们希望遍历时先遍历深度较大的节点，所以我们将子节点列表反转后再依次添加到队列中。最后，当队列为空时，意味着遍历结束，我们返回结果数组res即可。
在最后一段代码中，我们构建了一个示例树，并对它进行了深度优先遍历，输出了遍历结果。由于该树的深度较小，遍历结果比较容易理解。如果我们对更大的树进行遍历，可以通过调整代码中的节点值来观察遍历结果的变化。
相关文章