Python递归实现树的遍历算法
假设我们有一个二叉树的节点类，包含左子节点、右子节点和节点值：
class TreeNode: def __init__(self, val): self.left = None self.right = None self.val = val
为了演示二叉树的遍历算法，我们可以定义一个二叉树类，该类包含根节点，并提供前序遍历、中序遍历和后序遍历的方法：
class BinaryTree: def __init__(self, root=None): self.root = root # 前序遍历 def preorder(self, root): if not root: return print(root.val) self.preorder(root.left) self.preorder(root.right) # 中序遍历 def inorder(self, root): if not root: return self.inorder(root.left) print(root.val) self.inorder(root.right) # 后序遍历 def postorder(self, root): if not root: return self.postorder(root.left) self.postorder(root.right) print(root.val)
使用以上代码，我们可以创建一个二叉树，并演示遍历算法，如下所示：
# 创建一个二叉树 node1 = TreeNode("p") node2 = TreeNode("i") node3 = TreeNode("d") node4 = TreeNode("a") node5 = TreeNode("n") node6 = TreeNode("c") node7 = TreeNode("o") node1.left = node2 node1.right = node3 node2.left = node4 node2.right = node5 node3.left = node6 node3.right = node7 bt = BinaryTree(node1) # 前序遍历 bt.preorder(node1) # 输出 "p i a n d c o d" # 中序遍历 bt.inorder(node1) # 输出 "a i n d p c o d" # 后序遍历 bt.postorder(node1) # 输出 "a n d i c o d p"
上述代码输出了前序遍历、中序遍历和后序遍历的结果。这些算法都是基于递归实现的，每次递归都会遍历一个节点。在访问节点时，我们先访问当前节点的值，再访问其左子节点和右子节点。这样，就可以按照前序遍历的顺序访问整个树。同样的，不同的访问顺序会导致不同的遍历结果。
相关文章