3.2.11 #

解答 #

树的高度为树中深度最大的点的深度。

因此 N 个结点最多只能构造出高度为 N-1 的树来，并不能构成高度为 N 的树。

如果将题目变为用 N 个结点构造高度为 N-1 的二叉搜索树。

这样的树即为二叉搜索树的最坏情况，除唯一的叶子结点之外，每个结点有且只有一个子树。

于是除根结点外，每个结点都有两种选择，要么在左，要么在右。

因此共有 $2 ^ {n - 1}$ 种形状。

接下来证明，对于某一种确定的最坏情况，在 N 个元素各不相同的情况下，输入顺序是唯一的。

证明：

就 1 2 3 这三个元素而言，构造这样一棵树：

  2
1   3

可以有 2 1 3 和 2 3 1 两种序列，因为在插入 2 之后可以选择的位置有两个

但最坏情况下的二叉搜索树不存在具有两个子结点的结点，因此输入顺序是唯一的。

反证：

也可以这样考虑，假设序列 A 可以构造出一棵最坏情况下的二叉树，插入顺序为 $x_1 \dots x_n$

假设存在与 A 顺序不同的序列 B，它构造出的二叉树与 A 的相同。

由于 A 和 B 的元素相同，因此 A 必然可以通过有限次元素交换得到 B。

根据最坏情况下的二叉搜索树的性质，A 中的元素 $x_n$ 必然满足 $x_1 \dots x_{n - 1}$ 的所有关系。

例如，假设 $x_1 > x_2$， 则 $x_3$ 也必然满足 $x_1 > x_3$，即后面的元素必然满足前面元素的关系。

于是 A 存在关系序列 $r_1 \dots r_{n - 1}$，只有满足这样序列的输入才能构造出对应的二叉树。 （可以将 $r$ 理解为大于号或者小于号，由于元素各不相同，因此不存在等号）

显然 A 中的任意两个元素交换会导致至少一个 $r$ 倒置，除非进行逆向交换，否则这种倒置不可能消除。 （大于号和小于号是不满足交换律的）

因此 A 和 B 必定相同，得证。

于是每一种最坏情况下的形状都唯一对应一种输入序列，共有 $2 ^ {n - 1}$ 种构造方式。