4

从集合中的每个键排列生成一个 BST（通过连续插入节点）

{1、2、3、4、5、6、7、8、9、10、11}。

有多少排列决定高三的树？

4

2 回答 2

0

您必须检查的节点排列数是 11！= 39,916,800，所以你可以写一个程序来暴力破解。这是一个用 C++ 编写的骨架：

vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
unsigned numSuccesses = 0;
do {
    if (bstHeightOf(values) == 3) values++;
} while (next_permutation(values.begin(), values.end());

在这里，您只需要编写bstHeightOf函数，该函数计算通过按指定顺序插入给定节点形成的 BST 的高度。我将把它留作练习。

您可以使用以下观察结果来修剪大量搜索空间：

  1. 高度为 2 的 BST 中的最大节点数为 7。
  2. 根不能是 1、2、3、9、10 或 11，因为如果是，一棵子树中的节点将超过 7 个，因此整个树的高度将大于 3。

鉴于您知道可能的根，一种选择是使用键 {1, 2, 3, ..., 11} 生成所有 BST（不是通过列出所有排序，而是通过列出所有树），过滤它直到高度为 3 的节点集，然后使用此递归算法计算通过插入值可以构建每棵树的方式数。这可能会比上述方法快得多，因为要检查的树的数量远低于排序的数量，并且可以在线性时间内检查每棵树。

希望这可以帮助！

于 2013-10-16T23:33:00.877 回答
0

替代 templatetypdef 的答案可能更棘手，但可以完全手动完成。

考虑高度为 3 的完全二叉树：它有 15 个节点。您正在寻找具有 11 个节点的树；这意味着这 15 个节点中有 4 个丢失了。可以毫不费力地列举出这些缺失节点可能出现的模式。（提示：我通过将模式分成两组来做到这一点。）这将为您提供具有 11 个节点的高度为 3 的树的所有形状。

完成此操作后，您只需要推理这些树形与您正在寻找的实际树之间的关系。（提示：这种关系非常简单——不要想太多。）

这允许您枚举满足要求的结果树。如果你达到 96，你得到的结果和我一样。对于这些树中的每一个，我们现在需要找出有多少排列产生了这棵树。

这部分是棘手的部分；您现在可能需要将这些树分成更小的组，通过对称性您知道，产生该树的排列数量对于组中的所有树都是相同的。例如，

       6
      / \
     /   \
    3     8
   / \   / \
  2   5 7   10
 /   /     / \
1   4     9   11

将有相同数量的排列产生它

       6
      / \
     /   \
    4     9
   / \   / \
  2   5 7   11
 / \     \  /
1   3    8 10

您还需要找出每组中有多少棵树；这个例子的类包含 16 棵树。（提示：我将它们分成 7 组，每组 2 到 32 棵树。）现在你需要为每组找出产生这种树的排列数。您可以“递归地”确定这一点，仍然在纸上；对于包含上面两个示例树的类，我得到 12096 个排列。由于该类包含 16 棵树，因此导致此类树的排列总数为 16*12069 = 193536。对其他六个类执行相同操作，并将数字相加得到总数。

如果此解决方案的任何特定部分让您感到困惑或有任何不清楚的地方，请不要犹豫！

于 2013-10-17T21:23:00.163 回答