28、二叉树：原理、实现与操作

二叉树：原理、实现与操作

1. 二叉树基础

二叉树是一种常见的数据结构，在数据存储和检索方面有着广泛的应用。不同的插入顺序可能会生成相同的二叉树，例如，一组 10 个元素可以有 3,628,800 种不同的插入顺序，但最终只会产生 16,796 种不同的树，这些树的形态从完全平衡到完全不平衡都有。

从实际应用的角度来看，有序树在存储和检索随机数据时效率很高，但在处理预排序数据时效果不佳。

2. 树的遍历顺序

对于给定的二叉树，一个常见的操作是遍历它，即依次访问所有元素。这在映射或折叠树时很常见，在搜索特定值时也会用到。树的遍历方式有很多种，主要分为递归和非递归两种。

2.1 递归遍历顺序

以图 10.5 中树的左分支为例，该分支本身是一个由根节点 1、左分支 0 和右分支 2 组成的树。可以用六种顺序遍历这棵树：
- 1, 0, 2
- 1, 2, 0
- 0, 1, 2
- 2, 1, 0
- 0, 2, 1
- 2, 0, 1

可以发现，其中三种顺序与另外三种是对称的。例如，1, 0, 2 和 1, 2, 0 是对称的，都是先访问根节点，然后从左到右或从右到左访问两个分支。只考虑从左到右的方向，就剩下三种顺序，它们根据根节点的位置命名：
- 前序遍历 (1 0 2 或 1 2 0)
- 中序遍历 (0 1 2 或 2 1 0)
- 后序遍历 (0 2 1 或 2 0 1)

这些术语是根据操作中运算符的位置创造的。为了更好地理解，可以将根节点（1）替换为加号（+）：
- 前