二叉搜索树是一种重要的数据结构，它的每个节点最多有两个子节点，称为左子节点和右子节点。
二叉搜索树的特性是：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
构建二叉搜索树如下图所示：
二叉搜索树的遍历有三种基本方式：先序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。
-
先序遍历
先序遍历的顺序是：根节点 -> 左子树 -> 右子树。也就是说，先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。
def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
preorder_traversal(root) # 4 2 1 3 6 5 7
-
中序遍历
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。也就是说，先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
inorder_traversal(root) # 1 2 3 4 5 6 7
中序遍历一棵二叉搜索树可以生成一个有序序列
-
后序遍历
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。也就是说，先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
postorder_traversal(root) # 1 3 2 5 7 6 4
