1. 简介
本文将讲解如何对二叉树进行排序，并分析其排序过程中的时间复杂度与空间复杂度。
2. 二叉树概述
二叉树是一种每个节点最多有两个子节点的树形结构，通常称为左子节点和右子节点。
常见的二叉树类型包括：
- 根树（Rooted Binary Tree）
- 满二叉树（Full Binary Tree）
- 完全二叉树（Complete Binary Tree）
- 完美二叉树（Perfect Binary Tree）
- 平衡二叉树（Balanced Binary Tree）
- 退化树（Degenerate Tree）
下图展示了一个完全二叉树的结构：
二叉树的常见表示方式有：
- 数组表示法：按照从上到下、从左到右的顺序填充数组，缺失的子节点位置留空
- 链式表示法：每个节点包含数据、左指针和右指针
3. 二叉搜索树（BST）
二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，满足以下条件：
- 对于任意节点，其左子树中所有节点的值都小于该节点值
- 其右子树中所有节点的值都大于该节点值
- 左右子树本身也是 BST
下图展示了一个大小为 9、深度为 3 的二叉搜索树：
BST 的特性使得查找、插入等操作在平均情况下时间复杂度为 **O(log n)**，最坏情况为 **O(n)**，其中 n 是树的节点数量。
4. 树排序算法（Tree Sort）
4.1 算法定义
树排序是一种在线排序算法，其核心思想是：
- 从数组构建一个二叉搜索树（BST）
- 对 BST 进行中序遍历，从而获得有序序列
具体步骤如下：
✅ 将数组元素依次插入 BST
✅ 对 BST 执行中序遍历以获取排序结果
我们以数组形式输入数据进行排序。
4.2 伪代码实现
插入操作
递归地将元素插入合适的位置：
algorithm insert(node, value):
// INPUT
// node = 当前节点对象
// value = 要插入的值
// OUTPUT
// 返回插入后的节点对象
if node == null:
return new Node(value)
else if value <= node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
中序遍历
递归地访问左子树 -> 根节点 -> 右子树：
algorithm traverseInOrder(node):
// INPUT
// node = 当前节点对象
// OUTPUT
// 按升序打印节点值
if node != null:
traverseInOrder(node.left)
print(node.value)
traverseInOrder(node.right)
5. 复杂度分析
5.1 时间复杂度
BST 插入操作的平均时间复杂度是 **O(log n)**，最坏情况下是 **O(n)**（例如输入数组已排序，导致树退化为链表）。
对于大小为 n 的数组：
- 构建 BST 的时间复杂度为：
- 平均情况：O(n log n)
- 最坏情况：O(n²)
中序遍历操作的时间复杂度为 **O(n)**。
因此，树排序的总时间复杂度为：
✅ 平均情况：O(n log n)
❌ 最坏情况：O(n²)
⚠️ 为了维持平均性能，BST 必须保持平衡。为此，可以使用自平衡 BST，如：
- AVL 树
- 红黑树
- 伸展树（Splay Tree）
- B 树
5.2 空间复杂度
由于需要为每个元素创建一个节点，空间复杂度为 **O(n)**。
6. 总结
本文简要介绍了二叉树、二叉搜索树及其排序方法——树排序。我们给出了插入和中序遍历的核心伪代码，并分析了其时间与空间复杂度。
树排序的效率高度依赖于 BST 的结构是否平衡。若 BST 退化为链表，排序效率会下降到 O(n²)，因此推荐使用自平衡 BST 以获得更稳定的性能。