python二叉搜索树遍历

在Python中，二叉搜索树（Binary Search Tree，BST）是一种常见的数据结构，它的每个节点都包含一个键值，并且左子树的所有节点的键都小于该节点的键，右子树的所有节点的键都大于该节点的键。遍历BST主要有三种方式：

1. **前序遍历（Preorder Traversal）**：先访问根节点，然后递归地遍历左子树，最后遍历右子树。Python代码示例：

   def preorder_traversal(root):
       if root is not None:
           print(root.val)  # 访问根节点
           preorder_traversal(root.left)  # 遍历左子树
           preorder_traversal(root.right)  # 遍历右子树

2. **中序遍历（Inorder Traversal）**：先递归地遍历左子树，然后访问根节点，最后遍历右子树。对于排序后的BST，这将返回一个升序序列。Python代码：

   def inorder_traversal(root):
       if root is not None:
           inorder_traversal(root.left)
           print(root.val)
           inorder_traversal(root.right)

3. **后序遍历（Postorder Traversal）**：先递归地遍历左子树和右子树，最后访问根节点。Python实现：

   def postorder_traversal(root):
       if root is not None:
           postorder_traversal(root.left)
           postorder_traversal(root.right)
           print(root.val)