二叉搜索树（BST）的定义及性质

# 1. 简介

1.1 什么是二叉搜索树（BST）？

二叉搜索树（Binary Search Tree，简称BST）是一种常见的数据结构，它具有以下特点：
- 每个节点最多有两个子节点，分别为左子节点和右子节点；
- 对于每个节点，其左子树中的节点值小于该节点的值，右子树中的节点值大于该节点的值；
- 左右子树也分别为二叉搜索树。

1.2 二叉搜索树的历史和应用

二叉搜索树最早由Adelson-Velsky和Landis在1962年提出，并且在计算机科学领域得到了广泛的应用。二叉搜索树常用于实现动态集合的操作，例如查找、插入、删除等，同时也能应用于算法设计中。在实际项目中，二叉搜索树的高效查找特性使其成为一个重要的数据结构。

# 2. 二叉搜索树的基本定义

二叉搜索树（Binary Search Tree，简称BST）是一种常见的数据结构，在计算机科学领域中被广泛运用。BST具有以下基本定义和性质：

### 节点的结构

在二叉搜索树中，每个节点包含一个键值，以及指向左子树和右子树的指针。节点的键值遵循以下规则：

- 若左子树不为空，则左子树上所有节点的键值均小于该节点的键值
- 若右子树不为空，则右子树上所有节点的键值均大于该节点的键值
- 左右子树也分别为二叉搜索树

### 有序性质

由于BST的定义规定了节点的键值与子树之间的大小关系，因此BST具有有序性质。对BST进行中序遍历将得到一个递增的序列。

### 查找操作

通过比较目标键值和当前节点的键值，可以在BST中进行高效的查找操作。从根节点开始，若目标键值较小则移动到左子树，若较大则移动到右子树，直到找到目标节点或搜索失败。

### 插入与删除操作

插入操作通过查找找到插入位置，将新节点插入到对应位置。删除操作涉及待删除节点的情况讨论：若待删除节点为叶子节点，则直接删除；若只有一个子节点，则将子节点替换待删除节点；若有两个子节点，则找到后继节点替换。

二叉搜索树的基本定义为设计算法和解决问题提供了基础，下一节将介绍BST的性质。

# 3. 二叉搜索树的性质

二叉搜索树具有一些重要的性质，这些性质对于理解二叉搜索树的操作和应用非常关键。接下来我们将详细介绍二叉搜索树的几个重要性质。

#### 3.1 二叉搜索树的中序遍历特性

二叉搜索树的中序遍历是有序的，即将二叉搜索树按照中序遍历的顺序输出，可以得到一个递增的排序序列。这一性质为二叉搜索树的查找操作提供了便利，也为其他操作提供了基础。

# Python中序遍历二叉搜索树的代码示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

# 示例代码演示
# 构建一个二叉搜索树
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right =